How can we prove this identity: $$\sum _{k=1}^{n-1} \binom{n-1}{k} k^{k-1} (n-k)^{n-k-1}=n^{n-1}-n^{n-2}$$ A friend of mine gave me this problem several days ago. At first sight, the form of the summand may imply binomial theorem, but I haven't figured out the right way. Another possible way is to transform the sum into integration, however, the term $k^k$ does not seem to suit some famous integral representations. Therefore I'm kind of stuck and would like you to give some suggestions. Thank you.
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment