Can any one help me in proving the following equality:
$$n^n= \sum_{i=1}^n {n \choose i}\cdot i^{i-1}\cdot (n-i)^{n-i}$$
I tried some different ideas but none of them worked!
[Math] Combinatorial equation
co.combinatorics
Related Solutions
Here is a solution to your warm up problem. It uses a few known elementary identities, and some short inductions for identities I didn't recognize. I also changed your notation slightly from $l$ to $k$ in the internal summations.
Setting $x=2$, the first term vanishes, and we combine the second and third terms as $(B)$ and take the last term as $(A)$.
\begin{align} &\sum_{j=0}^i \binom{n-1-j}{i-j} 2^{j-1} \sum_{k=0}^j (-1)^k \binom{n+1}{k} 2^{i-k-1}(i-k) \tag{A} \\ &\sum_{j=0}^{i-2} \binom{n-1-j}{i-2-j} 2^{j-1} \sum_{k=0}^j (-1)^k \binom{n+1}{k} \left( 2^{i-k} + 2^{i-k-1}(i-2-k)\right) \tag{B} \end{align} Fortunately for us, both are equal to $i\cdot2^{i-2}$ when $i$ is even, and do not depend on $n$. First, we focus on $(A)$. Switch the order of summation to get
\begin{equation} \sum_{k=0}^i (-1)^k \binom{n+1}{k} 2^{i-2}(i-k) \sum_{j=k}^i \binom{n-1-j}{i-j} 2^{j-k} \tag{A} \end{equation}
Then reindex the internal summation, and repeatedly apply the hockey stick identity to show \begin{equation} \sum_{j=0}^{i-k}\binom{n-1-k-j}{i-k-j}2^j = \sum_{j=0}^{i-k}\binom{n-k}{j} \end{equation}
I found it easier to write out by changing variables $a=i-k-j$, $b=i-k$ and $c=n-i-1$, then simplifying $\sum_{a=0}^b \binom{c+a}{c}2^{b-a}$.
$(A)$ naturally splits at the point $i-k$, and since we want to show that the whole thing is $i\cdot2^{i-2}$, we can break it into two pieces and show
\begin{align} \sum_{k=1}^i (-1)^k k\binom{n+1}{k}\sum_{j=0}^{i-k} \binom{n-k}{j} &=0 \tag{A1}\\ \sum_{k=0}^i (-1)^k \binom{n+1}{k} \sum_{j=0}^{i-k} \binom{n-k}{j} &=1 \tag{A2} \end{align}
We can simplify $(A1)$ slightly by incorporating $k$ into the binomial, and ignoring the $n+1$ term that comes out. Switching the order of summations again, we write
\begin{equation} Q(n,i) = \sum_{j=0}^{i-1} \sum_{k=1}^{i-j} (-1)^k \binom{n}{k-1} \binom{n-k}{j} \end{equation}
We will induct on $n$ and $i$ to show that $Q(n,i)=0$ for $i$ even, and $-1$ for $i$ odd. The base cases are easy to check, especially if taking $i=0$ and $i=1$. But first, we need an auxillary identity, which we will also use in $(A2)$.
\begin{equation} P(n,i) = \sum_{j=0}^{i} (-1)^{i-j}\binom{n}{j} \binom{n-1-j}{i-j} \end{equation} We claim that $P(n,i)=1$ for all $n$ and $i$. This is certainly true for $i=0$. We split $\binom{n}{j}$ into two to get an induction:
\begin{align} P(n,i) &= \sum_{j=0}^{i} (-1)^{i-j}\binom{n-1}{j} \binom{n-1-j}{i-j} + \sum_{j=1}^{i} (-1)^{i-j}\binom{n-1}{j-1} \binom{n-1-j}{i-j} \\ &= \sum_{j=0}^{i} (-1)^{i-j}\binom{n-1}{i} \binom{i}{j} + \sum_{j=1}^{i} (-1)^{i-j}\binom{n-1}{j-1} \binom{n-1-j}{i-j} \\ &= \binom{n-1}{i}\sum_{j=0}^{i} (-1)^{i-j}\binom{i}{j} + \sum_{j=0}^{i-1} (-1)^{i-1-j}\binom{n-1}{j} \binom{(n-1)-1-j}{(i-1)-j} \\ &= 0 + P(n-1,i-1) \end{align}
Now we give a similar proof for $Q$. In the fourth to fifth lines, we used the alternating sum of binomial coefficients up to some number. You might be able to give a direct proof if your generatingfunctionology is strong, since these look like convolutions of simple functions, but these proofs seemed easy enough that I didn't bother trying.
\begin{align} Q(n,i) &= \sum_{j=0}^{i-1} \sum_{k=1}^{i-j} (-1)^k \binom{n}{k-1} \binom{n-k}{j} \\ &= \sum_{j=0}^{i-1} \sum_{k=1}^{i-j} (-1)^k \binom{n-1}{k-1} \binom{n-k}{j} + \sum_{j=0}^{i-2} \sum_{k=2}^{i-j} (-1)^k \binom{n-1}{k-2} \binom{n-k}{j} \\ &= \sum_{j=0}^{i-1} \sum_{k=1}^{i-j} (-1)^k \binom{n-1}{j} \binom{n-1-j}{k-1} + \sum_{j=0}^{i-2} \sum_{k=2}^{i-j} (-1)^k \binom{n-1}{k-2} \binom{n-k}{j} \\ &= \sum_{j=0}^{i-1} \binom{n-1}{j} \sum_{k=0}^{i-1-j} (-1)^{k+1} \binom{n-1-j}{k} + \sum_{j=0}^{i-2} \sum_{k=1}^{i-1-j} (-1)^{k+1} \binom{n-1}{k-1} \binom{n-1-k}{j} \\ &= \sum_{j=0}^{i-1} \binom{n-1}{j} (-1)^{i-1-j+1} \binom{n-2-j}{i-1-j} - Q(n-1, i-1) \\ &= -P(n-1,i-1) - Q(n-1, i-1) \end{align}
Now, since our equation $(A1)$ was just $(n+1)Q(n,i)$, and $i$ is even, it's $0$. A similar treatment yields $(A2)$, again using the alternating binomial sum identity near the end:
\begin{align} &\,\sum_{k=0}^i (-1)^k \binom{n+1}{k} \sum_{j=0}^{i-k} \binom{n-k}{j} \\ &= \sum_{j=0}^i \sum_{k=0}^{i-j} (-1)^k \binom{n+1}{k} \binom{n-k}{j} \\ &= \sum_{j=0}^i \sum_{k=0}^{i-j} (-1)^k \binom{n}{k} \binom{n-k}{j} + \sum_{j=0}^i \sum_{k=0}^{i-j} (-1)^k \binom{n}{k-1} \binom{n-k}{j} \\ &= \sum_{j=0}^i \sum_{k=0}^{i-j} (-1)^k \binom{n}{j} \binom{n-j}{k} + Q(n,i) \\ &= \sum_{j=0}^i \binom{n}{j} \sum_{k=0}^{i-j} (-1)^k \binom{n-j}{k} \\ &= \sum_{j=0}^i \binom{n}{j} (-1)^{i-j} \binom{n-1-j}{i-j} \\ &= P(n,i) \end{align}
So we have shown that $(A) = i\cdot2^{i-2}$ for $i$ even. Let's use this for $(B)$, since $i-2$ is also even, we have:
\begin{equation} \sum_{j=0}^{i-2} \binom{n-1-j}{i-2-j} 2^{j-1} \sum_{k=0}^j (-1)^k \binom{n+1}{k} 2^{i-k-3}(i-2-k) = (i-2)2^{i-4} \end{equation} After multiplying both sides by $2^2$, the only place the left side differs from $(B)$ is the extra $-2$ in $(i-2-k)$, and the right side is $2^{i-1}$ smaller than we would like. So we show that
\begin{equation} \sum_{j=0}^{i-2} \binom{n-1-j}{i-2-j} 2^{j-1} \sum_{k=0}^j (-1)^k \binom{n+1}{k} 2^{i-k} = 2^{i-1} \end{equation} Dividing out the factor of $2^{i-1}$ and switching the order of summation, we get
\begin{equation} \sum_{k=0}^{i-2} (-1)^k \binom{n+1}{k} \sum_{j=k}^{i-2} \binom{n-1-j}{i-2-j}2^{j-k} \end{equation} Of course we recognize our hockey stick identity from earlier, so this simplifies to the case of $(A2)$
\begin{equation} \sum_{k=0}^{i-2} (-1)^k \binom{n+1}{k} \sum_{j=0}^{i-2-k} \binom{n-k}{j} =1 \end{equation}
Everything is already contained in OEIS comments for A001864 and A000435 (a remarkable comment is that A000435 is the sequence that started it all: the first sequence in the database!)
We take $n$ labelled vertices, consider all trees on them, and sum up the distances between all pairs of vertices (each distance counted twice).
One way to do it is the following: this sum is the number of 5-tuples $(T,a,b,c,d)$ such that $T$ is a tree, $a,b,c,d$ are vertices, $ab$ is an edge of $T$ and this edge belongs to the path between $c$ and $d$ (in the order $cabd$ on the path). If we remove $ab$, we get two connected components $A\ni a$, $B\ni b$. If $|A|=i$, $|B|=n-i$, we may fix $A$, $B$ by $\binom{n}i$ ways, after that fix restrictions of $T$ onto $A$, $B$ by $i^{i-2}(n-i)^{n-i-2}$ ways and fix $a,b,c,d$ by $i^2(n-i)^2$ ways. Totally we get RHS of your formula.
Why we get LHS is explained in Claude Lenormand's comment for A000435 (there we count the sum of distances from the fixed vertex 0 to other vertices in all trees, of course it is $n$ times less than the sum of all distances.)
Best Answer
Your equation can be written as an equation for exponential generating functions: $f(x) = g(x)(f(x)+1)$, where $$f(x) = \sum_{n\ge1}n^nx^n/n!$$ and $$g(x) = \sum_{n\ge1}n^{n-1}x^n/n!$$
We can see that for those $f(x)$ and $g(x)$, we have $f(x) = xg'(x)$. If we then solve the differential equation $$xg'(x) = \frac{g(x)}{1-g(x)}$$ with $g(0)=0$, we get that the solution satisfies $x=g(x)e^{-g(x)}$.
By the Lagrange inversion formula, the computational inverse of $xe^{-x}$ is exactly our $g(x)$.
I'm sure some permutation of the reasoning steps above gives a proof for your equation.