# Thread: Fibonacci sequence induction proof

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

2. "One of my questions is how do I express the fact that the answer is a even number mathematically?" Let n = 2k

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