Prove Fibonacci identity using mathematical induction

[issacnewton]

Homework Statement

Prove that $n$th Fibanacci number $F_n$ is even if and only if $3|n$

Relevant Equations

Mathematical Induction

Let $P(n)$ be the statement that

$$ F_n \text{ is even} \iff (3 \mid n) $$

Now, my base cases are $n=1,2,3$. For $n=1$, statement I have to prove is

$$ F_1 \text{ is even} \iff (3 \mid 1) $$

But since $F_1 = 1$ (Hence $F_1$ not even) and $3 \nmid 1$, the above statement is vacuously true. Now, for $n=2$, statement is

$$ F_2 \text{ is even} \iff (3 \mid 2) $$

But, since $F_2 = 1$ (Hence $F_2$ not even) and $3 \nmid 2$, the above statement is vacuously true. Lastly, for $n=3$, statement is

$$ F_3 \text{ is even} \iff (3 \mid 3) $$

Since $F_3=2$, we have $F_3$ as even and $3 \mid 3$. Since both antecedent and consequent are true, the biconditional is true. So, base cases are true. Now, let $k \geqslant 3$ be an arbitrary in $\mathbb{N}$. And suppose that $P(m)$ is true for $1 \leqslant m \leqslant k$. i.e.

$$ F_m \text{ is even} \iff (3 \mid m) $$

for $1 \leqslant m \leqslant k$. I have to prove that $P(k+1)$ is true. I have to prove that

$$ F_{k+1} \text{ is even} \iff (3 \mid k+1) $$

Since this is biconditional statement, I will first prove forward direction

$$ F_{k+1} \text{ is even} \to (3 \mid k+1) $$

Suppose that $F_{k+1}$ is even. Now, $F_{k+1} = F_k + F_{k-1} = 2 F_{k-1} + F_{k-2}$. Using this, I must have $F_{k-2}$ as even. Since $k \geqslant 3$, it implies $1 \leqslant k-2 \leqslant k$. Now, I can use the inductive hypothesis and conclude that $3 \mid (k-2)$. This means that $k-2 = 3 \alpha$ for some $\alpha \in \mathbb{Z}$. It follows that $k +1 = 3 (\alpha + 1)$ and $3 \mid (k+1)$.
This proves the forward direction. Now, I have to prove the reverse direction

$$ (3 \mid k+1) \to F_{k+1} \text{ is even} $$

Suppose $3 \mid (k+1)$. I will try to prove this with contradiction, so assume the opposite of consequent. Hence suppose that $F_{k+1}$ is odd. Since $F_{k+1} = 2 F_{k-1} + F_{k-2}$, it must be true that $F_{k-2}$ is odd. As before, since $1 \leqslant k-2 \leqslant k$, using contrapositive of inductive hypothesis

$$ (F_{k-2} \text{ is odd}) \to (3 \nmid k-2)$$

Hence, it must be true that $3 \nmid (k-2)$. But, as $3 \mid (k+1)$, I have $(k+1) = 3 \alpha$ and $(k-2) = 3(\alpha -1)$. This means that $3 \mid (k-2)$. But this is a contradiction. So, initial assumption that $F_{k+1}$ is odd, is wrong. Hence $F_{k+1}$ is even. This proves the reverse direction. Hence

$$ F_{k+1} \text{ is even} \iff (3 \mid k+1) $$

So, $P(k+1)$ is true. Using strong induction, this means that $P(n)$ is true for all $n \in \mathbb{N}$.

Is this a correct proof ?
Thanks $\smile$

 

[fresh_42]

It looks ok but I got a bit lost in the many cases you considered. You derived the essential formula
$$
F_{k+1}=2F_{k-1}+F_{k-2}
$$
which means that $F_{k+1}\equiv F_{k-2}\pmod{2}$ and $F_{k-2} \equiv 0 \pmod{2} \Longleftrightarrow 3\,|\,(k-2)$ by induction hypothesis. Both statements together are
$$
F_{k+1}\equiv F_{k-2}\equiv 0 \pmod{2} \Longleftrightarrow 3\,|\,(k-2).
$$
Remains to show that $3\,|\,(k-2) \Longleftrightarrow 3\,|\,((k-2)+3) \Longleftrightarrow 3\,|\,(k+1).$

You had all the ingredients. I just cleaned your room a little bit.

 

[issacnewton]

I should learn to be more succinct. Thanks

 

[Gavran]

The proof can be get by using $m = 3n$, $m = 3n+1$ and $m = 3n+2$, where $n \in \mathbb {N_0}$.

$m = 3n$
The base case: $n = 0$, $F_m = F_{3n} = F_0 = 0$.
The induction step: Suppose that for $n = k$, where $k \gt 0$, $F_m = F_{3n} = F_{3k}$ is even. Now it must be proved that for $n = k+1$, $F_m = F_{3n} = F_{3(k+1)}$ is even too.

The same approach can be applied for $m = 3n+1$ and for $m = 3n+2$, when $F_m$ are odd numbers.

 

[PeroK]

Alternatively, let $P(n)$ be that $F_{3n}$ is even, and $F_{3n+1}$ and $F_{3n+2}$ are odd. Starting with $n =0$.