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

Question

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)

Answer 1

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.

Answer 2

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!