2
$\begingroup$

If $F_n$ denotes the $n$-th Fibonacci number ($F_0 = 0, F_1 = 1, F_{n+2} = F_{n+1} + F_n$), show that $5^n$ divides $F_{5^n}$.

$\endgroup$
7
$\begingroup$

Note that $$ \begin{pmatrix}a+b & a \\ a & b\end{pmatrix}^5 = \begin{pmatrix}* & c \\ c & *\end{pmatrix} $$ where $c=5 a (a^4 + 3 a^3 b + 4 a^2 b^2 + 2 a b^3 + b^4)$. Therefore, if $5^n$ divides $a$, then $5^{n+1}$ divides $c$.

Apply this to $$ \begin{pmatrix}1&1\\1&0\end{pmatrix}^n = \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix} $$ for a proof by induction that $5^n$ divides $F_{5^n}$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Now that we have aids like WA, we can dare compute $A^5$ just to see what comes out... $\endgroup$ – lhf Jun 15 '16 at 15:00
  • $\begingroup$ $5$ seems to be very special here: there is no obvious multiple of $k$ in $c$ for $k\ne 5$. $\endgroup$ – lhf Jun 16 '16 at 14:21
  • $\begingroup$ Interesting :-) $\endgroup$ – Jyrki Lahtonen Jun 16 '16 at 18:28

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.