As the title says.
Prove that ${n+1 \choose k} = {n \choose k} + {n \choose k-1}$
It looks to me like induction but since there are two variables, I'm not really sure how to even set up a base case. If it is, in fact, induction.
$\begingroup$
$\endgroup$
6
-
2$\begingroup$ This is Pascal's Law and it has been asked before on here for sure. $\endgroup$– Git GudCommented Sep 23, 2013 at 19:16
-
$\begingroup$ Notice $k \leq n$, so induction via $n$ works. $\endgroup$– AlexRCommented Sep 23, 2013 at 19:16
-
$\begingroup$ This is a duplicate, but consider what the expansion of these terms looks like. Can you see how to make the connection? $\endgroup$– abiessuCommented Sep 23, 2013 at 19:16
-
$\begingroup$ @GitGud Weren't able to find any. But well how to search for this anyways, too general terms... @ Nick: I'll give it a shot since I weren't able to find a dupe. $\endgroup$– AlexRCommented Sep 23, 2013 at 19:22
-
4$\begingroup$ See also this post and other questions linked there $\endgroup$– Martin SleziakCommented Oct 29, 2016 at 6:39
|
Show 1 more comment
2 Answers
$\begingroup$
$\endgroup$
1
We know $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$ So now $$\begin{align*} \binom{n}{k} + \binom{n}{k-1} & = \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)! (n-k+1)!} \\ & = \frac{n! (n-k+1)}{k! (n+1-k)!} + \frac{k n!}{k! (n+1-k)!} \\ & = \frac{(n+1-k+k)n!}{k! (n+1-k)!} = \frac{(n+1)!}{k! (n+1-k)!} \\ & = \binom{n+1}{k} \end{align*}$$ q.e.d.
-
$\begingroup$ Exactly what I was looking for. Thank you. $\endgroup$– NickCommented Sep 23, 2013 at 20:41
$\begingroup$
$\endgroup$
3
The first summand is if your choice of $k$ elements excludes the first element.
The second summand is if the $k$ elements includes the first element.
-
$\begingroup$ Nice. This answer stays much closer to the definition of the binomial coefficient than any induction proof can ever be. $\endgroup$ Commented Sep 23, 2013 at 19:28
-
-
$\begingroup$ $\binom{n}{k} =$ the number of distinct subsets of cardinality $k$ of a set of $n$ elements. $\endgroup$ Commented Sep 23, 2013 at 19:30