Question

Prove that F(n)<2^n where F(n) is the nth Fibonacci number. Tried using strong induction, and failed. Am I doing something wrong?

Answer 1

\(f(1) = 1 < 2^1\) and \(f(2) = 1 < 2^2 \). So it holds for \( n ≤ 2\) .

Answer 2

My attempt:
Base cases:
f(1)=1<2
f(2)=1<4

Inductive Step:
Inductive hypothesis is: For all positive integers j less than or equal to k, f(j)<2^j.
f(k+1)=f(k)+f(k-1)
<2^k+2^(k-1)
=3*2^(k-1)

But since 4*2^(k-1)>3*2^(k-1), I can't proceed.

Answer 3

Let it holds for all \( n = k \)

Then \( f(k+1) = f(k) + f(k-1) < 2^k + 2^{(k -1)} < 2^k + 2^k =2^{(k+1)} \)

Answer 4

Note: \(2^k \gt 2^{(k-1)}\).

Answer 5

Oh yeah. Forgot about that. Thanks!

Answer 6

Glad to help :)