You can try to show this by induction:
• According to the given closed form, we have [tex]S_1=3\times2^{1-1}+2(-1)^1=3-2=1[/tex], 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
[tex]S_{k-1}=3\times2^{(k-1)-1}+2(-1)^{k-1}=3\times2^{k-2}+2(-1)^{k-1}[/tex]
and
[tex]S_k=3\times2^{k-1}+2(-1)^k[/tex]
We want to then use this assumption to show the closed form is correct for n = k + 1, or
[tex]S_{k+1}=3\times2^{(k+1)-1}+2(-1)^{k+1}=3\times2^k+2(-1)^{k+1}[/tex]
From the given recurrence, we know
[tex]S_{k+1}=S_k+2S_{k-1}[/tex]
so that
[tex]S_{k+1}=3\times2^{k-1}+2(-1)^k + 2\left(3\times2^{k-2}+2(-1)^{k-1}\right)[/tex]
[tex]S_{k+1}=3\times2^{k-1}+2(-1)^k + 3\times2^{k-1}+4(-1)^{k-1}[/tex]
[tex]S_{k+1}=2\times3\times2^{k-1}+(-1)^k\left(2+4(-1)^{-1}\right)[/tex]
[tex]S_{k+1}=3\times2^k-2(-1)^k[/tex]
[tex]S_{k+1}=3\times2^k+2(-1)(-1)^k[/tex]
[tex]\boxed{S_{k+1}=3\times2^k+2(-1)^{k+1}}[/tex]
which is what we needed. QED
