0
$\begingroup$

How can I prove that $F_{2n}$ is divisible by $F_n$ in the Fibonacci sequence?

$\endgroup$
8
  • $\begingroup$ Do you mean " is divisible by"? $\endgroup$ – Michael McGovern Feb 27 '18 at 22:23
  • $\begingroup$ This question, or variants, seems to be coming up a lot over the past few days. Anyway, here is a reference. $\endgroup$ – lulu Feb 27 '18 at 22:23
  • 1
    $\begingroup$ In fact, $F_{2n} = F_n (F_{n+1} + F_{n-1})$. (My favorite proof of this: if $A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$, then $A^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}$. Now write $A^{2n} = (A^n)^2$ and compare the two sides.) $\endgroup$ – Daniel Schepler Feb 27 '18 at 22:29
  • $\begingroup$ Since $(x^n-y^n)\mid (x^{2n}-y^{2n})$, it is a straightforward consequence of the closed formula for Fibonacci numbers. Actually $F_{2n}=L_n F_n$ where $L_n$ is the $n$-th Lucas number. $\endgroup$ – Jack D'Aurizio Feb 27 '18 at 22:30
  • $\begingroup$ @JackD'Aurizio I think it's a bit more complex than that, since $x$ and $y$ are irrational. You would still be left with showing $x^n + y^n$ is an integer. $\endgroup$ – Daniel Schepler Feb 27 '18 at 22:32

Browse other questions tagged or ask your own question.