<s>[INST] How to prove an identity by induction I am working on the following problem:
$\text{For $n$ $\ge$ 1, Prove the following:}$
$n(1+x)^{n-1} = \sum_{k=1}^{n} k {n\choose k}x^{k-1} $
$\text{Deduce that: } \sum_{k=1}^{n}k{n \choose k}=n2^{n-1} $
I followed the proof by induction as follows:
$\text{Base Case: let n=1 , both RHS and LHS will evaluate to 1}$
$\text{Assume true for n=l. Now consider n=l+1}$
$(l+1)(1+x)^l=\sum_{k=1}^{l+1}k {l+1 \choose k} x^{k-1}$
$(l+1)(\sum_{k=0}^{l} {l \choose k} x^k)=\sum_{k=1}^{l+1}k {l+1 \choose k} x^{k-1}$
After this, I am kinda lost. any ideas on how to continue the proof?
 [/INST] Well,  $(n+1)(1+x)^n = (1+x)\frac{n+1}n\cdot n(1+x)^{n-1}= (1+x)\frac{n+1}n\cdot \sum\limits_{k=1}^nk{n\choose k}x^{k-1}=$
$\frac {n+1}n(\sum\limits_{k=1}^nk{n\choose k}x^{k-1}+ x\sum\limits_{k=1}^nk{n\choose k}x^{k-1})=$
$\frac {n+1}n(\sum\limits_{k=1}^nk{n\choose k}x^{k-1} + \sum\limits_{k=1}^nk{n\choose k}x^{k})=$
$\frac {n+1}n(\sum\limits_{k=1}^nk{n\choose k}x^{k-1} + \sum\limits_{k=2}^{n+1}(k-1){n\choose k-1}x^{k-1})=$
$\frac {n+1}n(1{n\choose 1}x^0 +\sum\limits_{k=2}^n[k{n\choose k}+(k-1){n\choose k-1}]x^{k-1} + n{n\choose n}x^n)=$
$\frac {n+1}n\cdot n + \frac {n+1}n\sum\limits_{k=2}^n[k\frac {n!}{k!(n-k)!}+(k-1)\frac {n!}{(k-1)!(n-k+1)!}]x^{k-1} +\frac {n+1}n\cdot nx^n)=$ ...
$(n+1) + \frac {n+1}n\sum\limits_{k=2}^n[\frac {n!(n-k+1)}{(k-1)!(n-k+1)!}+\frac {n!(k-1)}{(k-1)!(n-k+1)!}]x^{k-1}   + (n+1)x^n =$
$k{n+1\choose k}x^{k-1}|_{k=1} +\frac {n+1}n\sum\limits_{k=2}^n\frac{n!n}{{(k-1)!(n-k+1)!}}x^{k-1} +k{n+1\choose k}x^{k-1}|_{k=n+1}=$
$k{n+1\choose k}x^{k-1}|_{k=1} +\sum\limits_{k=2}^n\frac{(n+1)!}{{(k-1)!(n-k+1)!}}x^{k-1} +k{n+1\choose k}x^{k-1}|_{k=n+1}=$
$k{n+1\choose k}x^{k-1}|_{k=1} +\sum\limits_{k=2}^nk\frac{(n+1)!}{{k!(n-k+1)!}}x^{k-1} +k{n+1\choose k}x^{k-1}|_{k=n+1}=$
$\sum\limits_{k=1}^{n+1}k{n+1\choose k}x^{k-1}$
</s>