Question

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.

Answer 1

You can try to show this by induction:

• According to the given closed form, we have $S_1=3\times2^{1-1}+2(-1)^1=3-2=1$, 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

$S_{k-1}=3\times2^{(k-1)-1}+2(-1)^{k-1}=3\times2^{k-2}+2(-1)^{k-1}$

and

$S_k=3\times2^{k-1}+2(-1)^k$

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

$S_{k+1}=3\times2^{(k+1)-1}+2(-1)^{k+1}=3\times2^k+2(-1)^{k+1}$

From the given recurrence, we know

$S_{k+1}=S_k+2S_{k-1}$

so that

$S_{k+1}=3\times2^{k-1}+2(-1)^k + 2\left(3\times2^{k-2}+2(-1)^{k-1}\right)$

$S_{k+1}=3\times2^{k-1}+2(-1)^k + 3\times2^{k-1}+4(-1)^{k-1}$

$S_{k+1}=2\times3\times2^{k-1}+(-1)^k\left(2+4(-1)^{-1}\right)$

$S_{k+1}=3\times2^k-2(-1)^k$

$S_{k+1}=3\times2^k+2(-1)(-1)^k$

$\boxed{S_{k+1}=3\times2^k+2(-1)^{k+1}}$

which is what we needed. QED