http://www.artofproblemsolving.com/Forum/viewtopic.php?f=37&t=337&hilit

amparvardi wrote: Let $(F_n)_{n\geq 1} $ be the Fibonacci sequence $F_1 = F_2 = 1, F_{n+2} = F_{n+1} + F_n (n \geq 1),$ and $P(x)$ the polynomial of degree $990$ satisfying \[ P(k) = F_k, \qquad \text{ for } k = 992, . . . , 1982.\] Prove that $P(1983) = F_{1983} - 1.$ So $P(x)=\sum_{i=992}^{1982}\frac{\prod_{k=992,k\ne i}^{1982}(x-k)}{\prod_{k=992,k\ne i}^{1982}(i-k)}F_i$ And $P(1983)=\sum_{i=992}^{1982}\frac{\prod_{k=992,k\ne i}^{1982}(1983-k)}{\prod_{k=992,k\ne i}^{1982}(i-k)}F_i$ $P(1983)=\sum_{i=992}^{1982}\frac{991!(-1)^{1982-i}F_i}{(1983-i)(i-992)!(1982-i)!}$ $P(1983)=\sum_{i=0}^{990}\frac{991!(-1)^{i}F_{i+992}}{i!(991-i)!}$ Let then $F_k=au^n+bv^n$ with $u=\frac{1+\sqrt 5}2$ and $v=\frac{1-\sqrt 5}2$ such that $uv=-1$ and $u+v=1$ $P(1983)=\sum_{i=0}^{990}\frac{991!(-1)^{i}(au^{i+992}+bv^{i+992})}{i!(991-i)!}$ $P(1983)=au^{992}\sum_{i=0}^{990}\binom{991}{i}(-u)^i$ $+bv^{992}\sum_{i=0}^{990}\binom{991}{i}(-v)^i$ $P(1983)=au^{992}((1-u)^{991}+u^{991})$ $+bv^{992}((1-v)^{991}+v^{991})$ $P(1983)=au^{992}(v^{991}+u^{991})$ $+bv^{992}(u^{991}+v^{991})$ $P(1983)=au^{1983}+bv^{1983}-au-bv$ $\boxed{P(1983)=F_{1983}-1}$ Q.E.D.

Finite differences make this pretty simple. Let $P_0(x) = P(x)$ and $P_k(x) = P_{k-1}(x+1) - P_{k-1}(x)$. Using induction and the Fibonacci recurrence we quickly deduce that $P_k(n) = F_{n-k}$, when $992 \leq n \leq 1982 - n$. But since $P_0(x)$ is degree $990$, $P_{990}(x)$ is the constant polynomial, with $P_{990}(992) = F_2 = 1$. Then $P_{990}(993) = 2 = F_3 - 1$. Now doing induction on $k$ in the reverse direction, we get that $P_k(1983-k) = F_{1983-2k} - 1$, for $0 \leq k \leq 990$. In particular $P_0(1983) = P(1983) = F_{1983} - 1$, as desired.

I found this generalisation in a book. Can someone provide a proof of this? It is in the Lagrange interpolation section of the book. Let $P(x)$ be a polynomial of degree $n$ such that $P(k)=F_k\forall k=n+2,n+3,\ldots ,2n+2$. Prove that $P(2n+3)=F_{2n+3}-1\forall n\geq 0$

Claim: $\binom{m}{m} F_n + \binom{m}{m-1} F_{n+1} + \binom{m}{m-2} F_{n+2} + ... + \binom{m}{0} F_{n+m} = F_{n+2m}$ We proceed by induction. The base case of $m=1$ is trivial: $$F_n + F_{n+1} = F_{n+2}$$We assume it works for $m$ and claim that it will work for $m+1$. Then, we assume: $$\binom{m}{m} F_n + \binom{m}{m-1} F_{n+1} + \binom{m}{m-2} F_{n+2} + ... + \binom{m}{0} F_{n+m} = F_{n+2m}$$Then, $$\binom{m+1}{m+1} F_n + \binom{m+1}{m} F_{n+1} + \binom{m+1}{m-1} F_{n+2} + ... + \binom{m+1}{0} F_{n+m+1} = x$$Subtracting, we see that: $$x-F_{n+2m} = F_{n+1} + \binom{m}{m}F_{n+1} + \binom{m}{m-1}F_{n+2} + \binom{m}{m-2}F_{n+3} + ... + \binom{m}{1}F_{n+m} + \binom{m}{0}F_{n+m+1} = F_{n+2m+1}$$Therefore, it follows that $x = F_{n+2m}+ F_{n+2m+1} = F_{n+2m+2}$. Claim:$P(x+992) = F_{992} + F_{991} \binom{x}{1} + F_{990}\binom{x}{2} + F_{989} \binom{x}{3} + ... + F_2 \binom{x}{990}$ is one such valid polynomial. By the identity above, it follows that for all $x < 990$, $P(x+992) = F_{x+992}$. Furthermore, $$P(991 + 992) = F_{992} + F_{991} \binom{991}{1} + F_{990}\binom{991}{2} + F_{989} \binom{991}{3} + ... + F_2 \binom{991}{990}$$so $$P(991+992) + 1 = F_{992} + F_{991} \binom{991}{1} + F_{990}\binom{991}{2} + F_{989} \binom{991}{3} + ... + F_2 \binom{991}{990} + F_1 \binom{991}{991}$$which clearly by the identity is $F_{1983}$. The desired result follows. $\blacksquare$

i just used lagrange interpolation

Using Lagrange interpolation$,$ $P(x)=\sum\limits_{k=992}^{1982}\prod\limits_{j=992,j\neq k}^{1982}\frac{x-j}{k-j}\cdot F_k.$ Define $\alpha =\frac{\sqrt 5+1}2,\beta =\frac{\sqrt 5-1}2.$ Let $x=1983,$ then $$\begin{aligned}f(1983) &=\sum\limits_{k=992}^{1982}\prod\limits_{j=992,j\neq k}^{1982}\frac{1983-j}{k-j}\cdot F_k\\ &=\sum\limits_{k=992}^{1982}\frac{991!\cdot F_k}{(-1)^{1982-k}\cdot (k-992)!\cdot (1982-k)!\cdot (1983-k)}.\\ &=\sum\limits_{j=0}^{990}\frac{991!\cdot F_{j+992}}{j!\cdot (991-j)!\cdot (-1)^{990-j}}\\ &=\sum\limits_{j=0}^{990}\dbinom{991}{j}\cdot (-1)^j\cdot F_{j+992}\\ &=\sum\limits_{j=0}^{990}\dbinom{991}{j}\cdot (-1)^j\cdot\frac{\alpha ^{j+992}-\beta ^{j+992}}{\sqrt 5}\\ &=\frac{\alpha ^{992}}{\sqrt 5}\sum\limits_{j=0}^{990}\dbinom{991}{j}\cdot (-1)^j\cdot\alpha ^{j}-\frac{\beta ^{992}}{\sqrt 5}\sum\limits_{j=0}^{990}\dbinom{991}{j}\cdot (-1)^j\cdot\beta ^{j}\\ &=\frac{\alpha ^{992}}{\sqrt 5}\left(\alpha ^{991}+\beta ^{991}\right)-\frac{\beta ^{992}}{\sqrt 5}\left(\alpha ^{991}+\beta ^{991}\right)\\ &=\frac{1}{\sqrt 5}\left(\alpha ^{1983}-\beta ^{1983}\right)-\frac{1}{\sqrt 5}\cdot\alpha ^{991}\beta ^{991}(\alpha -\beta)\\ &=F_{1983}-1.\blacksquare\end{aligned}$$