21
$\begingroup$

How do I prove the following identity directly?

$$\sum_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$$

I thought about using the binomial theorem for $(x+a)^n$, but got stuck, because I realized that my $x$ and $a$ in this case are dynamic variables. Any hints? Don't give me the answer; I really want to think through this on my own, but a nudge in the correct direction would be awesome. Thanks!

$\endgroup$
8
$\begingroup$
  1. This identity is known as "Abel's Identity". It can be proved by generalizing:

$$\sum_{k} \binom{n}{k} (k+s-n)^{k} (r+n-k)^{n-k-1} = \frac{(r+s)^n}{r}$$ (By plugging $s=n-1,r=1$ we get the original identity.) A nicer way to write it is: $$\sum_{k} \binom{n}{k} (s-k)^{n-k} (r+k)^{k-1} = \frac{(r+s)^n}{r}$$ Sometimes an additional parameter is added: $$\sum_{k} \binom{n}{k} (s-tk)^{n-k} (r+tk)^{k-1} = \frac{(r+s)^n}{r}$$ This generalized identity is much easier to prove.

  1. One more hint: To prove the generalized identity, one can expand $(s-k)^{n-k}$ by the binomial theorem, and change order of summation.
$\endgroup$
  • $\begingroup$ I really like the hint! (+1) $\endgroup$ – Sungjin Kim Apr 6 '13 at 18:39
5
$\begingroup$

Don't give me the answer I really want to think through this on my own, but a nudge in the correct direction would be awesome.

As yee wish; it's yer question after all.

There are the following exponential generating functions:

$$\begin{align*} \frac{-z}{W(-z)(1+W(-z))}&=\sum_{k=0}^\infty\frac{(k-1)^k}{k!}z^k\\ \frac{-W(-z)}{z}&=\sum_{k=0}^\infty\frac{(k+1)^{k-1}}{k!}z^k \end{align*}$$

where $W(z)$ is the Lambert function. (Sometimes, these EGFs are instead expressed in terms of the "tree function" $T(z)=-W(-z)$.) The Maclaurin series for $-W(-z)$ looks like this:

$$-W(-z)=\sum_{k=1}^\infty \frac{k^{k-1}}{k!} z^k$$

which you will have to prove, perhaps by composing two appropriate series.

Now, the OP's identity can be recast as a convolution:

$$\sum_{k=0}^n \frac{(k-1)^k}{k!}\frac{(n-k+1)^{n-k-1}}{(n-k)!}=\frac{n^n}{n!}$$

Switching to the generating function view, the convolution on the left has the generating function

$$\left(\frac{-z}{W(-z)(1+W(-z))}\right)\left(\frac{-W(-z)}{z}\right)=\frac1{1+W(-z)}$$

which means

$$\frac1{1+W(-z)}=1+\sum_{k=1}^\infty\frac{k^k}{k!}z^k$$

Now to prove the validity of this identity, you could start by deriving the formula (and the corresponding series) for the derivative of the Lambert function. Recall the fundamental relation $W(z)\exp(W(z))=z$; use implicit differentiation to derive an expression $W^\prime(z)$ which can then be manipulated to look like $\dfrac1{1+W(-z)}$. Again, the details are left up to you.

$\endgroup$
2
$\begingroup$

A nice proof uses the Lagrange-Bürman inversion formula. Start defining: \begin{equation} C(z) = z e^{C(z)} \end{equation} which gives the expansion: \begin{equation} e^{\alpha C(z)} = \alpha \sum_{n \ge 0} \frac{(\alpha + n)^{n - 1} z^n}{n!} \end{equation} Then you have: \begin{equation} e^{(\alpha + \beta) C(z)} = e^{\alpha C(z)} \cdot e^{\beta C(z)} \end{equation} Expanding and comparing both sides gives Abel's binomial theorem: \begin{equation} (\alpha + \beta) (\alpha + \beta + n)^{n - 1} = \sum_{0 \le k \le n} \binom{n}{k} (\alpha + k)^{k - 1} (\beta + n - k)^{n - k - 1} \end{equation}

$\endgroup$
2
$\begingroup$

As an additional observation I would like to point out that the series expansion of $$e^{\alpha T(z)}$$ where $$T(z) = z \times e^{T(z)}$$ can also be computed with the Cauchy Residue Theorem, which gives a variant of Lagrange Inversion.

We seek to compute $$[z^n] e^{\alpha T(z)} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} e^{\alpha T(z)} \; dz.$$

Put $w=T(z)$ in the functional equation for $T(z)$ to get $$z = w e^{-w} \quad \text{and} \quad dz = e^{-w} - w e^{-w} = (1-w) e^{-w}.$$

Substitute this into the integral to obtain $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{e^{w(n+1)}}{w^{n+1}} e^{\alpha w} e^{-w} (1-w) \; dw.$$ This is $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{e^{w(n+\alpha)}}{w^{n+1}} (1-w) \; dw.$$ Now we can read off the residue at $w=0$ to get $$\frac{(n+\alpha)^n}{n!} - \frac{(n+\alpha)^{n-1}}{(n-1)!} = (n+\alpha) \frac{(n+\alpha)^{n-1}}{n!} - n \frac{(n+\alpha)^{n-1}}{n!} = \alpha \frac{(n+\alpha)^{n-1}}{n!}$$ as quoted in the answer by @vonbrand above.

$\endgroup$
0
$\begingroup$

How you tried induction? First consider, the base case $n=0$. Then show that if it holds for $n$ then this implies that it holds for $n+1$. Another way could be to write $n = (n-k+1)+(k+1)$, and then do the expansion of $n^n$, i.e going the other way.

$\endgroup$
  • 4
    $\begingroup$ Not sure if its that simple. For the first approach, the inductive step looks quite difficult. For the second way, notice that the index dummy variable and your $k$ are really very different entities. $\endgroup$ – Macavity Mar 31 '13 at 9:31
0
$\begingroup$

long ago, I see this problem was solved by $WZ$ methods.

see:http://en.wikipedia.org/wiki/Lambert%27s_W_function

the same problem we have $$\displaystyle\sum_{k=1}^{n-1}C_{n}^{k}k^{k-1}(n-k)^{n-k-1}=2n^{n-2}(n-1)$$

$\endgroup$
  • 2
    $\begingroup$ When you say WZ method do you mean Wilf-Zeilberger Pair? $\endgroup$ – user0987654321 Mar 31 '13 at 16:53

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.