Given the following:
$$(1)\quad\quad \sum_{k=1}^n(k-1){n \choose k-1} + \sum_{k=1}^n {n\choose k -1} = \sum_{k=0}^{n-1}k{n\choose k} + \sum_{k=0}^{n-1}{n\choose k}$$
I am trying to understand how it goes from the LHS to the RHS.
My approach so far, given the first sum summand of the LHS, we have, and taking from the concept here
$$(2)\quad\quad \sum_{k=1}^n(k-1){n \choose k-1}$$
Let $k = m + 1$, then eq (2) becomes
$$(3) \quad\quad \sum_{m=0}^nm{n\choose m}$$
Now we let $l = n +1$, the eq (3) becomes
$$(4)\quad\quad\sum_{m=0}^{l-1}m{l-1\choose m}$$
Change the symbols in (4) to resemble the first first summand of the RHS of (1), namely, let $m = k$ and $l = n$ and substitute we have:
$$(5)\quad\quad\sum_{k=0}^{n-1}k{n-1\choose k}$$
However this does need seem to be the same. Any help to what I am missing would be great!
NOTE: I have done the above process for the 2nd summand of the LHS of (1) to match the 2nd summand of the RHS of (1) and I still get $n-1$ for the top value in the binomial coefficient.
Best Answer
In $(3)$, you are changing $$ \sum_{k=1}^n(k-1)\binom{n}{k-1} $$ via the substitution $k\mapsto m+1$. This leads to $$ \sum_{m=0}^{\color{#C00}{n-1}}m\,\binom{n}{m} $$ The summation is to be taken over $k\in[1,n]$, thus $m+1\in[1,n]$, which is the same as $m\in[0,n-1]$. This is the reason for the change in the limits of summation.
Note that $k$ is bound to the scope of this summation, so it is okay to substitute as is done here. However, $n$ is not bound to the scope of this formula; it could very well be referenced elsewhere. Changing $n$ probably requires a more global substitution affecting more than just this summation. Thus, substituting $l=n+1$ is not a safe thing to do.
As this procedure becomes more familiar, I find it possible to do this without changing the variable name; i.e. substituting $k\mapsto k+1$, thereby reducing the number variable names floating about.