Prove the combinatorial identity $${n \choose k} = {n-2\choose k-2} + 2{n-2\choose k-1} + {n-2\choose k} .$$
I understand the left side, which is obvious, but I'm struggling to get anywhere on the RHS. I also would appreciate suggestions on how to approach these kind of problems. I was told to use committees and split them up, but even then it's not so intuitive to me.
I've tried substituting small numbers to see where I can go.
Thank you in advance for your time.
Hint: try writing the right side as $$\left[\binom{n-2}{k}+\binom{n-2}{k-1}\right]+\left[\binom{n-2}{k-1}+\binom{n-2}{k-2}\right]$$
The committee trick works pretty well. Say you want to choose a committee of $k$ people out of $n$. Among $n$ people there are two leaders (you and me). The terms on the RHS are number of possibilities: with both leaders, with one leader, and with no leaders.
Suppose you want to form a committee of $k$ people from a group of $n$. We know that we can do this in $\binom n k$ ways.
But suppose that two of the people are somewhat distinguished; let's call them A and B. So we want to count the cases based on these guys being in the committee or not separately:
The sum of these cases is equal to $\binom n k$.
You could also prove this equality without any computation by interpreting the meaning of $n \choose k$: it is the number of subsets of size $k$ (or $k$-subset) in a set $S$ of size $n$. Let us select two distinct elements $a$ and $b$ of $S$ and let $T = S-\{a,b\}$. The $k$-subsets of $S$ can be divided into four categories:
Summing up, you get $$ {n \choose k} = {{n-2}\choose {k}} + {{n-2}\choose {k-1}} + {{n-2}\choose {k-1}} + {{n-2}\choose {k-2}} = {{n-2}\choose {k}} + 2{{n-2}\choose {k-1}} + {{n-2}\choose {k-2}} $$
Hint Use the standard and similar-looking Pascal's Identity: $${n \choose k} = {{n - 1} \choose k} + {{n - 1} \choose {k - 1}} .$$
Additional hint Apply the identity to both terms on the r.h.s. of the identity itself.
It is well known that one can represent ${n\choose k}=\frac{n!}{k!(n-k)!}$. Try using this. If you still have trouble then you have:
$\begin{align}\frac{(n-2)!}{k!(n-2-k)!}+2\frac{(n-2)!}{(k-1)!(n-1-k)!}+\frac{(n-2)!}{(k-2)!(n-k)!}\\=\frac{(n-2)!(n-1-k)(n-k)}{k!(n-k)!}+2\frac{(n-2)!k(n-k)}{k!(n-k)!}+\frac{(n-2)!(k-1)k}{k!(n-k)!}\\=\frac{(n-2)!(n-1-k)(n-k)+2(n-2)!k(n-k)+(n-2)!(k-1)k}{k!(n-k)!}\\=\frac{(n-2)!}{k!(n-k)!} [(n-1-k)(n-k)+2k(n-k)+(k-1)k]\\=\frac{(n-2)!}{k!(n-k)!} [n^2-2kn+k^2-n+k+2kn-2k^2+k^2-k]\\=\frac{(n-2)!}{k!(n-k)!} (n^2-n)\\=\frac{(n-2)!}{k!(n-k)!} (n-1)n\\=\frac{n!}{k!(n-k)!}\end{align}$
We can start with the right hand side:
$\binom{n-2}{k-2}+\binom{n-2}{k-1} = \binom{n-1}{k-1}$, and again $\binom{n-2}{k-1}+\binom{n-2}{k}=\binom{n-1}{k}$, now adding these result we have:
$\binom{n-1}{k-1}+\binom{n-1}{k} = \binom{n}{k}$
Hint: Use the identity $$\binom nk = \binom{n-1}{k-1} + \binom{n-1}k$$ And rewrite your sum as $${n-2\choose k-2} + 2{n-2\choose k-1} + {n-2\choose k}=\left({n-2\choose k-2} + {n-2\choose k-1}\right) + \left({n-2\choose k-1} + {n-2\choose k}\right)$$
There is a well known Identity called Pascal's Identity, namely that ${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$. The proof of this can be done algebraically if you please ($\frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-k-k)!} = \frac{n!}{k!(n-k)!}$ with some expansion) or through casework.]
This can finish the problem pretty quickly.
One way to interpret the numbers in Pascal’s triangle is that $n\choose k$ is the number of different paths from the point $(0,0)$ at the top of the triangle (the $0$-th number in row #$0$, where there is a $1$ that equals $0\choose0$) to the point $(n,k)$ (where $n\choose k$ appears) using steps that either increase $n$ by $1$ and leave $k$ alone or that increase both $n$ and $k$ by $1$.
In this picture, the possible steps in the path would move by one square to the east (increasing only $n$) or to the southeast (increasing both $k$ and $n$).
If you’re patient and careful, you can check, for example, that there are $20$ different paths from the green square to the yellow square by southward or southeastward steps.
It’s not hard to see that every $S$ or $SE$-moving path from the green square to the yellow square has to pass through one of the blue squares, where the $n$ value is smaller than in the yellow square by $2$. From either the top or bottom blue square, there’s only one way to continue on to the yellow square, but from the middle blue square, there are two ($S$, then $SE$ or vice versa).
This is pretty much a proof of your identity, because the number of paths from the green square to any (yellow) square containing $n\choose k$ must pass through one of exactly three (blue) squares in the column where $n$ is smaller by $2$, and the paths to the yellow square can be counted separately according to which blue square they pass through, and if you do so, you get the formula you asked about.
One way to do is to expand R.H.S., but it is not a wise choice, see others' answer.
${n-2\choose k-2} + 2{n-2\choose k-1} + {n-2\choose k}$
$= \frac{(n-2)!}{(k-2)!(n-k)!} + \frac{2(n-2)!}{(k-1)!(n-k-1)!} + \frac{(n-2)!}{k!(n-k-2)!}$
$= \frac{(n-2)!}{(k-2)!(n-k-2)!} (\frac{1}{(n-k)(n-k-1)} + \frac{2}{(k-1)(n-k-1)} + \frac{1}{k(k-1)})$
And
$\frac{1}{(n-k)(n-k-1)} + \frac{2}{(k-1)(n-k-1)} + \frac{1}{k(k-1)}$
$= \frac{k(k-1) + 2(n-k)k + (n-k)(n-k-1)}{(n-k)(n-k-1)k(k-1)}$
$= \frac{k(k-1) + k(n-k) + (n-k)k + (n-k)(n-k-1)}{(n-k)(n-k-1)k(k-1)}$
$= \frac{k(n-1) + (n-k)(n-1)}{(n-k)(n-k-1)k(k-1)}$
$= \frac{n(n-1)}{(n-k)(n-k-1)k(k-1)}$
So, we have
${n-2\choose k-2} + 2{n-2\choose k-1} + {n-2\choose k}$
$= \frac{(n-2)!}{(k-2)!(n-k-2)!} \times \frac{n(n-1)}{(n-k)(n-k-1)k(k-1)}$
$= \frac{n!}{k!(n-k)!} = {n \choose k}$
