3
$\begingroup$

I want to show that : $$\binom{n}{k}+\binom{n}{k-1} = \frac{(n+1)!}{k!(n+1-k)!}$$

Here is my proof : $\forall 1\leq k\leq n$ :

$$\begin{align} \binom{n}{k}+\binom{n}{k-1} &= \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n+1-k)!} \tag1 \\[4pt] &=\frac{n!(n+1-k)}{k!(n+1-k)!} +\frac{n!k}{k!(n+1-k)!} \tag2 \\[4pt] &= \frac{n!(n+1-k+k)}{k!(n+1-k)!} \tag3 \\[4pt] &=\frac{(n+1)!}{k!(n+1-k)!} \tag4 \\[4pt] &=\binom{n+1}{k} \tag5 \end{align}$$

And normally I avoided problem of factorial not defined since $k\leq n$.

Do you think this is correct ?

Thank you a lot

EDIT : Thank you everyone and especially Riemann and Jean-Claude Arbault since it is not defined for $k=0$...

$\endgroup$
4
  • 4
    $\begingroup$ I think it's fine, except that you should assume $k\ge 1$, because $\binom{n}{k-1}$ may not be defined if $k=0$. $\endgroup$
    – Riemann
    Nov 23, 2022 at 8:15
  • $\begingroup$ this looks good to me $\endgroup$
    – adrien_vdb
    Nov 23, 2022 at 8:16
  • $\begingroup$ Your title should probably be ${n\choose k}+{n\choose k-1}={n+1\choose k}$ as that's the more meaningful expression. But your proof, which is just arithmetical manipulation, is just fine. $\endgroup$
    – fleablood
    Nov 23, 2022 at 20:40
  • $\begingroup$ It's done ! Thank you ! $\endgroup$
    – coboy
    Nov 23, 2022 at 21:31

1 Answer 1

3
$\begingroup$

Yes it's correct $$\binom{n}k+\binom{n}{k-1}$$ $$=\frac{n!}{(n-k)!\cdot k!}+\frac{n!}{(n+1-k)!\cdot (k-1)!}$$ $$=\frac{n!}{(n-k)!\cdot (k-1)!}\left(\frac{1}{k}+\frac{1}{n+1-k}\right)$$ $$=\frac{n!}{(n-k)!\cdot (k-1)!}\left(\frac{n+1-k+k}{k(n+1-k)}\right)$$ $$=\frac{n!(n+1)}{(n+1-k)!\cdot k!}$$ $$=\frac{(n+1)!}{(n+1-k)!\cdot k!}$$ $$=\binom{n+1}{k}$$ Here we made the assumption that $k\ne 0$

$\endgroup$
10
  • 1
    $\begingroup$ One must be careful with boundaries. (a well-known trap for induction proofs, for instance, though it's not the case here) As stated by Rieman above, there is an error in the proof. For $k=0$, $n\choose k-1$ is not defined. And even if you care to define it to be zero, $(-1)!$ is not defined, and there is no way you are going to define it to be zero. $\endgroup$ Nov 23, 2022 at 10:12
  • $\begingroup$ It's understood that $k\ne0$ $\endgroup$
    – Vanessa
    Nov 23, 2022 at 10:16
  • $\begingroup$ Not in the question. And it's a proof verification question, so you have to consider what is correct, and what is not. I.e., when you write "yes it's correct", you are wrong ;-) $\endgroup$ Nov 23, 2022 at 10:18
  • $\begingroup$ Btw isn't $(-1)!=(0-1)!=\Gamma(0)?$ $\endgroup$
    – Vanessa
    Nov 23, 2022 at 10:18
  • $\begingroup$ @Jean-ClaudeArbaut i see...thanks $\endgroup$
    – Vanessa
    Nov 23, 2022 at 10:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .