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

## marked as duplicate by N. F. Taussig combinatorics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Mar 9 '18 at 16:58

• 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