Let f₀, f₁, f₂, . . . be the Fibonacci sequence defined as f₀ = 0, f₁ = 1, and for every k > 1, f_k = f_k-1 + f_k-2.

Use induction to prove that for every n ? 0, f_n ? 2^n-1 . Base case should start at f₀ and f₁. For the inductive case of f_k+1 , youll need to use the inductive hypothesis for both k and k ? 1.