IMC 2015 · Day 2 · P8

Let $n = 26$, then $3^{75} = (n+1)^{n-1}$. We use the following well-known

Lemma. If $f(x)$ is a polynomial of degree at most $n$, then its $(n+1)$-st finite difference vanishes: $\Delta^{n+1} f(x) := \sum\limits_{i=0}^{n+1} (-1)^i \binom{n+1}{i} f(x + i) \equiv 0$.

Proof. If $\Delta$ is the operator which maps $f(x)$ to $f(x+1) - f(x)$, then $\Delta^{n+1}$ is indeed $(n+1)$-st power of $\Delta$ and the claim follows from the observation that $\Delta$ decreases the power of a polynomial.

In other words, $f(x) = \sum\limits_{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\limits_{j=0}^{k} \binom{k}{j} \cdot \frac{(-1)^j}{j+1} = \frac{1}{k+1} \cdot \sum\limits_{j=0}^{k} (-1)^j \cdot \binom{k+1}{j+1} = \frac{1}{k+1}$, since the alternating sum of binomial coefficients $\sum\limits_{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}$.