Let F1 = 1, F2 = 1, Fn+2 = Fn+1 + Fn be the Fibonacci sequence. Let p(x) be a polynomial of degree 990 such that p(k) = Fk for k = 992, 993, ... , 1982. Show that p(1983) = F1983 - 1.
Solution
Solution by Alexandre Thiéry
We show first that mC0 Fn + mC1 Fn+1 + mC2 Fn+2 + ... + mCm Fn+m = Fn+2m, where aCb is the binomial coefficient. This is a simple induction on m. For m = 1 it is immediate. Suppose it is true for m. Then ∑0m+1 m+1Ci Fn+i = Fn + ∑1m (mCi + mCi-1)Fn+i + Fn+m+1 = ∑ mCi Fn+i + ∑ mCi Fn+i+1 = ∑ mCi Fn+2+i = Fn+2+2m = Fn+2(m+1), so it is true for m+1.
Now we claim that p(x) = F992 + F991 (x-992) + (1/2!) F990 (x-992)(x-993) + (1/3!) F989 (x-992)(x-993)(x-994) + ... + (1/990!) F2 (x-992)(x-993)...(x-1981). For we have p(992+n) = F992 + nC1 F991 + nC2 F990 + ... + nCn F992-n = F992+n for n = 0, 1, ... , 990.
If we add the term 1/991! F1 (x-992)(x-993)...(x-1982), then we keep the same values at x = 992, 993, ... , 1982 and we get F1983 at x = 1983. Hence p(1983) = F1983 - the value of the extra term at 1983 = F1983 - 1.
© John Scholes
jscholes@kalva.demon.co.uk
24 Nov 2003
Last corrected/updated 24 Nov 03