Determine which Fibonacci numbers are even (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!
 A: 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.
A: 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.
A: 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$.
A: 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.
