Fibonacci Polynomial

Lemma :

If a polynomial of degree $n$ or less satisfies $P(j)=r^{j}$ for $j=0,1,...,n$ ,then $P(n+1)=r^{n+1}-(r-1)^{n+1}$

Solution I claim $P(x)=\sum_{k=o}^{n}(_{k}^{x})(r-1)^k$

Clearly, $P$ is a polynomial of degree at most $n$ .Since, the binomial coefficients $(_{k}^{j})$ disappear for $k>j$ ,the Binomial Theorem yields $P(j)=\sum_{k=o}^{j}(_{k}^{j})(r-1)^k=r^{j}$

Hence, $P(n+1)=\sum_{k=o}^{n}(_{k}^{n+1})(r-1)^k=r^{n+1}-(r-1)^{n+1}$

Generalization of the Lemma

If $P(k)=r^{k}$ for $k=m,m+1,...,m+n$ ,then $P(m+n+1)=r^{m}(r^{n+1}-(r-1)^{n+1})$ .

Solution Simple! Just let $P(x)=r^{m}\sum_{k=0}^{n}(r-1)^{k}(_{k}^{x})$ and proceed as previous.

Generalization of the Given Problem

If a polynomial $P$ of degree $n$ satisfies $P(k)=F_{k}$ for $k=m,m+1,...,m+n$ then $P(m+n+1)=F_{m+n+1}-F_{m-n-1}$ .

Let $p(k)=\sqrt{5}P(k)$ .By Binet’s Formula, $p(k)=a^k-b^k$ where $a=\frac{1+\sqrt{5}}{2}$ and $b= \frac{1-\sqrt{5}}{2}$ .

By the Generalized lemma $p(m+n+1)=a^{m}(a^{n+1}-(a-1)^{n+1})-b^{m}(b^{n+1}-(b-1)^{n+1})$

Note that, $a-1=\frac{1}{a}$ and $b-1=\frac{1}{b}$ .

Hence, $p(m+n+1)=(a^{m+n+1}-b^{m+n+1})-(a^{m-n-1}-b^{m-n-1})$

So, $P(m+n+1)=F_{m+n+1}-F_{m-n-1}$ .

Hence, $P(29)=P_{15+13+1}-F_{15-13-1}=F_{29}-1=514229-1=514228$ .