# Product of consecutive Fibonacci numbers divisibility

Prove that the product of any $k$ consecutive Fibonacci numbers is divisible by the product of the first $k$ Fibonacci numbers.

We can try to show that for every prime $p$, the power of $p$ appearing in the product $F_1F_2\ldots F_k$ is less than that appearing in $F_{i+1}F_{i+2}\ldots F_{i+k}$. This would be sufficient. But the problem is that the closed form, $F_n=\dfrac{1}{\sqrt{5}}(\varphi^n-(-\varphi)^{-n})$ where $\varphi=\dfrac{1+\sqrt{5}}{2}$, doesn't seem to help much.

• have you tried proving this with induction?
– 123
Nov 11 '14 at 5:08
• You don't need $F_n=\dfrac{1}{\sqrt{5}}(\varphi^n-(-\varphi)^{-n})$ to prove it. Just prove $F_{nm}$ is divisible by $F_n$ (and also $F_m$ ). Then try some examples (first 4, 5, 6 fibonacci numbers and etc.). Then use induction. Jan 22 '15 at 7:24
• If you are still unable to do it, just post what have you done so far. And I will post rest. Jan 23 '15 at 10:26

## 1 Answer

We have $$F_{n+m}=F_nF_{m+1}+F_{n-1}F_{m}$$ Indeed, or $m=0$ the claim is $F_n=F_n\cdot 1+F_{n-1}\cdot 0$; for $m=1$ the claim is $F_{n+1}=F_n\cdot 1+F_{n-1}\cdot 1$; and for larger $m$ the claim follows from adding the corresponding equalities for $m-1$ and $m-2$. Define $$P(i,k):=F_{i+1}\cdot F_{i+2}\cdot\ldots\cdot F_{i+k}.$$ Then we have the identity \begin{align}P(i,k)&=P(i,k-1)F_{i+k}\\&=P(i,k-1)(F_kF_{i+1}+F_{k-1}F_i)\\&=P(i,k-1)F_kF_{i+1}+P(i-1,k)F_{k-1}\end{align} This allows us to show the

Claim. For $k\ge1$, $i\ge1$ we have $P(1,k)\mid P(i,k)$.

Proof. The case $i=1$ is trivial, as i sthe case $k=1$. For all other cases, we use the above identity: If $P(i,k-1)=cP(1,k-1)$ and $P(i-1,k)=dP(1,k)$, then $$P(i,k)=P(i,k-1)F_kF_{i+1}+P(i-1,k)F_{k-1}=(cF_{i+1}+dF_{k-1})P(1,k)$$ as was to be shown. $_\square$