# Math induction: Fibonacci Numbers

• Apr 11th 2010, 03:53 PM
firebio
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.

• Apr 11th 2010, 04:33 PM
Bacterius
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.
• Apr 11th 2010, 06:34 PM
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.
• Apr 11th 2010, 08:29 PM
firebio
Quote:

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
• Apr 12th 2010, 01:16 PM
MATNTRNG
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...
• Apr 12th 2010, 03:06 PM
Quote:

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!