3
$\begingroup$

I have a seemingly simple question to solve by induction. The question says $F_n$ divides $F_{2n}$ in the Fibonacci sequence. My thoughts on this.

First,since the n-th term of the Fibonacci sequence is given as the sum of the two previous terms, simple induction won't suffice. So I should try composite induction.

That is, supposing that $F_k$ divides $F_{2k}$ for all $k<n$, I must prove $F_{n}$ divides $F_{2n}$. Is this approach valid?

Doesn't seem to work. If I write $F_{2n}=F_{2n-1}+F_{2n-2}$ then by the inductive hypothesis, $F_{n-1}$ divides $F_{2n-2}$ but this does not help me assert that $F_n$ divides $F_{2n}$. Am I doing this wrong?

$\endgroup$
1
4
$\begingroup$

Using $F_{m+n} = F_{n-1}F_m+F_nF_{m+1}$ with $m=n$, we have $$F_{2n} = F_{n-1}F_n+F_nF_{n+1} = F_n\left(F_{n-1}+F_{n+1}\right)$$

So $F_n$ divides $F_{2n}$.

$\endgroup$
9
$\begingroup$

My favorite Fibonacci technique is the matrix formulation, which is well worth knowing and easily proved: $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n= \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$

Then $$ \begin{pmatrix}F_{2n+1}&F_{2n}\\F_{2n}&F_{2n-1}\end{pmatrix} =\begin{pmatrix}1&1\\1&0\end{pmatrix}^{2n} =\begin{pmatrix}1&1\\1&0\end{pmatrix}^{n} \begin{pmatrix}1&1\\1&0\end{pmatrix}^{n} = \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$ Now look at the $(1,2)$ entries and get: $$ F_{2n} = F_n(F_{n+1}+F_{n-1}) $$

$\endgroup$
1
  • $\begingroup$ Thanks, looks impressive. $\endgroup$ – MelaniesWoes Feb 27 '18 at 0:14
6
$\begingroup$

Hint: Try to prove $\gcd(F_m, F_n) = F_{\gcd(m,n)}$ using induction. You might need these intermediate steps:

  1. $\gcd(F_n, F_{n+1}) = 1.$
  2. $F_{m+n}=F_mF_{n+1}+F_{m−1}F_n.$
$\endgroup$
1
  • 3
    $\begingroup$ $F_{m+n}=F_mF_{n+1}+F_{m−1}F_n$ is enough: just take $m=n$. $\endgroup$ – lhf Feb 26 '18 at 23:50
4
$\begingroup$

$n$th term of the Fibonacci sequence is given by$\sqrt{5}F_n=\varphi^n-(-\varphi)^{-n},$ where $\varphi=\dfrac{1+\sqrt 5}{2}.$ Now write $F_{2n}$ and factor it as a difference of two squares to reach the desire result.

Even though my proof goes without induction, if you really need, you can use induction to derive the Binet's formula.

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