proving $\binom{n-1}{k} - \binom{n-1}{k-2} = \binom{n}{k} - \binom{n}{k-1} $

Solution 1:

We will prove the equivalent $$\binom{n-1}k+\binom n{k-1}=\binom nk +\binom{n-1}{k-2}\tag1$$

Let $[m]=\{1,2,3,\dots,m\}.$ Write $$\binom{[m]}j=\{S\subseteq [m]\mid |S|=j\}$$ Let $$\mathcal S_1=\binom{[n-1]}k\cup \binom{[n]}{k-1}\\\mathcal S_2=\binom{[n]}k\cup \binom{[n-1]}{k-2}$$

Show $|\mathcal S_1|,|\mathcal S_2|$ are equal to the left and right side of (1), respectively.

The map sending $f:\mathcal S_1\to\mathcal S_2$ defined as: $$f(S)=\begin{cases} S\setminus \{n\}& |S|=k-1,n\in S\\ S\cup\{n\}& |S|=k-1, n\not\in S\\ S&|S|=k \end{cases}$$

The image in the first case is a subset of $[n-1]$ of size $k-2.$

The image in the other two cases is a subset of $[n]$ of size $k.$

Show this is one-to-one and onto.

This is really just hiding the direct proof using the simpler combinatorial result: $$\binom{n}{k}=\binom{n-1}k+\binom{n-1}{k-1}\\\binom n{k-1}=\binom{n-1}{k-1}+\binom{n-1}{k-2}$$

Both sides of $(1)$ are equal to the total number of subsets of $[n-1]$ of sizes $k-2,k-1,$ or $k.$

Solution 2:

Hint: You might also find appealing that algebraically this binomial identity is encoded by the relation \begin{align*} 1-z^2=(1+z)(1-z) \end{align*}

Denoting with $[z^k]$ the coefficient of $z^k$ of a series we can write \begin{align*} \binom{n}{k}=[z^k](1+z)^n\tag{1} \end{align*}

Using (1) and noting that $[z^p]z^qA(z)=[z^{p-q}]A(z)$ we obtain \begin{align*} \color{blue}{\binom{n-1}{k}}\color{blue}{ - \binom{n-1}{k-2}} &=[z^k](1+z)^{n-1}-[z^{k-2}](1+z)^{n-1}\\ &=[z^k]\left(1-z^2\right)(1+z)^{n-1}\\ &=[z^k](1-z)(1+z)^n\\ &=[z^k](1+z)^n-[z^{k-1}](1+z)^{n}\\ &\,\,\color{blue}{=\binom{n}{k}-\binom{n}{k-1}} \end{align*}