Find a closed term for $f(n) = n + 2 f(n-1)$, $f(1)=1$

Question

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?

Answer 1

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} $$

Answer 2

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.

Answer 3

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$.