Math induction: Fibonacci Numbers

Printable View

April 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 $a_0 =1, a_1 =1$ and for n >2 by $a_n=a_{n-2}+ a_{n-1}$ .
Show by induction that $a_{3n}$ is even.

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

Thanks in advance
April 11th 2010, 04:33 PM
Bacterius

Hello,
you can use the fact that $\textrm{even} + \textrm{odd} = \textrm{odd}$ and $\textrm{odd} + \textrm{odd} = \textrm{even}$ . This will allow you to set up an induction step.
April 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.
April 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 $a_3n$ is even, should the induction step be $a_3(n-1)$ be even?

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

Thanks
April 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...
April 12th 2010, 03:06 PM
Archie Meade

Quote:

Originally Posted by firebio

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

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

Thanks in advance

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

$a_{3n}=Even$

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

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

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

Proof

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

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

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