<s>[INST] Find the closed solution of $s_{n} = 3s_{n-1} + 2^{n-2} - 1$ Find the closed solution of $s_{n} = 3s_{n-1} + 2^{n-2} - 1$ if $s_1 = 0, s_2 = 0, s_3 = 1$
I have attempted to use $p_n = c2^{n-2} - d$ [where $h_n = A(3)^n$, but to no avail] - i ended up with $c=-1$ and $d=-\frac{1}{2}$, which is incorrect.
Any help is appreciated! Thanks.
Edit: solution I require is $\frac{1}{2} (3^{n-1}+1-2^n)$
Edit2: Solutions to the homogeneous equation would be of the form $h_n = A(\alpha)^n + B(\beta)^n$, and $p_n$ will exist such that $s_n = h_n + p_n$
 [/INST] A general technique is taught by Wilf's "generatingfunctionology". Define $S(z) = \sum_{n \ge 0} s_n z^n$ and write ($s_0$ you get from the recurrence "backwards", mostly for not having to mess around with indices):
$$
s_{n + 1} = 3 s_n + 2^{n - 1} - 1 \qquad s_0 = \frac{1}{6}
$$
Multiply the recurrence by $z^n$, add over $n \ge 0$ to get:
$$
\begin{align*}
\frac{S(z) - s_0}{z} 
  &= 3 S(z) + \frac{1}{2} \sum_{n \ge 0} 2^n z^n - \sum_{n \ge 0} z^n \\
  &= 3 S(z) + \frac{1}{2} \frac{1}{1 - 2 z} - \frac{1}{1 - z}
\end{align*}
$$
Solving for $S(z)$ and expanding in partial fractions:
$$
S(z) 
   = \frac{1}{6} \frac{1}{1 - 3 z} 
       - \frac{1}{2} \frac{1}{1 - 2 z}
       + \frac{1}{2} \frac{1}{1 - z}
$$
Everything in sight is geometric series:
$$
s_n = \frac{1}{6} \cdot 3^n - \frac{1}{2} \cdot 2^n + \frac{1}{2}
    = \frac{1}{2} \left( 3^{n - 1} - 2^{n - 1} + 1 \right)
$$
</s>