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:
$\displaystyle f_{n} = f_{n-1} + f_{n-2}$
Using induction, prove that $\displaystyle f_{3n}$ is a even number for all $\displaystyle 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:
$\displaystyle f_{n} = f_{n-1} + f_{n-2}$
Using induction, prove that $\displaystyle f_{3n}$ is a even number for all $\displaystyle 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 $\displaystyle F_0=0,\;\;\;F_1=1$

$\displaystyle F_2=Even+Odd=Odd$

$\displaystyle F_3=Odd+Odd=Even$

$\displaystyle F_4=Even+Odd=Odd$

$\displaystyle F_5=Odd+Even=Odd$

$\displaystyle F_6=Odd+Odd=Even$

the pattern is for n=0, 1, 2, 3, 4.... $\displaystyle 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 $\displaystyle F_0$

P(k)

$\displaystyle F_{3n}=Even$

P(k+1)

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

Proof

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

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

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