2
$\begingroup$

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?

  • 0
    OEIS: http://oeis.org/search?q=1,4,11,26,57,120,247,502,1013,2036&sort=number&language=english&go=Search (I made some misleading comment before, ignore it)2011-12-09

3 Answers 3

3

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.

  • 0
    I find this approach more clearly2011-12-09
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$.

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

  • 0
    @SalvoTringali Yes, I see this now2011-12-09