How to derive this Combinatorial identity

Question

I was in my Combinatorics class the other day, and at some point in a problem, we needed to know $$\sum_{n=1}^{m} n 2^n.$$ Someone in class looked it up and proved what it was by induction, but I was wondering how we can derive what th actual identity is.

Answer 1

$$\sum_{n=1}^{m}x^n=\frac{x^{m+1}-1}{x-1}-1$$ differentiate both sides to get $$\sum_{n=1}^{m}nx^{n-1}=\frac{mx^{m+1}-(m+1)x^m+1}{(x-1)^2}$$

multiply by $x$ on both sides to finally get

$$\sum_{n=1}^{m}nx^{n}=\frac{mx^{m+2}-(m+1)x^{m+1}+x}{(x-1)^2}$$

now let $x=2$. This , then, yields:

$$\sum_{n=1}^{m}n2^n=m2^{m+2}-(m+1)2^{m+1}+2$$

Answer 2

you know that $$\sum_{i=0}^n x^i=\frac{x^{n+1}-1}{x-1}$$ for $x\neq 1$. Derive both sides so that \begin{align} \sum_{i=1}^n ix^i=x\sum_{i=0}^n ix^{i-1}&=x\left(\frac{(n+1)x^n(x-1)-(x^{n+1}-1)}{(x-1)^2}\right) \\ &=x\left(\frac{nx^{n+1}-(n+1)x^{n}+1}{(x-1)^2}\right) \end{align} Set $x=2$. So $\sum_{i\le n}i2^i=2(n2^{n+1}-(n+1)2^n+1)=2((n-1)2^n+1).$

Answer 3

We know that $$\sum_{n=0}^m x^n = \frac{x^{m+1}-1}{x-1}$$. If we differentiate then multiply both sides by x, we should get an expression. Plug in 2