Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
OEIS: oeis.org/… (I made some misleading comment before, ignore it) –  sdcvvc Dec 9 '11 at 21:48
add comment

3 Answers 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.

share|improve this answer
    
I find this approach more clearly –  Mahoni Dec 9 '11 at 22:09
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.