# 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

• 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

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.

• 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