If S_1=1,S_2=8 and S_n=S_n-1+2S_n-2 whenever n≥2. Show that S_n=3⋅2n−1+2(−1)n for all n≥1.

You can try to show this by induction:

• According to the given closed form, we have , which agrees with the initial value S₁ = 1.

• Assume the closed form is correct for all n up to n = k. In particular, we assume

and

We want to then use this assumption to show the closed form is correct for n = k + 1, or

From the given recurrence, we know

so that

which is what we needed. QED