Let $F_n$ denote the $n^{th}$ Fibonacci number, given by $F_1=F_2=1$ and $F_n=F_{n-1}+F_{n-2}$. Then for fixed $p$ show that $$\sum_{k=1}^{n} \binom {n}k F_p^k F_{p-1}^{n-k}F_k = F_{p n}$$
Is there a way that we can solve this using recursion. I know that the Fibonacci number sequence depends on recursion to operate. I tried to use the generating function of the Fibonacci, without any success. Any help? Thank you
On
You can use $F_n=(\phi^n-\psi^n)/(\phi-\psi)$, where $\phi=(1+\sqrt{5})/2$ and $\psi=(1-\sqrt{5})/2$, to show that $$ \begin{aligned} \sum_{k=1}^n {n\choose k} F_p^k F_{p-1}^{n-k} F_k&= \frac{(\phi F_p+F_{p-1})^n-(\psi F_p+F_{p-1})^n}{\phi-\psi} \end{aligned} $$ (replace the formula for $F_k$ in the sum). Then use the formula again (having in mind $\phi\psi=-1$) to conclude $\phi F_p+F_{p-1}=\phi^p$ and $\psi F_p+F_{p-1}=\psi^p$.
Fibonacci numbers are well-known to have an exponential growth, and for a fixed couple of constants $\alpha,\beta$, by letting $\varphi=\frac{1+\sqrt{5}}{2}$ and $\overline{\varphi}=\frac{1-\sqrt{5}}{2}$, we have $$ \sum_{k=0}^{n}\binom{n}{k}\alpha^k \beta^{n-k} F_k = \frac{(\alpha\varphi+\beta)^n-(\alpha\overline{\varphi}+\beta)^n}{\sqrt{5}}\tag{1}$$ due to the binomial theorem. It is reasonable to expect that the solution to the given problem is not very far from being a consequence of a similar identity. Indeed $$ F_{pn}=\frac{\varphi^{pn}-\overline{\varphi}^{pn}}{\sqrt{5}}=F_p\sum_{k=0}^{n-1}\varphi^{pk}\overline{\varphi}^{p(n-1-k)} \tag{2}$$ simply follows from $(a^n-b^n)=(a-b)(a^{n-1}+a^{n-2}b+\ldots+a b^{n-2}+b^{n-1})$.
Are you able to turn the RHS of $(2)$ into the LHS of the original identity, by exploiting $\varphi\overline{\varphi}=-1$, $\varphi+\overline{\varphi}=1$, $F_m = \frac{1}{\sqrt{5}}\left(\varphi^m-\overline{\varphi}^m\right)$ and the binomial theorem?