# solving recurrence relation.

Solve the following recurrence relation $$P(1)=2$$ $$P(n)=2P(n-1)+2^n\cdot n$$ for $n\ge 2$

I know I need to expand to look for a pattern but it's not clicking for me. I don't see the pattern that will simplify this recursive statement. Any help is much appreciated.

• I am not sure I edited the equation correctly (it was not clear). If not tell me!
– Ant
Commented Sep 30, 2014 at 19:04
• For what concerns the problem, have you tried looking here ?en.wikipedia.org/wiki/…
– Ant
Commented Sep 30, 2014 at 19:06
• n2^n on that last part instead of 2n
– Tim
Commented Sep 30, 2014 at 19:09

Dividing the both sides by $2^n$ gives us\begin{align}P(n)=2P(n-1)+n\cdot 2^n&\iff \frac{P(n)}{2^n}=\frac{2P(n-1)}{2^n}+\frac{n\cdot 2^n}{2^n}\\&\iff \frac{P(n)}{2^n}=\frac{P(n-1)}{2^{n-1}}+n\\&\iff Q(n)=Q(n-1)+n\end{align} where $$Q(n)=\frac{P(n)}{2^n}.$$

Hence, since we have $$Q(n+1)-Q(n)=n+1,$$we have, for $n\ge 2$, \begin{align}Q(n)&=Q(1)+\sum_{k=1}^{n-1}(k+1)\\&=\frac{P(1)}{2^1}+\frac{(n-1)n}{2}+(n-1)\\&=\frac{n(n+1)}{2}.\end{align} Note that this holds for $n=1$.

Hence, we have $$P(n)=\frac{n(n+1)}{2}\cdot 2^n=n(n+1)\cdot 2^{n-1}\ \ (n\ge 1).$$

• beautiful solution Commented Sep 30, 2014 at 19:36

first, list $$P(1), P(2), P(3), P(4)$$ to find some pattern:

$$P(1)=2$$

$$P(2)=2P(1)+2^2\times2$$

$$P(3)=2P(2)+2^3\times3=2(2P(1)+2^2\times2)+2^3\times3$$

$$P(4)=2P(3)+2^4\times4=2(2(2P(1)+2^2\times2)+2^3\times3)+2^4\times4$$

the pattern for $$P(n)$$ is there will be $$a-1$$ number of 2 multiplying $$P(1)$$, $$a-2$$ number of 2 multiplying $$(2^2\times2)$$, $$a-3$$ number of 2 multiplying $$(2^3\times3)$$...

Therefore, we can write $$2^{n-1}\times2+2^{n-2}\times2^2\times2+2^{n-3}\times2^3\times3+...+2^{n-n}\times2^n\times n$$

Simplify it, we get $$2^n\times1+2^n\times2+2^n\times3+...+2^n\times n$$.

take out the common factor, $$2^n\times(1+2+3+...+n)$$ which is $$2^n\times\frac{(1+n)n}{2}$$.