Show that $\binom{n}{3} = \binom{2}{2} + \binom{3}{2} + \binom{4}{2}+...+\binom{n - 1}{2}$

Question

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$

Answer 1

$$S=\sum_{k=2}^{n-1} {k \choose 2} =\text{co-efficient of}~ x^2~ \text{in}\sum_{k=0}^{n-1}(1+x)^k= \text{co-efficient of} ~x^2~ \text{in} \frac{(1+x)^n-1}{1+x-1}. $$ $$\implies S= \text{co-efficient of} ~x^3~ \text{in} [(1+x)^n-1]={n \choose 3}$$

Answer 2

$3$ is arbitrary here. You can apply the same idea of this proof to obtain that $$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-2}{k-1} + \dots + \binom{k-1}{k-1} $$ with an anologous proof.

Also it's helpful to see the identity $$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} $$ in a more combinatorial sense.

The number of ways of choosing $k$ objects out of $n$ is equal to the number of ways of choosing $k$ objects out of the first $n-1$ or choosing $k-1$ out of the first $n-1$ (therefore forcing your k^th choice to be the n^th object).

Answer 3

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