<s>[INST] Find a closed term for $f(n) = n + 2 f(n-1)$, $f(1)=1$ I cannot help myself, but I don't get the closed term for: $f(n) = n + 2 f(n-1)$, where f(1) = 1. I tried to find the pattern when looking at some iterations, and I think I see the pattern very clearly:
$...(6 + 2 ( 5 + 2 ( 4 + 2 (  3 +2 ( 2 \cdot 1 ) ) ) ) ... )$
It's always n, reduced by the iteration plus two times the next iteration.
Any hints or what construct I should use to find the term? 
 [/INST] Just for fun, here is a solution using generating functions.
Let $F(x)=\sum_{n=1}^\infty f(n)x^n$.  Then,
$$\begin{align*}
F(x)&=\left(\sum_{n=2}^\infty (n+2f(n-1))x^n\right)+x\\
&=\left(\frac{x}{(1-x)^2}-x+2x\sum_{n=1}^\infty f(n)x^n\right)+x\\
&=\frac{x}{(1-x)^2}+2xF(x)
\end{align*}$$
So,
$$F(x)=\frac{x}{(1-x)^2(1-2x)}=\frac{1}{x-1}-\frac{1}{(1-x)^2}+2\left(\frac{1}{1-2x}\right)$$
where the far right hand side is the partial fraction decomposition.
Now,
$$\frac{1}{x-1}=-\sum_{n=0}^\infty x^n$$
$$\frac{1}{(1-x)^2}=\sum_{n=0}^\infty (n+1)x^n$$
$$2\left(\frac{1}{1-2x}\right)=2\sum_{n=0}^\infty (2x)^n$$
Hence,
$$F(x)=\sum_{n=0}^\infty (-1-(n+1)+2^{n+1})x^n$$
So, since the coefficient of $x^n$ is $f(n)$, we get $f(n)=2^{n+1}-n-2$.
</s>