# Fibonacci numbers is defined by the recurrence relation $F_{n+2} = F_{n+1} + F_n$, prove by induction

Question: $F_0 = 0, F_1 = 1$,Prove by induction on $n$ that, for $n\ge 0$, $F_n$ is even if $n$ is a multiple of $3$

Base Case: Let $n = 1$, Substituting the value into the equation $F_{1+2} = F_{1+1} + F_{1} = F_{2} + F_{1} = F_{1} + F_{0} + F_{1} = 1 + 0 + 1 = 2$ Thus, the equation holds true for the first multiple of three.

Induction Hypothesis: Considering a value $k+2$ that is some arbitrary multiple of 3 and return even for the equation.And $n = k$

$F_{k+2} = F_{k+1} + F_{k}$,

Induction Step: To prove the equation holds true for $n = k+3$, that $k+5$ is all some odd number(Fact: Adding $2$ to any odd number gives odd number),

$F_{k+5} = F_{k+4} + F_{k+3}$,

$RHS = F_{k+4} + F_{k+2} + F_{k+1}$ (From Induction Hypothesis)

How do i get further to this proof...

Here is the question, is my argument true so far? How do i proceed further to this proof?

PS: My prof havn't agreed to my proof initiation. It will be good to give some detail explanation. So I can argue back, if needed

PSS:Please no answers, Just help me(If possible)

• If $k+2$ is a multiple of $3$ then is $k+3$ a multiple of 3? No, right? So start off the induction step by $k+5$. – rookie Feb 18 '17 at 17:29
• @stud_iisc Thank you for the revert. Very valid point. I have amended my solution. – Smit Feb 18 '17 at 17:42
• Again. If $k+3$ is a multiple of $3$ then is $k+5$ a multiple of $3$? No, right? With the current induction hypothesis you need to prove that $F_{k+6}$ is even. – rookie Feb 18 '17 at 17:53
• @stud_iisc made the change. – Smit Feb 18 '17 at 18:04

## 2 Answers

Hint: Apply recurrence equation to $F_{k+4}$ once in $F_{k+5} = F_{k+4} + F_{k+3}$ and you'll be able to prove the required.

• Thank you. I have added the solution as a answer, It will be great you could check if the proof is FINALLY correct. thanks agn. – Smit Feb 18 '17 at 18:27

Base Case: Let $n = 1$, Substituting the value into the equation $F_{1+2} = F_{1+1} + F_{1} = F_{2} + F_{1} = F_{1} + F_{0} + F_{1} = 1 + 0 + 1 = 2$ Thus, the equation holds true for the first multiple of three.

Induction Hypothesis: Considering a value $k+2$ that is some arbitrary multiple of 3 and return even for the equation.And $n = k$

$F_{k+2} = F_{k+1} + F_{k}$,

Induction Step: To prove the equation holds true for $n = k+3$, that $k+5$ is all some odd number(Fact: Adding $2$ to any odd number gives odd number),

$F_{k+5} = F_{k+4} + F_{k+3}$,

$RHS = F_{k+4} + F_{k+3}$

$F_{k+4} = F_{k+3} + F_{k+2}$ By Recurrence relation of $F_{n+2}$

Applying the above relation to the RHS, we get:

$RHS = F_{k+3} + F_{k+2} + F_{k+3}$

$= 2.F_{k+3} + F_{k+2}$

Since, multiplying any number with 2 will result in even and $F_{k+2}$ is even based on Induction Hypothesis.

Hence, the equation holds true for all the odd $n$ will result even.

@stud_iisc Thanks for your help!

• Glad to be of help. But the statement "Hence, the equation holds true for all the odd n will result even", is this true? The question is to prove that $F_n$ is even for all $n$ which is a multiple of $3$, which is exactly what you proved via mathematical induction. :) – rookie Feb 19 '17 at 6:09