Fibonacci Sequence - Induction.

[glover_m]

Prove F_n ≤ (7/4)ⁿ 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

 

[HallsofIvy]

Prove F_n ≤ (7/4)ⁿ 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

Well, $(7/4)^{k-1}= (4/7)(7/4)^k$ so $(7/4)^{k-1}+ (7/4)^k= (4/7+ 1)(7/4)^k$. And 4/7+ 1= 11/7= (11/7)(4/7)(7/4)= (44/49)(7/4) and 44/49< 1.