Prove that
$$(2m-1)^m=\sum_{j=1}^m(2j-1)C^m_j(2m-1)^{m-j},$$ where $C^m_j$ denotes binomial coefficient.
I tried induction but got nowhere. I guess some simple binomial coefficient identity will do the trick, but I cannot think of any.
Thanks in advance
On
I just came across this nine year old question and thought I'd provide another approach:
$$
\begin{align}
&\sum_{j=1}^m(2j-1)\binom{m}{j}(2m-1)^{m-j}\\
&=\sum_{j=1}^m2j\binom{m}{j}(2m-1)^{m-j}-\sum_{j=1}^m\binom{m}{j}(2m-1)^{m-j}\tag1\\
&=2m\sum_{j=1}^m\binom{m-1}{j-1}(2m-1)^{m-j}-\sum_{j=0}^m\binom{m}{j}(2m-1)^{m-j}+(2m-1)^m\tag2\\[3pt]
&=2m(2m)^{m-1}-(2m)^m+(2m-1)^m\tag3\\[12pt]
&=(2m-1)^m\tag4
\end{align}
$$
Explanation:
$\text{(1):}$ split the sum as the difference of two sums
$\text{(2):}$ apply $j\binom{m}{j}=m\binom{m-1}{j-1}$ to the first sum
$\phantom{\text{(1):}}$ add and subtract the $j=0$ term of the second sum
$\text{(3):}$ Binomial Theorem
$\text{(4):}$ simplify
Let me typeset this as follows: $$ (2n-1)^n = \sum_{k=1}^n {n\choose k} (2k-1) (2n-1)^{n-k}.$$ Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that $$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$ i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$ In the present case we have $$ A(z) = \sum_{k\ge 1} (2k-1) \frac{z^k}{k!} = 1 + (2z-1) \exp(z)$$ and $$B(z) = \sum_{k\ge 0} (2n-1)^k \frac{z^k}{k!} = \exp(z(2n-1)).$$ The product of these two is $$Q(z) = \exp(z(2n-1)) + (2z-1) \exp(2nz).$$ Extracting coefficients we have $$ n! [z^n] Q(z) = n! \frac{(2n-1)^n}{n!} + n! 2 \frac{(2n)^{n-1}}{(n-1)!} - n! \frac{(2n)^n}{n!}.$$ This is $$ (2n-1)^n + 2n (2n)^{n-1} - (2n)^n = (2n-1)^n.$$ QED.