1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$. $\endgroup$ – André Nicolas Aug 5 '13 at 15:15
  • $\begingroup$ Thank you. I had a suspicion. I will se if I am successful now. $\endgroup$ – tychicus Aug 5 '13 at 15:18
  • $\begingroup$ 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$. $\endgroup$ – tychicus Aug 5 '13 at 15:29
  • $\begingroup$ Any fixed $k$ should work, but the statement of the theorem needs to change, we have to allow "skipping." $\endgroup$ – André Nicolas Aug 5 '13 at 15:53
  • $\begingroup$ This is the combinatorial number system, the linked article gives ample explanation. $\endgroup$ – Marc van Leeuwen Aug 6 '13 at 7:26
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – tychicus Aug 6 '13 at 7:21
  • $\begingroup$ @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.) $\endgroup$ – Brian M. Scott Aug 6 '13 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.