Putnam 2007, Problem B-5

Let $k$ be a positive integer. Prove that there exist polynomials $P_0(n), P_1(n), \ldots, P_{k-1}(n)$ (which may depend on $k$) such that for any integer $n$,
$$\left\lfloor \frac{n}{k} \right\rfloor^k = P_0(n) + P_1(n) \left\lfloor \frac{n}{k} \right\rfloor + \cdots + P_{k-1}(n) \left\lfloor \frac{n}{k} \right\rfloor^{k-1}.$$
($\lfloor a \rfloor$ means the largest integer $\leq a$.)

Solution:
For $n$ an integer, we have $\lfloor \frac{n}{k} \rfloor = \frac{n-j}{k}$ for $j$ the unique integer in $\{0, \ldots, k-1\}$ congruent to $n$ modulo $k$; hence
$$\prod_{j=0}^{k-1}\left(\left\lfloor \frac{n}{k} \right\rfloor - \frac{n-j}{k}\right) = 0.$$
By expanding this out, we obtain the desired polynomials $P_0(n), \ldots, P_{k-1}(n)$.

**Remark:** Variants of this solution are possible that construct the $P_i$ less explicitly, using Lagrange interpolation or Vandermonde determinants.