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? 
 A: Let $T(n) = f(n) + n + 2$ i.e. $f(n) = T(n) - n -2$. Hence, we get
$$
\begin{align}
T(n) - n -2 & = n + 2 \left(T(n-1) - (n-1) -2 \right)\\
& = n + 2 T(n-1) - 2n -2\\
& = 2 T(n-1) -n - 2\\
T(n) & = 2T(n-1)
\end{align}
$$
Hence, we get that $T(n) = 2^{n-1} T(1)$ where $T(1) = f(1) + 1 + 2 = 4$. Hence, $T(n) = 2^{n+1}$.
Hence, $$f(n) = 2^{n+1} - n - 2.$$
EDIT: The motivation for choosing $T(n)$ is as follows. From the form of the recurrence, it is evident that at each step the function $f(N)$, roughly doubles. However, there are some lower order terms apart from doubling. The motivation is to rewrite $f(n)$ in terms of some other function which will exactly double at each step. This is typically done by adding and subtracting lower order terms from both sides.
A: 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$.
A: Let $f(n) = 2^n \cdot g(n)$, then $2^n \cdot g(n) = n + 2^n \cdot g(n-1)$, which is $g(n) - g(n-1) = n \cdot 2^{-n}$. Therefore $g(n) = g_0 + \sum_{k=0}^n k \cdot 2^{-k}$. The initial condition implies $g_0 = \frac{1}{2}$, thus
$$
   f(n) = 2^n \cdot g(n) = 2^{n-1} + \sum_{k=0}^n k \cdot 2^{n-k}
$$ 
