# Thread: Math induction: Fibonacci Numbers

1. ## Math induction: Fibonacci Numbers

The Fibonacci Numbers : 1,1,2,3,5,8,13,21,34... are defined by $\displaystyle a_0 =1, a_1 =1$ and for n >2 by $\displaystyle a_n=a_{n-2}+ a_{n-1}$.
Show by induction that $\displaystyle a_{3n}$ is even.

base case: n=3 is 2, so it is even.
Assume $\displaystyle a_n=a_{n-2}+ a_{n-1}$ is even?
not sure how to do the induction step.

2. Hello,
you can use the fact that $\displaystyle \textrm{even} + \textrm{odd} = \textrm{odd}$ and $\displaystyle \textrm{odd} + \textrm{odd} = \textrm{even}$. This will allow you to set up an induction step.

3. I believe that the inductive step would be a3n is even. You must prove that a3(n+1) which equals a3n+3 is even.

4. Originally Posted by MATNTRNG
I believe that the inductive step would be a3n is even. You must prove that a3(n+1) which equals a3n+3 is even.
If i want to prove $\displaystyle a_3n$ is even, should the induction step be $\displaystyle a_3(n-1)$ be even?

And should i assume that $\displaystyle a_{n-2}$ and $\displaystyle a_{n-1}$ are odd?

Thanks

5. You are assuming that a3n is even as your inductive hypothesis and you want to prove that a3(n+1) is even to complete your proof, i believe. Sorry, I wish I could help you more but I am not sure where to go from here...

6. Originally Posted by firebio
The Fibonacci Numbers : 1,1,2,3,5,8,13,21,34... are defined by $\displaystyle a_0 =1, a_1 =1$ and for n >2 by $\displaystyle a_n=a_{n-2}+ a_{n-1}$.
Show by induction that $\displaystyle a_{3n}$ is even.

base case: n=3 is 2, so it is even.
Assume $\displaystyle a_n=a_{n-2}+ a_{n-1}$ is even?
not sure how to do the induction step.

The Fibonacci sequence, in terms of odd and even is...

OOEOOEOOEOOEOOEOOE.....

This is because the first 2 terms are odd
odd+odd=even=3rd term
odd+even=odd=4th term
even+odd=odd=5th term
odd+odd=even=6th term

The sequence cycles in this way

Hence if

$\displaystyle a_{3n}=Even$

The inductive step is..... does $\displaystyle a_{3n}$ being even cause $\displaystyle a_{3(n+1)}$ to be even ?

$\displaystyle a_{3(n+1)}=a_{3n+3}$

$\displaystyle a_{3n+3}=a_{3n+1}+a_{3n+2}$

Proof

If $\displaystyle a_{3n}$ is even, then both $\displaystyle a_{3n+1}$ and $\displaystyle a_{3n+2}$ must of necessity both be odd.

Hence, as this is true, and $\displaystyle a_{3}$ is even, $\displaystyle a_{3n}$ is even.

The inductive proof is really just basic logic in this case!