# How to derive this Combinatorial identity [duplicate]

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.

• This is why induction is a really terrible method of proof: it tells you that something is correct but rarely why it's correct. – Trevor Gunn Mar 9 '18 at 16:38
• You do need some trick (in general a standard one for each particular kind of analogous problem; if you know it you can solve, if you don't know it you can't ). – Piquito Mar 9 '18 at 16:55
• It is simply an Arithmetico geometric progression. Refer to brilliant.org/wiki/arithmetic-geometric-progression for more information – Rohan Shinde Mar 9 '18 at 17:20

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

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

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