1
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – rookie Feb 18 '17 at 17:29
  • $\begingroup$ @stud_iisc Thank you for the revert. Very valid point. I have amended my solution. $\endgroup$ – Smit Feb 18 '17 at 17:42
  • 1
    $\begingroup$ 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. $\endgroup$ – rookie Feb 18 '17 at 17:53
  • $\begingroup$ @stud_iisc made the change. $\endgroup$ – Smit Feb 18 '17 at 18:04
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Smit Feb 18 '17 at 18:27
1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. :) $\endgroup$ – rookie Feb 19 '17 at 6:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.