Question

Let f be a function of the positive integers such that f(1) = 1 and f(n+1) = f(n) + 2^n for all n>=1. Prove that f(n) = 2^n -1 using the principle of strong induction.

Answer 1

I prove the induction step only, ok? the basic step and the hypothesis step are easy, right?

Answer 2

yes

Answer 3

Assume f(n) = 2^n -1
need prove f(n+1) = 2^(n+1) -1
From \(\color{red}{f(n+1) = f(n) + 2^n}\) , we replace f(n) = 2^n -1
then \(f(n+1) = 2^n -1 + 2^n = 2*2^n -1= 2^{n+1} -1\) done.

Answer 4

Thank you!

Answer 5

np