Every integer is the unique sum of a “decreasing” sequence of binomial coefficients

Question

I need some advice as I am struggling with the following combinatorics exercise.

Let $k$ be a given positive integer. Show that any non-negative integer $N$ can be written uniquely in the form

$$N=\binom{x_k}{k}+\binom{x_{k-1}}{k-1}+\dots+\binom{x_1}{1},$$

where $0 \leq x_1 < \dots < x_{k-1} < x_k$.

The exercise is accompanied by this advice:

Let $x$ be such that $\binom{x}{k} \leq N < \binom{x+1}{k}$. Then any possible representation has $x_k = x$. Now use induction and the fact that $N-\binom{x}{k} < \binom{x}{k-1}$ to show the existence and uniqueness of the representation.

I am really stuck and thus grateful for the slightest hint on how to solve it.

Answer 1

Take as your induction hypothesis the statement that if $M$ is a non-negative integer less than $N$, and $\ell$ is any positive integer, then there is a unique decomposition

$$M=\binom{x_\ell}\ell+\binom{x_{\ell-1}}{\ell-1}+\ldots+\binom{x_1}1$$

with $0\le x_1<x_2<\ldots<x_\ell$.

There is certainly a unique non-negative integer $x$ such that $\binom{x}k\le N<\binom{x+1}k$. The first thing to verify is that it’s the only possible choice for $x_k$. Certainly nothing larger can possibly work. What if we start with some $x_k<x$? Then the biggest possible total that we can get is

$$\begin{align*} \binom{x-1}k+\binom{x-2}{k-1}+\ldots+\binom{x-k}1&=\sum_{i=1}^k\binom{x-k-1+i}i\\\\ &=\sum_{i=1}^k\binom{x-k-1+i}{x-k-1}\\\\ &=\binom{x}{x-k}-\binom{x-k-1}0\\\\ &=\binom{x}k-1\\\\ &<N\;. \end{align*}$$

So we set $x_k=x$ and let $N_1=N-\dbinom{x_k}k$. Verify that $N_1<N$. If $N_1=0$, you’re done. Otherwise, the induction hypothesis gives you a unique decomposition

$$N_1=\binom{x_{k-1}}{k-1}+\ldots+\binom{x_1}1$$

such that $0\le x_1<\ldots<x_{k-1}$. To finish, just show that $x_{k-1}$ in this decomposition is necessarily less than $x_k$; the hint that you’re given is to use the fact that $N_1<\dbinom{x_k}{k-1}$. To see why this is true, suppose on the contrary that $x_{k-1}\ge x_k$ and consider what this says about $\dbinom{x_k}k+\dbinom{x_{k-1}}{k-1}$ in view of Pascal’s identity.