3
$\begingroup$

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.

$\endgroup$

11 Answers 11

6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ why two leaders? because there are two variables? so the case with no leaders would be C(6,3), one leader C(6,4), and both leaders C(6,5)? $\endgroup$ – ponderingdev Sep 14 '15 at 2:00
  • 1
    $\begingroup$ Both leaders should be $C(6,3)$: you already choose both leaders, only need to choose $k-2$ more out of $n-2$ left. And two leaders because you are looking at $C(n-2,k)$ and so on. If it were $C(n-3,k)$ and so on, you would choose $3$ leaders and get a similar identity. $\endgroup$ – Quang Hoang Sep 14 '15 at 2:04
7
$\begingroup$

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]$$

$\endgroup$
5
$\begingroup$

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:

  • We can have $\binom{n-2}{k-2}$ committees with both A and B.
  • We can have $\binom{n-2}{k-1}$ committees with A and without B.
  • We can have $\binom{n-2}{k-1}$ committees without A and with B.
  • We can have $\binom{n-2}{k}$ committees without A and without B.

The sum of these cases is equal to $\binom n k$.

$\endgroup$
3
$\begingroup$

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:

  1. the $k$-subsets of $T$: ${n-2}\choose k$ possibilities,
  2. the $k$-subsets of the form $R \cup \{a\}$, where $R$ is a $(k-1)$-subset of $T$: ${n-2}\choose {k-1}$ possibilities,
  3. the $k$-subsets of the form $R \cup \{b\}$, where $R$ is a $(k-1)$-subset of $T$: ${n-2}\choose {k-1}$ possibilities
  4. the $k$-subsets of the form $R \cup \{a, b\}$, where $R$ is a $(k-2)$-subset of $T$: ${n-2}\choose {k-2}$ possibilities.

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}} $$

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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}$

$\endgroup$
  • 1
    $\begingroup$ I would quibble with saying the factorial formula is the definition of $\binom{n}{k}$. The definition is a combinatorial definition about counting subsets. The factorial formula is a consequence of that definition. $\endgroup$ – alex.jordan Sep 10 '15 at 18:40
  • $\begingroup$ @alex.jordan You are correct. Thanks. $\endgroup$ – nathan.j.mcdougall Sep 10 '15 at 18:46
2
$\begingroup$

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}$

$\endgroup$
0
$\begingroup$

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)$$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$).

enter image description here

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.

$\endgroup$
0
$\begingroup$

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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.