Combinatorial proof of $ \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}. $

Question

I'm trying to understand the combinatorial identity $ \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}. $ I have a good understanding of the algebraic manipulation involved, but I'm struggling with the following interpretation:

Suppose $k$-subset $A = \{0,1,2,3,...,n\}$ where $A$ has $n+1$ elements.

(1) Now, the subset $\binom{n}{k-1}$ can contain the subset of $A$ containing $0$ because to make that a subset, we can start with $\{0\}$ and append an additional $k-1$ numbers selected from $\{1,2,3,...,n\}$, and there are $\binom{n}{k-1}$ ways to do that.

(2) On the other hand, $\binom{n}{k}$ does not contain $0$ since it is the number of ways to select $k$-element subsets from $\{1,2,...,n\}$.

With statement (2), I don't have any issues; I understand that $A = \{0,1,2,...,n\}$ has $n+1$ elements, and if we remove $0$, we are left with the set $\{1,2,...,n\}$ which has $n$ elements. My problem is with statement (1) as I don't understand if we are saying that $A = \{0,1,2,...,n\}$ of length $n+1$ then why it is still there in $\binom{n}{k-1}$? it's because we remove another element to become $\{0,1,2,3,...,n-1\}$? Additionally, I'm not sure what "we can start with $\{0\}$ and append an additional $k-1$ numbers" means. Does it imply that subsets like $\{0,1\}, \{0,2\}$, etc., can be formed?

Any clarification on this would be greatly appreciated.

P.S. I'm concious that this problem is already here in Mathematics StackExchange, but this way of prooving the problem (with the $0$ cases) is not yet. Prove that $\binom{n+1}k = \binom nk + \binom n {k-1}$

Answer 1

Like you said $\binom{n+1}{k}$ counts how many subsets of $\{0,\dots,n\}$ you can make that contain $k$ (distinct) elements.

Now you can split all these sets in two categories:

1. Subsets of $\{0,\dots,n\}$ with $k$ elements that contain $0$:
   Since for a subset in this category you already have $0$ included, to complete the subset all you have to do is pick $k-1$ more elements from the remaining $n$ (remember, we have $n+1$ in total).
   Thus the number of subsets with $k$ elements containing $0$ are $\binom{n}{k-1}$.
2. Subsets of $\{0,\dots,n\}$ with $k$ elements that don't contain $0$:
   Since these subsets do not contain $0$, you are basically counting the number of subsets with $k$ (distinct) elements from the set $\{0,\dots,n\}\setminus\{0\}$, which has $n$ elements.
   These are precisely $\binom{n}{k}$ in total.

Since a set either does or doesn't contain $0$, the two cases above cover all possible subsets of $\{0,\dots,n\}$ containing $k$ elements, so putting everything together we get the wanted equality: $$\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$$

Answer 2

you can understand it as,

suppose there is a set A having n elements say

A = {$A_1 , A_2, A_3 , ........ A_n$}

now if person 1 and 2 are given a task to choose either k elements or k+1 elements out of set A, and asked in how many ways can the task be done.

now assuming that 1 is a little smarter than 2 lets see the difference in their approaches towards the problem.

while 2 goes in a conventional way to calculate the ans by simple permutations and combinations he reports the ans as

${n \choose k} + {n \choose k+1}$

which is correct no doubt.

now since 1 is smarter he uses his wittiness and simplifies the problem in a different way. He adds a new dummy element to set A say $d_{\phi}$ and makes a new set $A_N$

$A_N = A + d_{\phi}$

now 1 chooses k+1 elements outta the new set $A_N$ if the element $d_{\phi}$ is chosen he regards it as null and it signifies that only k elements were chosen if $d_{\phi}$ is not chosen then k+1 elements are chosen.

so this new set $A_N$ covers both the cases without considering them different. so 1 reports the ans as

${n+1 \choose k}$ which also happens to be correct.

thus finally arriving at our result

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

Answer 3

The problem becomes more comprehensible with the aid of an illustration. Consider an image featuring 5 balls, 4 of which are blue and 1 is red. Enumerating all possible combinations visually elucidates the scenario.