The Fibonacci Numbers : 1,1,2,3,5,8,13,21,34... are defined by and for n >2 by .

Show by induction that is even.

base case: n=3 is 2, so it is even.

Assume is even?

not sure how to do the induction step.

Thanks in advance

Printable View

- April 11th 2010, 03:53 PMfirebioMath induction: Fibonacci Numbers
The Fibonacci Numbers : 1,1,2,3,5,8,13,21,34... are defined by and for n >2 by .

Show by induction that is even.

base case: n=3 is 2, so it is even.

Assume is even?

not sure how to do the induction step.

Thanks in advance - April 11th 2010, 04:33 PMBacterius
Hello,

you can use the fact that and . This will allow you to set up an induction step. - April 11th 2010, 06:34 PMMATNTRNG
I believe that the inductive step would be

*a***3n**is even. You must prove that*a***3(n+1)**which equals*a***3n+3**is even. - April 11th 2010, 08:29 PMfirebio
- April 12th 2010, 01:16 PMMATNTRNG
You are assuming that

*a***3n**is even as your inductive hypothesis and you want to prove that*a***3(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 PMArchie Meade
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

The inductive step is..... does being even__cause__to be even ?

**Proof**

If is even, then both and must of necessity both be odd.

Hence, as this is true, and is even, is even.

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