<s>[INST] integer as sum of three binomials Prove that for any nonnegative integer $n$ $\exists x,y,z \in \mathbb{N}$ and $0\leq x<y<z$ so
$$n=\binom{x}{1}+\binom{y}{2}+\binom{z}{3}$$
Please give me a hint, I don't have any idea.
 [/INST] Easy to see that
$$
1 = {x_1 \choose 1}+{y_1 \choose 2}+{z_1 \choose 3}
$$
where $x_1 = 0$, $y_1 = 1$, $z_1 = 3$.
Now suppose
$$
i = {x_i \choose 1}+{y_i \choose 2}+{z_i \choose 3}
$$
where $0 \leq x_i < y_i < z_i$. We want to decide $0 \leq x_{i+1} < y_{i+1}<z_{i+1}$ such that
$$
i + 1 = {x_{i+1} \choose 1}+{y_{i+1} \choose 2}+{z_{i+1} \choose 3}
$$

I provide a procedure to decide $x_{i+1}, y_{i+1}, z_{i+1}$ below.


*

*if $x_i < y_i - 1$
Let $x_{i+1} = x_i + 1, y_{i+1} = y_i, z_{i+1} = z_i$. Easy to see that the sum increment $1$.


*

*if $x_i = y_i - 1\textbf{ and }y_i < z_i - 1$
Let $x_{i+1} = 0, y_{i+1} = y_i + 1, z_{i+1} = z_i$. We have
\begin{align}
&{z_{i+1} \choose 3} + {y_{i + 1} \choose 2}+{x_{i+1} \choose 1} - {z_i \choose 3} - {y_i \choose 2}-{x_i \choose 1}\\
=& {z_i \choose 3} + {y_i + 1 \choose 2}+{0 \choose 1} - {z_i \choose 3} -{y_i \choose 2} - {y_i - 1 \choose 1} \\
=& \frac{(y_i + 1)y_i}{2} + 0 - \frac{y_i(y_i - 1)}{2} - (y_i - 1)\\
=& 1
\end{align}


*

*if $x_i = y_i - 1\textbf{ and }y_i = z_i - 1$
Let $x_{i+1} = 0, y_{i+1} = 1, z_{i+1} = z_i + 1$. We have
\begin{align}
&{z_{i+1} \choose 3} + {y_{i + 1} \choose 2}+{x_{i+1} \choose 1} - {z_i \choose 3} - {y_i \choose 2}-{x_i \choose 1}\\
=& {z_i + 1 \choose 3} + {1 \choose 2}+{0 \choose 1} - {z_i \choose 3} -{z_i - 1 \choose 2} - {z_i - 2 \choose 1} \\
=& \frac{(z_i + 1)z_i(z_i - 1)}{6} + 0 + 0 - \frac{z_i(z_i-1)(z_i-2)}{6} - \frac{(z_i - 1)(z_i - 2)}{2} - (z_i - 2)\\
=& \frac{z_i(z_i - 1)}{2} - \frac{(z_i-1)(z_i - 2)}{2} - (z_i - 2)\\
=& 1
\end{align}
Note that the procedure guarantees $0 \leq x_{i+1} < y_{i+1} < z_{i+1}$.
</s>