3

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

My start: $$\begin{align}{n-1 \choose k-1} + {n-1 \choose k} &= \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{(k!)(n-k-1)!}\\ &= (n-1)! \times \Big(\frac{1}{(k-1)!(n-k)!} + \frac{1}{(k)!(n-k-1)!}\Big)\\ &= (n-1)! \times \Big(\frac{1}{(k-1)!}\frac{1}{(n-k)!}+\frac{1}{k!}\frac{1}{(n-k-1)!}\Big)\end{align}$$

Now what do I do with what I have inside the parentheses?

Thomas Andrews
  • 177,126
K. Gibson
  • 2,381
  • 2
    the real equality is ${n-1 \choose k-1} + {n-1 \choose k} = {n \choose k}$ – Arnaldo Jan 29 '17 at 19:13
  • Why did you change the question so drastically? You originally asked a specific question about numerators, and now you've revised the question to mean something else entirely. Fixing the times to plus is fine, rephrasing the question to ask something different makes me feel like I wasted effort trying to answer your original question. – Thomas Andrews Jan 29 '17 at 20:58
  • (And your last line just repeats your second-to-last line.) – Thomas Andrews Jan 29 '17 at 21:02

2 Answers2

1

The answer is that $$\frac{k}{k!}=\frac{k}{(k-1)!\cdot k}=\frac{1}{(k-1)!}$$

and similarly:

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

They are just skipping over that step when factoring out $(n-1)!$:

$$\begin{align}\binom{n-1}{k-1}+\binom{n-1}{k}&=(n-1)!\left(\frac 1{(k-1)!(n-k)!}+\frac 1{k!(n-1-k)!}\right)\\ &=(n-1)!\left(\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right)\end{align}$$

Thomas Andrews
  • 177,126
0

The real identity is:

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

and you can prove it like this:

$$\begin{align}{n-1 \choose k-1} + {n-1 \choose k} &= \frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{(k)!(n-k-1)!}\\&= \frac{(n-1)!}{(k-1)!(n-k-1)!}\left(\frac{1}{n-k}+\frac{1}{k}\right)\\ &=\frac{(n-1)!}{(k-1)!(n-k-1)!}\left(\frac{n}{(n-k)k}\right)\\& =\frac{n!}{k!(n-k)!}={n \choose k} \end{align}$$

Thomas Andrews
  • 177,126
Arnaldo
  • 21,342