Fibonacci sequence and the Principle of Mathematical Induction

Question

Consider the Fibonacci sequence, $F_n$. Prove that $2 ~\vert~ F_n$ if and only if $3 ~\vert~ n$, using the principle of mathematical induction.

I know that I have to prove two implications here. Looking at the first implication (if $2 ~\vert~ F_n$, then $3 ~\vert~ n$) , I am a little confused as to how my base case would look: is it valid to say that $F_1=1$ is not divisible by $2$ and $n=1$ is not divisible by $3$ making the statement true for $n=1$?

Answer 1

Note: this statement is true when using the following convention that $F_1 = 1, F_2 = 1, F_{n+2} = F_{n+1}+F_n$ (instead of the other common convention where $F_0 = 1, F_1=1$)

In particular, this will require what is known as strong induction (keeping track of multiple entries at a time instead of only the previous one)

To prove the forward direction that if $2|F_n$ then $3|n$, it is equivalent to prove its contrapositive: if $3\nmid n$ then $2\nmid F_n$.

We may as well prove the other direction at the same time (since the proofs in this case in fact are identical).

Note that: $F_1 = 1$ and $F_2 = 1$ satisfies both conditions.

Assume for our induction hypothesis that $F_{k} \equiv \begin{cases} 1\mod 2 & \text{for}~3\nmid k\\ 0\mod 2 & \text{for}~3\mid k\end{cases}$ for all $k\leq n$

Then for $n+1$, you have three cases: $\begin{cases} n+1\equiv 0\mod 3\\ n+1\equiv 1\mod 3\\ n+1\equiv 2\mod 3\end{cases}$

• First case: $n+1\equiv 0\mod 3$. Then that implies that $n$ and $n-1$ are both not divisible by 3. By induction hypothesis then, $F_n\equiv 1\mod 2$ and $F_{n-1}\equiv 1\mod 2$. So, $F_{n+1} = F_n + F_{n-1} \equiv 1 + 1 \equiv 0\mod 2$ (thus proving the backwards direction).

• Second case: $n+1\equiv 1\mod 3$. Then that implies that $n\equiv 0\mod 3$ and $n-1$ is not divisible by 3. By induction hypothesis then, $F_n\equiv 0\mod 2$ and $F_{n-1}\equiv 1\mod 2$. So, $F_{n+1}=F_n+F_{n-1}\equiv 0+ 1\equiv 1\mod 2$.

• Third case: $n+1\equiv 2\mod 3$. Then that implies that $n-1\equiv 0\mod 3$ and $n$ is not divisible by 3. By induction hypothesis then, $F_{n-1}\equiv 0\mod 2$ and $F_{n}\equiv 1\mod 2$. So, $F_{n+1} = F_n + F_{n-1} \equiv 1+ 0\equiv 1\mod 2$.

As any integer that is not a multiple of 3 will fall into either the second or third cases above, the forward direction is also proven.

Answer 2

you may be able to negotiate the tricky logic by a device such as the following. i shall just describe one version of the set-up, leaving you to finish the proof yourself if you find the notation helpful

let $T$ be the three-dimensional integer lattice whose elements are $(p,q,r)$, and define a subset $F \subset T$ by: $$ F = \{(p,q,r) | (p \equiv_2 1) \land (q \equiv_2 1) \land (r\equiv_20)\} $$ now define the following boolean function on the positive integers: $\mathfrak{F}(n) = $true if $(F_{3n+1},F_{3n+2},F_{3(n+1)}) \in F$ and false otherwise.

since the first three terms $F_1,F_2,$ and $F_3$ are $1,1,2$ then we have $(1,1,2) \in F$ so $\mathfrak{F}(0)$ is true. suppose now that $\mathfrak{F}(k)$ is true for all $k \lt n$...

Answer 3

$$f_{n+3}=f_{n+2}+f_{n+1}=f_{n+1}+f_n+f_{n+1}=2f_{n+1}+f_n$$

Since $2f_{n+1}$ is even, you get $f_{n+3}$ is even if and only if $f_n$ is even.

The statement follows now by induction : Check $P(1), P(2), P(3)$ and prove $P(n) \Rightarrow P(n+3)$.

Answer 4

Here again is my answer, this time written with no LaTeX in the hopes that it will circumvent the display issues the question asker is having with her Apple device.

Note: this statement is true when using the following convention that F(1) = 1, F(2) = 1, F(n+2) = F(n+1)+F(n) (instead of the other common convention where F(0) = 1, F(1)=1)

In particular, this will require what is known as strong induction (keeping track of multiple entries at a time instead of only the previous one)

To prove the forward direction that if 2|F(n) then 3|n, it is equivalent to prove its contrapositive: if 3 doesn't divide n then 2 doesn't divide F(n).

We may as well prove the other direction at the same time (since the proofs in this case in fact are identical).

Note that: F(1) = 1 and F(2) = 1 satisfies both conditions.

Assume for our induction hypothesis that F(k) = 1 mod 2 when 3 doesn't divide k, 0 mod 2 when 3|k for all k

Then for n+1, you have three cases: Either n+1 is equivalent to 0 mod 3, 1 mod 3, or 2 mod 3.

First case: n+1 = 0 mod 3. Then that implies that n and n-1 are both not divisible by 3. By induction hypothesis then, F(n) = 1 mod 2 and F(n-1) = 1 mod 2. So, F(n+1) = F(n) + F(n-1) = (1 + 1) mod 2 = 0 mod 2 (thus proving the backwards direction).

Second case: n+1 = 1 mod 3. Then that implies that n = 0 mod 3 and n-1 is not divisible by 3. By induction hypothesis then, F(n) = 0 mod 2 and F(n-1) = 1 mod 2. So, F(n+1)=F(n)+F(n-1) = (0 + 1) mod 2 = 1 mod 2.

Third case: n+1 = 2 mod 3. Then that implies that n-1 = 0 mod 3 and n is not divisible by 3. By induction hypothesis then, F(n-1) = 0 mod 2 and F(n)= 1 mod 2. So, F(n+1) = F(n) + F(n-1) = (1 + 0) mod 2 = 1 mod 2.

As any integer that is not a multiple of 3 will fall into either the second or third cases above, the forward direction is also proven.

Answer 5

As with many inductions, the proof is easier if we strengthen the induction hypothesis. To see how, we examine the parity of the sequence, i.e. its values mod $2.\,$ It appears to have period $\,3$

$$ {\rm mod}\ 2\!:\,\ f_n \equiv \overbrace{0,\,1,\,1},\overbrace{\,0,1,1},\,\ldots$$

If we can prove the this periodicity holds for all integers then that will yield the result, since it implies that $\,f_n\,$ is even iff $\,3\mid n.\,$ To prove this periodicity by induction it is convenient to split-up the sequence into its cycles $\,g_n := (f_{3n},\, f_{3n+1},f_{3n+2})\ {\rm mod}\ 2,\,$ i.e. each element is taken mod $\,2.\,$ Then the periodicity is equivalent to the constancy of this sequence $\,g_{n+1}\equiv g_n.\,$ This is easily proved by induction using the recurrence for the $\,f_i\,$ and modular arithmetic.

$\qquad\qquad {\rm mod}\ 2\!:\,\ f_{3n+1}\equiv \color{#0a0}1,\ f_{3n+2}\equiv \color{#0a0}1\,\Rightarrow\, f_{3n+3}\equiv \color{}1+\color{}1\equiv \color{#c00}0$

$\qquad\qquad{\rm mod}\ 2\!:\,\ f_{3n+2}\equiv 1,\ f_{3n+3}\equiv 0\,\Rightarrow\, f_{3n+4}\equiv 1+0\equiv\color{#c00} 1$

$\qquad\qquad{\rm mod}\ 2\!:\,\ f_{3n+3}\equiv 0,\ f_{3n+4}\equiv 1\,\Rightarrow\, f_{3n+5}\equiv 1+0\equiv\color{#c00} 1$

This proves the induction step $\ g_n \ \equiv\ (\color{#0a0}0,\color{#0a0}1,\color{#0a0}1)\,\Rightarrow\,g_{n+1}\equiv (\color{#c00}0,\color{#c00}1,\color{#c00}1)$

The base case: $\ g_0 = (f_0,f_1,f_2)\equiv (0,1,1)\ $ is clear, so the induction is complete.