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.
 A: Consider $z_m={m\choose 3}$ for all $m$. Difference $z_{m+1}-z_{m}=\frac{m(m-1)}{2}$. We choose such $m$, that $z_m$ is maximal, non exceeding $n$.
The most difference $n_y=n-z_m$ we would have to cover, is $\frac{m(m-1)}{2}-1$.
Now we choose $y_k={k\choose 2}$ to be maximal, non exceeding $n_y$. Note that maximal $k$ could be $m-1$, since $\frac{m(m-1)}{2}-1$ is the maximal value for $n_y$ (i.e. it can't be $\ge\frac{m(m-1)}{2}$). Analogically, $y_{k+1}-y_k-1=k-1$ is the maximal value to cover with $x$.
So, we select $y=k$ and $z=m$.
A: 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}$.
