37
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Except for slight nits on the notation used, looks good. You may want to use plus signs to seperate the terms and use $p_1(x), p_2(x)$ to avoid confusion with derivatives. $\endgroup$ – Macavity Jan 13 '15 at 15:18
  • $\begingroup$ thanks, I think It's better now. $\endgroup$ – Jorge Fernández Hidalgo Jan 13 '15 at 15:21
  • 1
    $\begingroup$ The change in notation cleared up your argument for me. Very nice and simple. I guess my experience as an analyst lead me in a different direction. $\endgroup$ – Joel Jan 13 '15 at 15:50
  • $\begingroup$ Fibonacci numbers grow faster than any polynomial, so just start with some asymptotic formula. $\endgroup$ – kjetil b halvorsen Jan 14 '15 at 17:01
34
$\begingroup$

(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.

$\endgroup$
  • 1
    $\begingroup$ You math guys never cease to amaze me. (I'm a physics guy who programs games) $\endgroup$ – Almo Jan 14 '15 at 0:11
  • $\begingroup$ @Micah I often heard about generating functions of sequences here on math.SE, but I've never had it covered by the lectures I attended so far and I'd like to learn about them. Can you tell me what keywords I have to look for / in what branch of maths this concept is used? $\endgroup$ – flawr Jan 14 '15 at 10:23
  • 2
    $\begingroup$ @flawr I recommend Graham, Knuth, Patashnik 'Concrete Mathematics. A Foundation for Computer Science'. Generating functions are pretty well covered there and book doesn't require much mathematical knowledge. $\endgroup$ – Crazy Yoghurt Jan 14 '15 at 14:18
  • $\begingroup$ @flawr Generating functions are a standard topic covered in a combinatorics course. They are also used in number theory. When I was an undergraduate I read "A Walk through Combinatorics" by Miclos Bona. He has a couple of good chapters on the subject in there. $\endgroup$ – Joel Jan 14 '15 at 16:20
  • $\begingroup$ @flawr: I learned about generating functions from Herbert Wilf's generatingfunctionology. An older edition of it is freely and legally available as a pdf. $\endgroup$ – Micah Jan 14 '15 at 16:50
48
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ I like it. Although the degree is at most $n-1$ I think. (It doesn't matter for the solution though). $\endgroup$ – Jorge Fernández Hidalgo Jan 13 '15 at 15:36
  • $\begingroup$ What I meant is that in the first paragraph it whould say " That is, if $p$ is degree $n$ then $p(x)-p(x-1)$ should be degree at most $n-1$" $\endgroup$ – Jorge Fernández Hidalgo Jan 13 '15 at 15:43
  • 2
    $\begingroup$ @ModdedBear While with arbitrary polynomials you have to worry about cancellation, here in fact the result is sharp; $p(x)-p(x-1)$ will be of degree exactly $n-1$. (This can be shown via a discrete version of the FTC; if you're curious about the details I encourage you to ask a question about it.) $\endgroup$ – Steven Stadnicki Jan 13 '15 at 17:43
  • 1
    $\begingroup$ Oh yeah. The proof is simple. The coeficient of the leading term is going to be $-na_n$ $\endgroup$ – Jorge Fernández Hidalgo Jan 13 '15 at 18:42
  • 1
    $\begingroup$ @StevenStadnicki: Ah, okay. I thought that you said that if $p$ is an arbitrary polynomial then you'd need to worry about cancellation in $p(x)-p(x-1)$, but not for the particular one we were looking at here. $\endgroup$ – Henning Makholm Jan 14 '15 at 16:06
26
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've seen that argument , I like it. can you make the part in the end actually do the math though? thanks. $\endgroup$ – Jorge Fernández Hidalgo Jan 13 '15 at 15:28
  • $\begingroup$ Which part would you like me to clarify? The polynomial growth or the exponential inequality? $\endgroup$ – Joel Jan 13 '15 at 15:30
  • $\begingroup$ The part at the very end where you say polynomial growth is slower than exponential growth. Everything else is perfect. $\endgroup$ – Jorge Fernández Hidalgo Jan 13 '15 at 15:31
  • 2
    $\begingroup$ Changed as requested. :) $\endgroup$ – Joel Jan 13 '15 at 15:41
8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Actually, this proof might be viewed just as a disguise of your own proof $\endgroup$ – Hagen von Eitzen Jan 13 '15 at 17:06
  • $\begingroup$ +1 This is exactly what I was thinking with my answer. I'm at a loss as to why my answer here took off so much, but I'm not complaining. $\endgroup$ – alex.jordan Jan 15 '15 at 21:49
2
$\begingroup$

$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.

$\endgroup$
  • 1
    $\begingroup$ Interesting... but, does this disprove polynomials with noninteger coefficients? $\endgroup$ – orion Jan 14 '15 at 10:27
  • $\begingroup$ Perhaps not ... $\endgroup$ – Henry Jan 14 '15 at 10:40
  • $\begingroup$ @orion If it's a polynomial, we may assume that it's a polynomial with rational coefficients (with denominators dividing the factorial of the degree). So $cF_n =p(n)$ for some polynomial with integer coefficients, $c$ an integer. Then for $(n,c)=1$, we need $n \mid F_{x+n}-F_x$ for all $x$. Can we do anything with this? $\endgroup$ – awwalker Jan 15 '15 at 8:41
  • $\begingroup$ @A Walker: Perhaps not: $n(n+1)/2$ is an example of a polynomial with rational coefficients where $P(x+2)-P(x)$ is odd $\endgroup$ – Henry Jan 15 '15 at 12:06
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.