<s>[INST] Single Solution for this Recurrence: $a(n)=3^n-a(n-1)+1$ I've solved this recurrence using the iteration method for even and odd values of $n$, but I cannot seem to find a singular explicit function that solves this recurrence for all values of $n$.
The recurrence is
$$a(n) =
\begin{cases}
1,  & \text{if $n=0$} \\
3^n-a(n-1)+1, & \text{otherwise}
\end{cases}$$
 [/INST] Let $A(x)=\sum_{n \ge 0} a_n x^n$ be the ordinary generating function. The recurrence and initial condition imply that
\begin{align}
A(x) 
&= a_0 x^0 + \sum_{n \ge 1} a_n x^n \\
&= 1 + \sum_{n \ge 1} (3^n - a_{n-1} + 1) x^n \\
&= 1 + \sum_{n \ge 1} (3x)^n - x \sum_{n \ge 1} a_{n-1} x^{n-1} + \sum_{n \ge 1} x^n \\
&= 1 + \frac{3x}{1-3x} - x A(x) + \frac{x}{1-x},
\end{align}
so
\begin{align}
A(x) 
&= \frac{1 + \frac{3x}{1-3x} + \frac{x}{1-x}}{1+x} \\
&= \frac{1 - 3x^2}{(1-x)(1+x)(1-3x)} \\
&= \frac{1/2}{1-x} - \frac{1/4}{1+x} + \frac{3/4}{1-3x} \\
&= \frac{1}{2}\sum_{n\ge 0} x^n - \frac{1}{4}\sum_{n\ge 0} (-x)^n + \frac{3}{4}\sum_{n\ge 0} (3x)^n \\
&= \sum_{n\ge 0} \left(\frac{1}{2} - \frac{1}{4} (-1)^n + \frac{3}{4} 3^n\right)x^n,
\end{align}
which immediately yields
$$a_n = \frac{2-(-1)^n+3^{n+1}}{4}.$$
</s>