# 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?

-
OEIS: oeis.org/… (I made some misleading comment before, ignore it) –  sdcvvc Dec 9 '11 at 21:48

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.

-
I find this approach more clearly –  Mahoni Dec 9 '11 at 22:09

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

-

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

-
And what's the reason you could use the assumption $f(n) = 2^n \cdot g(n)$? –  Mahoni Dec 9 '11 at 21:50
@Mahoni. $f(n) = 2^n \cdot 2^{-n} f(n)$ for all $n \in \mathbb{N}^+$, right? –  Salvo Tringali Dec 9 '11 at 21:52
@SalvoTringali Yes, I see this now –  Mahoni Dec 9 '11 at 21:59