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

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.

• I think there is a typo, we want to say that $x_k=x$. For the inequality $N-\binom{x}{k}\lt \binom{x}{k-1}$, all that is being used is the "Pascal" identity $\binom{x+1}{k}=\binom{x}{k}+\binom{x}{k-1}$. – André Nicolas Aug 5 '13 at 15:15
• Thank you. I had a suspicion. I will se if I am successful now. – tychicus Aug 5 '13 at 15:18
• By the way, how will the sum look like if e.g. $N = 12$? Is there only one $k$ value that fits when $N = 12$. – tychicus Aug 5 '13 at 15:29
• Any fixed $k$ should work, but the statement of the theorem needs to change, we have to allow "skipping." – André Nicolas Aug 5 '13 at 15:53
• This is the combinatorial number system, the linked article gives ample explanation. – Marc van Leeuwen Aug 6 '13 at 7:26

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.

• You wrote "So we set $x_k=x$ and let $N_1=N-\dbinom{x_1}k$." Did you mean $N_1=N-\dbinom{x_k}{k}$? That would be consistent with what you wrote in your next paragraph: $N_1=\dbinom{x_{k-1}}{k-1}+\ldots+\dbinom{x_1}{1}$ – tychicus Aug 6 '13 at 7:21
• @tychicus: Yes, I did; I’ve fixed it now. (The same mistake was in the original version of your hint, and I must have unconsciously copied that.) – Brian M. Scott Aug 6 '13 at 12:02