Part a) Prove or Disprove: There are only finitely many even Fibonacci numbers.

I think I want to disprove this, as I know that every 3rd Fibonacci number is even, and thus there will be infinitely many even Fibonacci numbers. I am having trouble deciding how to technically prove this. Perhaps induction.

Part b) Prove or Disprove: For all $n\geq1$, we have $F_n \leq 2^n$

I think I want to prove this, and I am thinking that I will have to use induction, but again, I don't know what the structure will be for the cases.

Perhaps my base case will be $F_1, F_2, F_3$ satisfy the claim, and my inductive hypothesis will be $F_{n-1} + F_{n-2} \leq 2^n$ implies $F_n+F_{n-1}\leq 2^{n+1}$. Maybe I can rewrite $2^{n+1}=4^n$

I'm unsure how to algebraically manipulate this statement.

Any help/suggestions/hints would be greatly appreciated.

  • 2
    $\begingroup$ Hint: if there are finitely many even Fibonacci numbers then there is a largest one, $F_m$. Then $F_{m+1}$ and $F_{m+2}$ are both odd... $\endgroup$ – Erick Wong Nov 22 '15 at 7:02

For the first one, we have $F_0=0$ and $F_1 = 1$ with $F_n=F_{n-1}+F_{n-2}$

Keep in mind that in arithmetic we have that $E+E=E$, $E+O=O$ and $O+O=E$ with $O$ being some odd number and $E$ being an even number. If there are finitely many even numbers that means that at some $M$ we have that for all $n>M$ that $F_n$ is odd, but then we have that $F_{n+2}=F_{n+1}+F_n$ which are two odd numbers added together, which makes $F_{n+2}$ even, hence the statement is false.

Second one, induction works quite fine. $$F_0=0\leq 2^0=1$$ Base case done, now assume that $F_n\leq 2^n$ then we have that $$F_{n+1}=F_{n}+F_{n-1}\leq 2F_n\leq 2\cdot 2^n = 2^{n+1}$$ And we're done


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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