In a sequence $P_n$ of quadratic trinomials each trinomial, starting with the third, is the sum of the two preceding trinomials. The first two trinomials do not have common roots. Is it possible that $P_n$ has an integral root for each $n$?
Problem
Source: Tuymaada 2021 Senior P8
Tags: polynomial, quadratics, algebra, rational functions
IndoMathXdZ
31.07.2021 02:06
A non conventional polynomial problem, and quite a unique exercise for polynomials. Solved with some moral support from Elben85. The answer is $\boxed{no}$. Suppose otherwise, that such a sequence of polynomials exists. Let $F_n$ be the fibonacci number, where $F_0 = 0, F_1 = 1$ and $F_{i + 2} = F_{i + 1} + F_i$ for all $i \ge 0$. Claim 01. For all $n \ge 2$, we have $P_n = F_{n - 2}P_1 + F_{n - 1} P_2$. Proof. We will prove this by induction on $n$. For $n = 2$, we have $P_2 = P_2$ which is true and for $n = 3$, it is indeed true that $P_3 = P_1 + P_2$. Now suppose that this is true for all $n \le k$, then \[ P_{k + 1} = P_k + P_{k -1} = (F_{k - 2} P_1 + F_{k - 1} P_2) + (F_{k - 3} P_1 + F_{k - 2}P_2) = F_{k -1}P_1 + F_k P_2\]and therefore, by induction, this statement is true for all $n \ge 2$. Let $r_i$ be the integer root (if there are two, pick one) of $P_i$, which must exists from the condition of the problem. We have that for all $n \ge 3$, \begin{align*} F_{n - 2}P_1(r_n) + F_{n - 1} P_2(r_n) &= 0 \\ F_{n - 2} P_1(r_n) &= -F_{n - 1} P_2(r_n) \\ \frac{P_1(r_n)}{P_2(r_n)} &= - \frac{F_{n - 1}}{F_{n - 2}} \end{align*}Let $f$ be defined as a function such that $f(x) = \frac{P_1(x)}{P_2(x)}$. Claim 02. $r_i \not= r_j$ for any $i \not= j$. Proof. First of all, we have $r_1 \not= r_2$ from the condition of the problem. Indeed, $r_i \not= r_1, r_2$, because we could just check $f(r_i)$. Now, suppose $r_i = r_j$, for some $i \not= j$, then take the pair $(i,j)$ that minimizes the sum of $i + j$. We have $i,j \ge 3$ from the above argument. \[ \frac{F_{i - 1}}{F_{i - 2}} = \frac{F_{j - 1}}{F_{j - 2}} \]We then have $1 + \frac{F_{i - 3}}{F_{i - 2}} = 1 + \frac{F_{j - 3}}{F_{j - 2}} \implies \frac{F_{i - 2}}{F_{i - 3}} = \frac{F_{j - 2}}{F_{j - 3}}$, which gives us a more minimal pair. Now, suppose that $P_i(x) = a_i x^2 + b_i x + c$ for $i \in \{ 1, 2 \}$. Claim 03. $\frac{a_2}{a_1}$ is an irrational. Proof. We have \[ \frac{P_1(r_n)}{P_2(r_n)} = - \frac{F_{n- 1}}{F_{n- 2}} \]However, since $r_i \not= r_j$ for all $i \not= j$, this means that $\lim_{n \to \infty} |r_n| = \infty$. Indeed, we have \[ \frac{a_1}{a_2} = \lim_{n \to \infty} \frac{P_1(r_n)}{P_2(r_n)} = \lim_{n \to \infty} - \frac{F_{n - 1}}{F_{n - 2}} = - \frac{\sqrt{5} + 1}{2} \] Now, we will prove that $\frac{a_2}{a_1}$ should have been rational, forcing a contradiction. Claim 04. $f$ is uniquely determined by $f(x_i) = y_i$ on $5$ distinct points. Proof. Indeed, suppose there are two such functions $f_1 = \frac{P_1}{P_2}$ and $f_2 = \frac{Q_1}{Q_2}$. Then, we have \[ \frac{P_1(x)}{P_2(x)} = \frac{Q_1(x)}{Q_2(x)} \implies P_1(x)Q_2(x) - P_2(x)Q_1(x) = 0 \]for five distinct roots of $x$. However, if $R(x) = P_1(x)Q_2(x) - P_2(x)Q_1(x)$ is not the null polynomial, then $R$ has degree of maximum four. However, $R$ is $0$ for five distinct inputs, this forces $R$ being null. Now, take $\alpha, \beta$ real roots of $P_1$, note that by the condition of the problem, $\alpha, \beta$ is not the root of $P_2$, plugging $R(\alpha), R(\beta)$ forces $Q_1 = c \cdot P_1$ for some constant $c$. Indeed, we know that there exists a function $f$ such that $f(r_n) = -\frac{F_{n- 1}}{F_{n- 2}}$ for all $n \in \mathbb{N}$. Note that $f$ is uniquely determined by the first five $r_3, r_4, r_5, r_6, r_7$. However, viewing \[ F_{n - 2} P_1(r_n) + F_{n - 2} P_2(r_n) = 0 \]with $F_i, r_i$'s being fixed, we get a linear equation with $a_1, a_2, b_1, b_2, c_1, c_2$ as variables. However, by a well known application of linear algebra, we could see that since $F_i, r_i \in \mathbb{Z}$ for any $i \in \mathbb{N}$, then we would deduce that $a_1, a_2, b_1, b_2, c_1, c_2 \in \mathbb{Q}$. This gives us $\frac{a_2}{a_1} \in \mathbb{Q}$.
This problem is quite a hard nut to crack, especially when polynomial is not my best subject. The solution above utilizes the polynomial as a whole, roots, and coefficients. Here I'll try to outline my motivation in the solution above.
For the first 30 minutes, I thought that the answer was yes: and if it were yes, the easiest way to do so is to construct a "recursion" of polynomial because this is the easiest way to "keep track" that all $P_n$ has integer roots. However, after trying solving a bunch of recursion for about 30 minutes, I decided to go with "no" instead.
Now, it's natural to rephrase the problem with the following form: $P_n = F_{n - 1} \cdot P_2 + F_{n - 2} \cdot P_1$ to have integer roots. There are particularly no concrete information about the "integer roots": so let $r_n$ be the integer root of $P_n$ for each $n$. We would get
\[ \frac{P_1(r_n)}{P_2(r_n)} = -\frac{F_{n - 1}}{F_{n - 2}} \]for all $n \ge 3$. This looks great because we have two fixed polynomials to deal with. Indeed, this and the condition of the problem easily implies that $r_1,r_2, r_3, r_4, \dots$ are all distinct. Therefore, $\lim_{n \to \infty} |r_n| = \infty$
Indeed, from here we get that if $P_1(x) = a_1x^2 + b_1x + c_1$ and $P_2(x) = a_2x^2 + b_2x + c_2$, then by taking $n$ really large, we would get $\frac{a_1}{a_2} = - \frac{\sqrt{5} + 1}{2}$. Heuristically, we believe that if $\frac{P_1(x)}{P_2(x)}$ is a rational number for infinitely many $x \in \mathbb{Z}$, then $\frac{a_1}{a_2}$ should be rational, so if we manage to prove this, we could easily derive a contradiction. The first thing I tried is to look at $\frac{P_1(x)}{P_2(x)}$ in term of its roots: $\frac{(x - r_1)(x - \alpha)}{(x - r_2)(x - \beta)}$, and tried manipulating this recursively which doesn't work out well because of several reasons: there are too many variables to keep track with, and even if it does work, tracking $\frac{(x - r_1)(x - \alpha)}{(x - r_2)(x - \beta)}$ as a "seperate" part of two polynomials would be really hard. Therefore, we could try considering this function $f(x) = \frac{P_1(x)}{P_2(x)}$ and try what we could get from here. What we know is that $f(x) \in \mathbb{Q}$ for infinitely many $\mathbb{Z}$. A common polynomial trick would be to force something equals to $0$ with "infinitely many zeroes"; but the most convenient way we could get from here is that $\frac{P_1}{P_2} - \frac{P_1'}{P_2'} = 0$ if they coincide at infinitely zeroes, in fact five points work (concerning the degree of both polynomials and just force it to be null with enough number of zeroes). Now, because we have a unique function. This means we could just make sure that this function should work on all large $r_i$. Indeed, fixing $P,Q$ and since we know that there should exists $r_i$ so that $f(r_i) =-\frac{F_{n + 1}}{F_n}$, now instead of considering the system of equation $F_{n - 2} P_1(r_n) + F_{n - 1}P_2(r_n) = 0$ in terms of $r_n$; we are more interested in the value of $\frac{a_2}{a_1}$, in which it's better to view this equation wrt the coefficients of $P_1, P_2$: and we get a system of linear equations, in which the solution has to be rational, which means $\frac{a_3}{a_1}$ should be rational. But we know that this leads to the unique polynomial we wanted -- for which we are done.