fibonacci sequence induction with recurrence function

Question

$$f(n) = \begin{cases} 1 & \text{when } n = 1 \\ 1 & \text{when } n = 2 \\ f(n-1) + f(n-2) & \text{when } n \geq 3 . \end{cases} $$ For any natural number $j$, show that the Fibonacci number $f(5j)$ is divisible by $5$, using mathematical induction.

So all I have is that I should probably just use $f(5j)$ and $f(5j +1)$ to get $f(5j + 5)$?

Answer 1

Look at the fibonnaci numbers mod $5$. We get $$\begin{array}{c|c} n & f(n) \mod 5 \\ \hline 1 & 1\\ 2 & 1 \\ 3& 2 \\ 4 & 3 \\ 5 & 0 \\ 6 & 3 \\ 7 & 3 \\ 8 & 1 \\ 9 & 4 \\ 10 & 0 \end{array}$$

Thus we see the pattern that for $f(5j + 1) \equiv f(5 j + 2) \mod 5$, $f(5j + 3) + f(5j + 4) \equiv 0 \mod 5$ and $f(5j) \equiv 0 \mod 5$. This is easy to prove using induction.

Answer 2

Base case is trivial. Suppose that $f(5k)$ is divisible by $5$ for some $k \geq 1$. Then \begin{align} f(5(k+1)) &= f(5k + 5)\\ &= f(5k + 4) + f(5k + 3)\\ &= (f(5k + 3) + f(5k + 2)) + (f(5k + 2) + f(5k + 1))\\ &= f(5k + 3) + 2f(5k + 2) + f(5k + 1)\\ &= (f(5k + 2) + f(5k + 1)) + 2(f(5k) + f(5k + 1)) + f(5k + 1)\\ &= (2f(5k + 1) + f(5k)) + 2f(5k) + 2f(5k + 1) + f(5k + 1)\\ &= 5f(5k + 1) + 3f(5k) \end{align} Clearly $5|5f(5k + 1)$ and since $5 | f(5k)$ we also have $5 | 3f(5k)$ which implies that $5|(5f(5k+1) + 3f(5k)) = f(5(k+1))$ as required.

Answer 3

You can write \begin{align} f(n+2)&=f(n+1)+f(n)\\[6px] f(n+3)&=f(n+2)+f(n+1)\\&=2f(n+1)+f(n)\\[6px] f(n+4)&=f(n+3)+f(n+2)\\&=2f(n+1)+f(n)+f(n+1)+f(n)\\&=3f(n+1)+2f(n)\\[6px] f(n+5)&=f(n+4)+f(n+3)\\&=3f(n+1)+2f(n)+2f(n+1)+f(n)\\&=5f(n+1)+3f(n) \end{align} Set $$ g(j)=f(5j) $$ You want to prove that $5\mid g(j)$.

The case $j=1$ is trivial, because $g(1)=f(5)=5$; if the statement holds for $j$, then $$ g(j+1)=f(5(j+1))=f(5j+5)=5f(5j+1)+3f(5j)=5f(5j+1)+3g(j) $$ and you're done.

Note that, more generally, for $k>0$, $$ f(n+k)=f(k)f(n+1)+f(k-1)f(n) $$ (where we use $f(0)=0$). The case $k=1$ is trivial. Then, assuming the statement holds for $k$ (and every $n$), we have \begin{align} f(n+k+1)&=f(n+k)+f(n-1+k)\\ &=f(k)f(n+1)+f(k-1)f(n)+f(k)f(n)+f(k-1)f(n-1)\\ &=f(k)f(n+1)+f(k)f(n)+f(k-1)f(n+1)\\ &=f(k+1)f(n+1)+f(k)f(n) \end{align} as required. (The case when $n=0$ is obvious, so we can assume $n>0$.)