Math induction anyone...?

Question

I came up with an explicit formula of: f(n) = 5*2^(n-1) - 3 as a solution to the recursive sequence: f(n) = 2f(n-1) + 3 for all integers n >= 2 and f(1) = 2. Is there a way to use mathematical induction to verify the "correctness" of my explicit formula?

Answer 1

Yes, in fact induction is an optimal method for proving the correctness of solutions to recursive functions. You need to do two things: first, prove that the formula is correct for n=1, and second, prove that if it is correct for n, then it is also correct for n+1. Then it will follow that the formula is correct for all n. Let us check these conditions:

f(1) = 5*2^(1-1) - 3 = 5*2^0 - 3 = 5-3 = 2 ✓

Suppose f(n) = 5*2^(n-1) - 3. Then by the recurrence relation f(n+1) = 2f(n) + 3 = 2*(5*2^(n-1) - 3) + 3 = 5*2^n - 6 + 3 = 5*2^((n+1)-1) - 3, so the formula also holds for n+1. ✓

Thus by induction, f(n) = 5*2^(n-1) - 3 for all n