Proving Pascal's identity $ \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$

Question

I'm trying to prove Pascal's identity, no luck so far. I have an answer which seem to include some unexplained shifts that I don't get.

What needs to be proved:

$$ \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$$

This shift is not clear to me: $$\binom{n}{k}+\binom{n}{k+1}=\frac{n!}{k!(n-k)!}+\frac{n!}{(k+1)!(n-k-1)!}$$ $$=\bbox[10pt,border:5px solid blue]{\frac{n!}{k!(n+1-(k+1))!}+\frac{n!(n-k)}{(k+1)!(n+1-(k+1))!}}$$

Answer 1

Rather than using the factorial definition within this argument, consider a more combinatorial argument, perhaps.

Given a set $S$ of order $n+1$, $\binom{n+1}{k+1}$ is the number of subsets of $S$ of order $k+1$. Fix one element of the set, $a \in S$. We have two disjoint and exhaustive possibilities here:

1. We include $a$ in our subset, and choose the remaining $k$ from $S\backslash\{a\}$, giving us $\binom{n}{k}$ choices.
2. We do not include $a$, and choose all $k+1$ elements from the subset $S\backslash\{a\}$, giving us $\binom{n}{k+1}$ choices.

Since these choices are disjoint and exhaustive, we can apply the elementary counting principle, the addition rule (aka the rule of sum), and the result follows.

Answer 2

Answering Eran's question:

---

The first term:

$\frac{n!}{k!(n-k)!} = \frac{n!}{k!(n+1-k-1)!} = \frac{n!}{k!(n+1-(k+1))!}$

is just adding and subtracting an extra $1$ and re-writing.

---

The second term:

$\frac{n!}{(k+1)!(n-k-1)!} = \frac{n!(n-k)}{k!(n-k-1)!(n-k)} = \frac{n!(n-k)}{k!(n-k)!}$

is multiplying $(n-k)$ in the numerator and denominator which allows you to re-write the factorial in the denominator. There's one last step, but that last step is the same as the first term.

Answer 3

The term in the blue rectangle should be:

$$ \frac{n!(k+1)}{(k+1)!(n-k)!}+\frac{n!(n-k)}{(k+1)!(n-k)!} $$

Now, it should be easy to add both fractions and arrive at the desired result.

Answer 4

Considering the highest factors in the factorials,

$$\binom n{k+1}=\binom nk\frac{n-k}{k+1}$$

so that

$$\binom nk+\binom n{k+1}=\binom nk\frac{n+1}{k+1}=\binom{n+1}{k+1}.$$

Answer 5

Two facts seem to be involved in getting to the formula in the blue box from the previous formula. One fact is that $$n+1-(k+1)=n-k.\tag1$$

The other fact is that $$ x((x-1)!) = x!.\tag2$$

I honestly don’t see why the fact in $(1)$ was invoked at this point. Yes, it’s a true fact, but invoking it just means we write $n+1-(k+1)$ in several places where $n-k$ would work better. Eventually, it might be useful to rewrite $n-k$ that way in order to relate to the expansion of $\binom{n+1}{k+1}$ into factorials, but we only actually make use of that in the last step of the derivation.

In particular, the specific way that the fact in $(2)$ is invoked is that we can multiply $\frac{n!}{(k+1)!(n-k-1)!}$ by $n-k$ on the top and bottom. On the top we get $n!(n-k),$ as shown in the blue box, and on the bottom we get $$(n-k)((n-k-1)!) = (n-k)!,$$ which uses fact $(2)$ with $x$ replaced by $n-k.$

Of course, because of fact $(1)$ It is equally true that $$(n-k)((n-k-1)!) = (n+1-(k+1))!,$$ which is how we get the formula in the blue box, but I think this is harder to see.