Mathematical Induction

Question

The sequence (U_n) is defined by the recurrence relation U_n= U_n-1 + 2ⁿ with u₀ = 5. Prove by mathematical induction that u_n = 3 + 2ⁿ⁺¹ for n >= 0

Answer 1

The base case (n=1), given u₀=5: u₁=u₀+2¹=5+2=7, but the proposed formula for u₁=3+2²=7. The base case is therefore true. (The corresponding series is 5, 7, 11, 19, 35, ...)

Generally, u_n+1=u_n+2ⁿ⁺¹ (given), and u_n=3+2ⁿ⁺¹ (proposed). 

u_n+1-u_n=2ⁿ⁺¹, and (proposed) u_n+1-u_n=(3+2ⁿ⁺²)-(3+2ⁿ⁺¹)=2ⁿ⁺²-2ⁿ⁺¹=2ⁿ⁺¹(2-1)=2ⁿ⁺¹.

Therefore, from the given formula and the proposed formula the difference between consecutive terms is identical, so the proposed formula is correct by induction.