<s>[INST] Show that $\binom{n}{3} = \binom{2}{2} + \binom{3}{2} + \binom{4}{2}+...+\binom{n - 1}{2}$ I cam across a question in The Book of Proof that states:
Show that $$\binom{n}{3} = \binom{2}{2} + \binom{3}{2} + \binom{4}{2}+...+\binom{n - 1}{2}$$
Which I found the answer to be:
Assume n ≥ 3. Then:
$$\binom{n}{3} = \binom{n - 1}{3} + \binom{n - 1}{2} = \binom{n - 2}{3} + \binom{n-2}{2}+ \binom{n - 1}{2} = \binom{2}{2} + \binom{3}{2}+...+\binom{n-1}{2}$$
I have just learned about the binomial theorem, and I am not sure how we got to that answer.
I understand that $\binom{n}{3} = \binom{n - 1}{3} + \binom{n - 1}{2}$ because that is the sum of the two previous rows in the Pascal triangle. But I can't find a simple explanation for the steps that follow or for why we assumed $n \geq 3$
 [/INST] Maybe you know the possible ways to $x_1+x_2+x_3+...+x_k=n$ when $x_i \in \mathbb{Z^+}$ is $\left(\begin{array}{c}n+k-1\\ k-1\end{array}\right)$ now suppose we need to find possible way to $$x_1+x_2+x_3 \leq n$$ first we take apart the states
$$x_1+x_2+x_3 =0 \to \left(\begin{array}{c}0+3-1\\ 3-1\end{array}\right)\\
x_1+x_2+x_3 =1 \to \left(\begin{array}{c}1+3-1\\ 3-1\end{array}\right)\\
x_1+x_2+x_3 =2\to \left(\begin{array}{c}2+3-1\\ 3-1\end{array}\right)\\
...\\
x_1+x_2+x_3 =n\to \left(\begin{array}{c}n+3-1\\ 3-1\end{array}\right)$$ sum of them is $$ \left(\begin{array}{c}2\\ 2\end{array}\right)+\left(\begin{array}{c}2\\ 2\end{array}\right)+\cdots+\left(\begin{array}{c}n+2\\ 2\end{array}\right)$$  second way to solve is to add a variable, to turn inequality to make equation like below
$$x_1+x_2+x_3 \leq n \mapsto x_1+x_2+x_3 +\bf{x_4}= n$$ it summarize all above ways to one states  $$x_=0 \to x_1+x_2+x_3=n\\x_4=1 \to x_1+x_2+x_3=n-1\\\vdots$$ so $$x_1+x_2+x_3+x_4=n \to \left(\begin{array}{c}n+4-1\\ 4-1\end{array}\right)=\left(\begin{array}{c}n+2\\ 3\end{array}\right)$$  so finally  $$
\left(\begin{array}{c}2\\ 2\end{array}\right)+\left(\begin{array}{c}3\\ 2\end{array}\right)+\left(\begin{array}{c}4\\ 2\end{array}\right)+...+\left(\begin{array}{c}n+2\\ 2\end{array}\right)=\left(\begin{array}{c}n+3\\ 3\end{array}\right)$$ hope it helps you
</s>