2

Show that if $n$ and $k$ are positive integers, then $ {n+1 \choose k}= \frac{(n+1) {n \choose k-1} }{k}$

I am most likely doing this wrong, but here is what I have:

There exist integer $a$ such that $2a$ is positive;

$ {2a+1 \choose 2a}= \frac{(2a+1) {2a \choose 2a-1} }{2a}$

I did a wonderful job confusing myself. How would one solve this problem?

Bobshark
  • 25
  • You've just rephrased ($\neq$ "proven") the thesis in the special case of $k$ being even and $n=k$, which is far from your first purpose. –  May 18 '15 at 02:24
  • 1
    We show that $k\binom{n+1}{k}=(n+1)\binom{n}{k-1}$. I have $n+1$ different doughnuts, and want to choose $k$ of them to eat for breakfast, and want to choose the one to eat first. Let us count how many ways there are to do this. I can choose the $k$ doughnuts, in $\binom{n+1}{k}$ ways, and then choose which of the $k$ to eat first, giving $k\binom{n+1}{k}$ ways. Or else I can choose the one to eat first from the $n+1$, and choose $k-1$ from the remaining $n$ for the rest of the meal. That gives $(n+1)\binom{n}{k-1}$ ways. Both counts are correct, so they are equal. – André Nicolas May 18 '15 at 02:33

1 Answers1

1

What did you do here with this $a$? I don't get it...

Just use the definition of the binomial coefficient: $$\begin{align*}\binom{n+1}{k} &= \frac{(n+1) \cdots (n+1-k+1)}{k!} \\&= \frac{n+1}{k} \frac{n(n-1)\cdots (n+1-k+1)}{(k-1)!} = \frac{n+1}{k} \binom{n}{k-1} \end{align*} $$

aexl
  • 2,102
  • Thank you for your response aexl! I have a question. How did you know how to approach this type of problem? i attempted it, but then with the 2a idea, I just made a mess. – Bobshark May 18 '15 at 02:31
  • @Bobshark I really just used the defintion of the binomial coefficent and wrote it down. Then you probably see, that you can factor out the term $\frac{n+1}{k}$, and you just need to see that $\binom{n}{k-1}$ is the rest, that is left over... – aexl May 18 '15 at 02:34