0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Jack, we posted our answers pretty much at the same time and although they are a bit different they are similar. If you think my answer is redundant, let me know and I'll erase it. $\endgroup$ – Hamed Jun 21 '18 at 21:45
  • $\begingroup$ @Hamed: I was going to write you the same. Our approaches are indeed very similar, just presented in a slightly different way. I guess it is no big deal to keep both answers, I am going to turn mine into CW. $\endgroup$ – Jack D'Aurizio Jun 21 '18 at 21:47
  • $\begingroup$ it would be helpful the end, thanks $\endgroup$ – Steven Jun 21 '18 at 22:07
2
$\begingroup$

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

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