0
$\begingroup$

I'm trying to do a proof on fibonacci numbers by induction, and I have an answer but I'm not sure its acceptable.

I'm trying to prove $F_n < 2^n$

My base case at 1 is $F_1 = 1; 2^1 = 2$ therefore checks out

My inductive hypothesis: $F_k < 2^k; 1 \le k \le n$

And inductive step: $F_{k+1} < 2^{k+1}$

I know $F_k = F_{k-1} + F_{k-2}$, so I substitute that into my I.S.

$F_k + F_{k-1} < 2^{k+1}$

We know the L.H.S is less than or equal to $2F_k$, and $2^{k+1} = 2^k 2$

we can conclude that $F_k + F_{k-1} < 2^{k+1}$ from the above statement. This is because the above statement is true, and it is shown the L.H.S is less than that of our statement

$\endgroup$
2
  • 2
    $\begingroup$ this is correct $\endgroup$ Commented Apr 6, 2017 at 17:11
  • 2
    $\begingroup$ You also have to check the base case $F_2$, since the Fibonacci sequence is defined by a linear recurrence relation of order $2$. $\endgroup$ Commented Apr 6, 2017 at 17:21

2 Answers 2

Reset to default
1
$\begingroup$

You are right and the proof is correct. Here is how I would write this up to clean up the proof text.

We would like to prove that $$F_n < 2^n \quad \forall n \ge 1.$$ Proceed by Mathematical Induction on $n$.

For the base case, note that $$ F_1 = 1 < 2 = 2^1, $$ hence $F_1 < 2^1$ and the statement holds for $n = 1$.

For the inductive step, assume that the claim is true for all $1 \le k \le n$, and let us prove that $F_{n+1} < 2^{n+1}$.

Notice that $$ \begin{split} F_{n+1} &= F_n + F_{n-1} \quad \text{by the Fibonacci recurrence} \\ &< 2F_n \quad \text{since Fibonacci numbers are an increasing sequence} \\ &< 2 \cdot 2^n \quad \text{by the Inductive Hypothesis} \\ &= 2^{n+1}. \end{split} $$ Hence, $F_{n+1} < 2^{n+1}$ as desired.

Q.E.D.

$\endgroup$
0
$\begingroup$

Correct .. but as @Bernard says you need to check $F_2$ in addition to $F_1$, and I would also spell out this part a bit better:

$F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} < 2^k + 2^ k = 2*2^k = 2^{k+1}$

$\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.