# Fibonacci sequence induction proof

• October 1st 2010, 08:46 AM
masterk
Fibonacci sequence induction proof
Hi!
I have a assignment involving the fibonacci sequence, and I wonder if anyone could give me a hand with it:
The fibonacci sequence is given as:
$f_{n} = f_{n-1} + f_{n-2}$
Using induction, prove that $f_{3n}$ is a even number for all $n \in \mathbb{N}$

I have been struggeling with this for some days now. One of my questions is how do I express the fact that the answer is a even number mathematically? Do I even need to?

Any help would be much appreciated!
Martin
• October 1st 2010, 08:52 AM
wonderboy1953
"One of my questions is how do I express the fact that the answer is a even number mathematically?" Let n = 2k
• October 1st 2010, 10:22 AM
Quote:

Originally Posted by masterk
Hi!
I have a assignment involving the fibonacci sequence, and I wonder if anyone could give me a hand with it:
The fibonacci sequence is given as:
$f_{n} = f_{n-1} + f_{n-2}$
Using induction, prove that $f_{3n}$ is a even number for all $n \in \mathbb{N}$

I have been struggeling with this for some days now. One of my questions is how do I express the fact that the answer is a even number mathematically? Do I even need to?

Any help would be much appreciated!
Martin

With $F_0=0,\;\;\;F_1=1$

$F_2=Even+Odd=Odd$

$F_3=Odd+Odd=Even$

$F_4=Even+Odd=Odd$

$F_5=Odd+Even=Odd$

$F_6=Odd+Odd=Even$

the pattern is for n=0, 1, 2, 3, 4.... $F_{3n}=Even$

Since the first 2 terms are even and odd, we never encounter two successive even numbers in the Fibonacci sequence.

The Fibonacci sequence pattern is EOOEOOEOOEOOEOO starting at $F_0$

P(k)

$F_{3n}=Even$

P(k+1)

$F_{3(n+1)}=Even$

Proof

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

every Even term is followed by 2 Odd terms, hence $F_{3n+3}$ is the 3rd term after $F_{3n}$

and so it is Even if $F_{3n}$ is Even.