2
$\begingroup$

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.

$\endgroup$
1
  • 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$ Commented Nov 22, 2015 at 7:02

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.