Math induction: Fibonacci Numbers

**firebio** · April 11th 2010, 03:53 PM

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

**Bacterius** · April 11th 2010, 04:33 PM

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.

**MATNTRNG** · April 11th 2010, 06:34 PM

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

**firebio** · April 11th 2010, 08:29 PM

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

**MATNTRNG** · April 12th 2010, 01:16 PM

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...

**Archie Meade** · April 12th 2010, 03:06 PM

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!

Thread: Math induction: Fibonacci Numbers

LinkBack

Thread Tools

Display

Math induction: Fibonacci Numbers

Similar Math Help Forum Discussions

[SOLVED] induction problem with fibonacci numbers

Strong induction on Fibonacci numbers

Induction with Fibonacci Numbers

Induction and Fibonacci Numbers

Help with induction for Fibonacci Numbers

Search Tags