6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ have you tried proving this with induction? $\endgroup$ – 123 Nov 11 '14 at 5:08
  • $\begingroup$ 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. $\endgroup$ – Tahir Imanov Jan 22 '15 at 7:24
  • $\begingroup$ If you are still unable to do it, just post what have you done so far. And I will post rest. $\endgroup$ – Tahir Imanov Jan 23 '15 at 10:26
2
$\begingroup$

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$

| cite | improve this answer | |
$\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.