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)
 A: 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!
A: 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.
