Thread: Fibonacci Sequence Proof

Fibonacci Sequence - Induction.
Prove F(n) ≤ (7/4)^n for all n, 0≤n

F(n) = F(n-1) + F(n-2)

Let P(n) be true for some n = k, for 0≤k

Let n = k+1

F(k+1) ≤ (7/4)^(k+1)

LHS: F(k+1) = F(k)+ F(k-1) ≤ F(k-1) + (7/4)^k ≤ (7/4)^(k-1) + (7/4)^k

This last line is where I'm stuck, I feel like either I messed up early on, or I'm missing a way of simplifying this to look like (7/4)^(k+1)

Originally Posted by glover_m

Fibonacci Sequence - Induction.
Prove F(n) ≤ (7/4)^n for all n, 0≤n

F(n) = F(n-1) + F(n-2)

Let P(n) be true for some n = k, for 0≤k

Let n = k+1

F(k+1) ≤ (7/4)^(k+1)

LHS: F(k+1) = F(k)+ F(k-1) ≤ F(k-1) + (7/4)^k ≤ (7/4)^(k-1) + (7/4)^k

This last line is where I'm stuck, I feel like either I messed up early on, or I'm missing a way of simplifying this to look like (7/4)^(k+1)

LHS:
F(k+1) = F(k)+ F(k-1)
≤ (7/4)^(k-1) + (7/4)^k
=(7/4)^(k-1) ( 1+7/4)...................1+7/4=2.75 < (7/4)^2
≤ (7/4)^(k-1)(7/4)^2
=(7/4)^(k+1)

i don't know why it is ≤ instead of <

thanks, was copying over from html so had to edit some things and must have forgot to change that too.

thanks a lot btw