Show that $$\sum _{k=1}^n\:k\left(n-1\right)^{k-1}\begin{pmatrix}n\\ k\end{pmatrix}=n^n.$$

So far I've done: \begin{align*} \sum _{k=1}^n\:\left(n-1\right)^{k-1}\frac{n!}{\left(k-1\right)!\left(n-k\right)!} &=\ \sum _{k=1}^n\:n\left(n-1\right)^{k-1}\begin{pmatrix}n-1\\ k-1\end{pmatrix}\\ &= \sum _{k=1}^n\:2^{n-1}\cdot n\left(n-1\right)^{k-1} \\ &= n2^{n-1}\cdot \sum _{k=1}^n\:\left(n-1\right)^{k-1}. \end{align*} And got stuck in here, though it doesn't seem to be close to the correct answer ($\ n^n$) anyway... Could I get some hints on how to get this one done? Thank you. *looked for this a while, hopefully it's not a duplicate

  • $\begingroup$ Where does $2^{n-1}$ come from? $\endgroup$ – Lord Shark the Unknown Aug 19 '17 at 9:42
  • $\begingroup$ The sum of all combinations n-1,k-1. $\endgroup$ – Alexander Aug 19 '17 at 9:47
  • 1
    $\begingroup$ @Alexander you seem to be forgetting that $$\sum (a\cdot b) \neq \left( \sum a \right) \cdot \left( \sum b \right)$$ $\endgroup$ – user12345 Aug 19 '17 at 10:16
  • $\begingroup$ @userSeventeen you're right, thanks for letting me know about the mistake $\endgroup$ – Alexander Aug 19 '17 at 10:37

You are very near to the full solution.

After setting $j=k-1$, by the Binomial Theorem we obtain $$\sum _{k=1}^n\:k\left(n-1\right)^{k-1}\binom{n}{k}= n\sum _{k=1}^n\left(n-1\right)^{k-1}\binom{n-1}{k-1}\\=n\sum _{j=0}^{n-1}\binom{n-1}{j}\left(n-1\right)^{j}1^{n-1-j}=n((n-1)+1)^{n-1}=n^n.$$

  • $\begingroup$ I don't get the second to last "=". Could you please expend on that? $\endgroup$ – Alexander Aug 19 '17 at 9:59
  • $\begingroup$ By binomial theorem $n^{n-1}(a+b)^{n-1}=\sum _{j=0}^{n-1}\binom{n-1}{j}a^jb^{n-1-j}$ with $a=n-1$ and $b=1$. $\endgroup$ – Robert Z Aug 19 '17 at 10:01
  • $\begingroup$ I see it now, thank you. $\endgroup$ – Alexander Aug 19 '17 at 10:02
  • $\begingroup$ @Alexander Well done!! $\endgroup$ – Robert Z Aug 19 '17 at 10:03

You get $$n\sum_{k=1}^n(n-1)^{k-1}\binom{n-1}{k-1} =n\sum_{j=0}^{n-1}(n-1)^j\binom{n-1}{j} =n\sum_{j=0}^{n-1}\binom{n-1}{j}x^j$$ where $x=n-1$ and I made the substitution $j=k-1$. Can you see where to go from here?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.