Determine which Fibonacci numbers are even

Question

(a) Determine which Fibonacci numbers are even. Use a form of mathematical induction to prove your conjecture.
(b) Determine which Fibonacci numbers are divisible by 3. Use a form of mathematical induction to prove your conjecture

I understand that for part a that all multiples of 3 of n are even. So F(0),F(3),F(6)... I just don't understand how to prove it.

For part B it is the same thing except multiples of 4

Please help, thank you!

Answer 1

Part A:

Base case: $F(0) = 0$, 0 is even. $F(3) = 2$, 2 is even.

Inductive Hypothesis: Assume $F(k)$ is even for some arbitrary positive integer $k$ that is divisible by 3.

Want to prove: That $F(k+3)$ is even given the inductive hypothesis.

\begin{align*} F(k+3) &= F(k+2) + F(k+1)\\ &= F(k+1) + F(k) + F(k+1)\\ &= F(k) + 2 F(k+1) \end{align*}

We know by our hypothesis that $F(k)$ is even. We also know that $F(k+1)$ is an integer, so $2 F(k+1)$ is necessarily even by properties of integers. And because the sum of two even integers is also even, it follows that $F(k+3)$ is even. This holds for any arbitrary positive integer $k$ that is divisible by 3, hence we've proved that $F(m)$ is even for all positive integers $m$ divisible by 3.

Part B:

Base case: $F(0) = 0$, 0 is a multiple of 3. $F(4) = 3$, 3 is a multiple of 3.

Inductive Hypothesis: Assume $F(k)$ is a multiple of 3 for some arbitrary positive integer $k$ that is divisible by 4.

Want to prove: That $F(k+4)$ is a multiple of 3 given the inductive hypothesis.

\begin{align*} F(k+4) &= F(k+3) + F(k+2)\\ &= F(k+2) + F(k+1) + F(k+1) + F(k)\\ &= F(k+1) + F(k) + F(k+1) + F(k+1) + F(k)\\ &= 2 F(k) + 3 F(k + 1) \end{align*}

By our hypothesis, $F(k)$ is a multiple of 3, so $2 F(k)$ must also be a multiple of 3. Furthermore, we know that $F(k+1)$ is some integer, so $3 F(k+1)$ must also be multiple of 3. Hence their sum, $F(k+4)$ must also be a multiple of 3.

Answer 2

Hint: You can look at the first few terms of the sequence modulo $n$, and then conclude a pattern (because each term is based upon the previous two). The first few terms of the Fibonacci sequence modulo $2$ are

$1,1,0,1,1,0,1,1,0,1,1,0,\ldots$

The first few terms of the Fibonacci sequence modulo $3$ are

$1,1,2,0,2,2,1,0,1,1,2,0,\ldots$

Now how can you formalize this argument using induction?

Another hint: you may want multiple base cases.

Answer 3

1,1,2,3,5,8 . . . an even number and an odd number added together is odd, an odd number plus and odd number is even.

Answer 4

Instead of trying to write proofs of three things --- that it's even when the index is a multiple of $3$, odd when it's $1$ more than that, and odd when it's two more than that --- write just one proof that covers all three.

Modulo $2$ you start with $1,1,0$. You've added the two $1$s to get $0$.

Then add $1$ and $0$ to get $1$: ${}\qquad 1,1,0,1$.

Then add $0$ and $1$ to get $1$: ${}\qquad 1,1,0,1,1$,

Then add those last two $1$s to get $0$: ${}\qquad 1,1,0,1,1,0$.

So if a sequence of three consecutive terms is $1,1,0$, then the next sequence of three consecutive terms is $1,1,0$.