# Proof: Fibonacci Sequence (2 parts)

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.

• 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... – Erick Wong Nov 22 '15 at 7:02

## 1 Answer

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