| |||||||||

## IMC2015: Day 2, Problem 8
Proposed by Fedor Petrov, St. Petersburg State University
In other words, $f(x)=\sum_{i=1}^{n+1} (-1)^{i+1}\binom{n+1}{i} f(x+i)$. Applying this for $f(x)=(n-x)^n$, substituting $x=-1$ and denoting $i=j+1$ we get $$ (n+1)^n=\sum_{j=0}^n (-1)^j \binom{n+1}{j+1} (n-j)^n=(n+1) \sum_{j=0}^n \binom{n}{j}\cdot \frac{(-1)^j}{j+1}\cdot (n-j)^n. $$ The $j$-th summand $\binom{n}{j}\cdot \frac{(-1)^j}{j+1}\cdot (n-j)^n$ may be interpreted as follows: choose $j$ letters, consider all $(n-j)^n$ words without those letters and sum up $\frac{(-1)^j}{j+1}$ over all those words. Now we change the order of summation, counting at first by words. For any fixed word $W$ with $k$ absent letters we get $\sum_{j=0}^k \binom{k}{j}\cdot \frac{(-1)^j}{j+1}=\frac1{k+1}\cdot \sum_{j=0}^k (-1)^j\cdot \binom{k+1}{j+1}=\frac1{k+1}$, since the alternating sum of binomial coefficients $\sum_{j=-1}^k (-1)^j\cdot \binom{k+1}{j+1}$ vanishes. That is, after changing order of summation we get exactly initial sum, and it equals $(n+1)^{n-1}$.
Define a map $\varphi:W\to W^*$ in the following way. Suppose that $w\in W$ is an arbitrary $26$-string and $x$ is its first letter. Remove the leading $x$ from $w$ and replace all other occurences of $x$ by the character $*$. Let $\varphi(w)\in W^*$ be the resulting $25$-string. Notice that the number of different Latin letters decreases by $1$, so we have $\ell(\varphi(w))=\ell(w)-1$. The map $\varphi$ is not injective. For every $u\in W^*$, as $u$ contains $\ell(u)$ different characters, there are $26-\ell(u)$ different Latin letters that are not used in $u$, there are $26-\ell(u)$ possible pre-images of $u$. The pre-images of $u$ contain $\ell(u)+1$ Latin letters, so their weights are equal to $\frac{1}{26-\ell(u)}$. Hence, the total weight of the pre-images of $u$ is equal to $1$. Therefore, the total weight of the words in $W$ is equal to the number of strings in $W^*$, which is $|W^*|=27^{25}$. | |||||||||

© IMC |