0

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.

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

2 Answers2

9

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

mathlove
  • 139,939
1

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

serendipity0217
  • 187