2

It's a homework problem. Prove $\binom{n}{k} = 0$ for $n = 0, 1, ... , k-1$

I think induction needs to be used, I can do $n = 0$ (and $n = 1$ since our teacher likes us to do the first two), but $n = m$ confuses me... Do you have to limit it so $m < k-1$ or something?

Sorry that's a brief explanation...

Edit: $\binom{n}{k} = \frac{n(n-1)...(n-k+1)}{1*2*...*k}$, also $\binom{n}{0} = 1$

I think what I am trying to ask is how do I approach this problem? You can prove the base case very easily, but I am not sure what the inductive hypothesis would be exactly, because $n$ is not $0,1,...,\infty$, but rather $0,1,...,k-1$ A hint on that might point me in the right direction?

dardeshna
  • 627
  • 2
    What is your definition of $(-1)!$? –  Sep 15 '15 at 01:54
  • 4
    More to the point, what is your definition of ${n\choose k}$? – vadim123 Sep 15 '15 at 01:56
  • 1
    This is a weird question because usually it's defined to be $0$ when $n<k$, so you need to be explicit about your definition. –  Sep 15 '15 at 01:58
  • Hopefully the edit makes a little more sense. – dardeshna Sep 15 '15 at 02:16
  • Could you give us what $n(n-1)\dots(n-k+1)$ is supposed to mean when $n<k$? How many times are we multiplying? –  Sep 15 '15 at 02:19
  • 4
    With the definition provided, do you even need induction? Your definition says that $\binom{n}{k}$ is proportional to $(n-l)$ for $l=0,1,\dots, k-1$, so for $0\leq n \leq k-1$, $\binom{n}{k}=0$. – Moya Sep 15 '15 at 02:22
  • 1
    If you take the definition of $\binom{n}{k}$ as being "the number of ways to select $k$ objects from a set of $n$ objects", then you can just make the argument that one cannot select more objects than the total number available. Some might consider that being cheeky, however. – 727 Sep 15 '15 at 02:31
  • I'm no mathematician, but I'm curious. It seems to me that having $\binom{n}{0}=1$ as part of the definition without saying anything about $n = 0$ or $n < k$ is a bit disingenuous. How do you prove $\binom{0}{k} = 0$? Because there's an $n$ up there? Then how about $\binom{0}{0}$? – muru Sep 15 '15 at 02:50
  • 2
    For $n<k$, we still have

    $$\binom{n}{k}=\frac{n(n-1)(n-2)\cdots (n-k+1)}{k!}$$which is obviously $0$ by inspection.

     – Mark Viola Sep 15 '15 at 02:52
  • @avid19 $$n(n-1)\cdots (n-k+1)=\prod_{j=0}^{k-1}(n-j)=\left(n\right)_k$$, where $\left(n\right)_k$ is the falling pocchammer symbol. – Mark Viola Sep 15 '15 at 02:56
  • I think you can limit it to where $k > n, k \in \mathbb{N}$, otherwise $\binom{n}{k} = 1$. – Obinna Nwakwue May 27 '17 at 23:50

0 Answers0