Proof the Fibonacci numbers are not a polynomial.

Question

I was asked a while ago to prove there is no polynomial $P$ in $\mathbb R$ such that $P(i)=f_i$ for all $i\geq0$. I tried to get a proof as slick as possible and here's what I got.

Let $p(x)=a_nx^n+a_{n-1}x^{n-1}+\dots +a_1x+a_0$ . Construct the polynomials $p_1(x)=a_n(x-1)^n+a_{n-1}(x-1)^{n-1}+\dots +a_1(x-1)+a_0$ and $p_2(x)=a_n(x-2)^n+a_{n-1}(x-2)^{n-1}+\dots +a_1(x-2)+a_0$.

Then the polynomial $p-(p_1+p_2)$ has infinitely many roots since $p(i)=p_1(i)+p_2(i)$ for $i$ an integer $\ge 1$ because of the Fibonacci recurrence. Hence we have $p_1+p_2=p$ since a non-zero polynomial of degree $n$ can have at most $n$ zeros.

However $p_1+p_2$ has leading coefficient $2a_n$. So they cannot be equal.

What do you think of my proof. Can you find other proofs? Simpler proofs? harder proofs? The less standard the better. I appreciate proofs which might look excessive in the amount of theory they use, although only if they finish quickly.

Thank you very much.

Regards

Answer 1

(A riff on a deleted answer:)

Any polynomial sequence has a rational generating function of the form $\frac{P(x)}{(1-x)^k}$. This can be seen by repeatedly differentiating the geometric series.

The Fibonacci sequence has generating function $\frac{x}{1-x-x^2}$, which is not of this form. Since generating functions are unique, it follows that the Fibonacci sequence is non-polynomial.

Answer 2

If we consider ratios of the Fibonacci numbers we can come up with a quick growth rate: $$\frac{F_{n+1}}{F_{n}} = \frac{F_{n} + F_{n-1}}{F_n} = 1 + \frac{F_{n-1}}{F_n}<2$$ and $$\frac{F_{n-1}}{F_{n}} = \frac{F_{n-1}}{F_{n-1}+F_{n-2}} > \frac{F_{n-1}}{2 F_{n-1}} = 1/2$$ which means $$1.5 < \frac{F_{n+1}}{F_n} < 2.$$ Hence, $(1.5)^n < F_n < 2^n$ for $n>1$ which means that the growth rate for the Fibonacci numbers is exponential.

Suppose $p(i)=F_i$ for some polynomial (of degree $m$) then the polynomial can be written as $$p(x) = a_m x^m + a_{m-1} x^{m-1} + \cdots + a_0.$$ Thus $$|F_n| = |p(n)| \le n^m \sum_{i=1}^m |a_m| := Cn^m.$$ This means $$(1.5)^n < Cn^m$$ for all $n$.

We can demonstrate that this inequality cannot hold for all $n$. It is clearer when logarithms are used: $$(1.5)^n < Cn^m$$ which means $$n \ln(1.5) < \ln(C) + m \ln(n)$$ and $$\ln(1.5) < \frac{\ln(C)}{n} + m \frac{\ln(n)}{n}.$$ The term $\ln(C)/n$ goes to zero as $n \to \infty$ and so does $\ln(n)/n$. However, since $\ln(1.5) > 0$ this is a contradiction.

Answer 3

Taking successive differences of a nonzero polynomial should result in a polynomial of the next smallest degree. That is, if $p$ is degree $n$, then $p(x)-p(x-1)$ should be of degree $n-1$.

But if $p(i)$ gives Fibonacci numbers, then $p(i)-p(i-1)=p(i-2)$. So $\deg p=\deg(p)-1$, a contradiction. (This is a different take on your argument (which is great) since you asked about alternatives.)

Answer 4

Consider repeated differences. That is, write down a row $p(1),p(2),p(3),\ldots$ and then in the next row the differences $p(2)-p(1),p(3)-p(2),p(4)-p(3),\ldots$ of the first row, then in the third row the differences of the second row, and so on. It should be well-known that a row obtained from a polynomial of degree $n$ produces values from a polynomial of degree $n-1$ in the next row and so on, so eventually we arrive at a degree $0$ (i.e., constant) row and from than on at all-zero rows.

However, if we start this with the Fibonacchi sequence, the next row is the (shifted) Fibonacci sequence and we will never obtain an all-zero row.

Answer 5

$F_1=1$ and $F_3=2$ so their difference is odd.

Polynomials have the property $P(x+n)-P(x)$ is divisible by $n$, and in particular $P(x+2)-P(x)$ is always even.

Answer 6

The simplest I can think of, in broad strokes: Fibonacci numbers are roughly exponential, and an exponential function grows faster than any polynomial, so they can't be represented by a polynomial. QED.

We can formalize this to pretty much any level desired. Let's start with the first assertion, that Fibonacci numbers are roughly exponential. Fibonacci numbers are defined by F(n) = F(n - 1) + F(n - 2), plus some initial conditions (here, F(0) = 0, F(1) = 1, but similar sequences with different initial conditions work just as well). Dividing through (since F(n) is positive for n > 0, we'll assume an appropriate n), F(n)/F(n - 1) = 1 + F(n - 2)/F(n - 1), so if we define r(n) = F(n)/F(n - 1), r(n) = 1 + 1/r(n - 1). Let r(k) = ø + e for some e and k. Then r(k + 1) = 1 + 1/(ø + e). 1/(ø + e) = (1/ø)/(1 + e/ø), which, when |e/ø| < 1, is a geometric series, (1/ø)(1 - e/ø + (e/ø)^2 - ...). Going back to r(k + 1), that's 1 + (1/ø)(1 - e/ø + ...) = 1 + 1/ø - (e/ø^2)(1 - e/ø + ...) = 1 + 1/ø - (e/ø^2)/(1 + ø/e) = 1 + 1/ø - (e/ø)(1/(ø + e)). Now, ø = (1 + sqrt(5))/2, so 1 + 1/ø = ø. Therefore, r(k + 1) = ø - (e/ø)(1/(ø + e), or, in other words, r(k + 1) = ø + f, where f = -(e/ø)(1/(ø + e)). For all e < -ø^3 or e > -ø, |f| < |e|, though we must make sure that -ø < e < ø for the geometric series trickery to work, and for the Fibonacci sequence in particular, the first real value for r is r(2) = 1, with e = ø - 1 falling well in this range and, subsequent differences being smaller, only produces more values in this range. Therefore, we can say that growth of the Fibonacci series is bounded between r(n) = 1 and r(n) = 2ø - 1. However, the sequence being bounded by 1^n isn't particularly useful, so we'll use the next two ratios of 2 and 3/2 to note that Cl·(3/2)^n ≤ F(n) ≤ Cr·2^n, where Cl and Cr are positive constants. In particular, F(n) ≥ Cl·(3/2)^n.

The rest can be proved similarly, in as much detail as you care about.