Suppose is a polynomial with integer coefficients such that for every positive integer , the sum of the decimal digits of is not a Fibonacci number. Must be constant?
(A Fibonacci number is an element of the sequence defined recursively by , , and for .)
Solution
The answer is yes, must be constant. By we mean the sum of the decimal digits of .
We need two claims.
Claim — If is nonconstant with positive leading coefficient, then there exists an integer polynomial such that all coefficients of are positive except for the second one, which is negative.
Proof. We will actually construct a cubic . We call a polynomial good if it has the property.
First, consider . Observe that in , every coefficient is strictly positive, except for the second one, which is zero.
Then, let . Using continuity as , it follows that if is large enough (in terms of ), then is good, with being the only negative coefficient.
Finally, we can let where is a sufficiently large multiple of (in terms of the coefficients of ); thus the coefficients of dominate (and are integers), as needed.
Claim — There are infinitely many Fibonacci numbers in each residue class modulo 9.
Proof. Easy. First note the Fibonacci sequence is periodic modulo 9 (indeed it is periodic modulo any integer). Moreover (allowing negative indices),
We now show how to solve the problem with the two claims. WLOG satisfies the conditions of the first claim, and choose as above. Let
where (and ). Then if we select for large enough (say ), the decimal representation consists of the concatenation of
* the decimal representation of ,
* the decimal representation of
* the decimal representation of , with several leading zeros,
* the decimal representation of , with several leading zeros,
* ...
* the decimal representation of , with several leading zeros.
(For example, if , then .)
Thus, the sum of the digits of this expression is equal to
for some constant depending only on and , independent of . But this will eventually
hit a Fibonacci number by the second claim, contradiction.