We will prove that:

\(\dbinom{n}{k} = \displaystyle \prod_{i=1}^{k} \frac{n-i+1}{i}\)

\(\forall\) \(k \in \mathbb{N}\), \(k \leq n\)

Proof #1: As the reader may guess, we will use induction to prove this. We establish a base case as \(k=1\):

\(\dbinom{n}{1} = \displaystyle \prod_{i=1}^{1} \frac{n-i+1}{i}\)

\(\Rightarrow\) \(\frac{n!}{1!(n-1)!} = n\)

\(\Rightarrow\) \(n=n\)

The base case clearly holds. Now we establish the inductive case as \(n=\alpha\):

\(\dbinom{n}{\alpha} = \displaystyle \prod_{i=1}^{\alpha} \frac{n-i+1}{i}\)

\(\Rightarrow\) \(\frac{n-\alpha}{\alpha +1} \dbinom{n}{\alpha} =\frac{n-\alpha}{\alpha +1} \displaystyle \prod_{i=1}^{\alpha} \frac{n-i+1}{i}\) (By hypothesis)

\(\Rightarrow\) \(\frac{n-\alpha}{\alpha +1} \dbinom{n}{\alpha} =\displaystyle \prod_{i=1}^{\alpha + 1} \frac{n-i+1}{i}\)

\(\Rightarrow\) \(\frac{n!(n-\alpha)}{(\alpha +1)!(n-\alpha)!} =\displaystyle \prod_{i=1}^{\alpha + 1} \frac{n-i+1}{i}\)

\(\Rightarrow\) \(\frac{n!}{(\alpha +1)!(n-(\alpha+1))!} = \displaystyle \prod_{i=1}^{\alpha + 1} \frac{n-i+1}{i}\)

\(\Rightarrow\) \(\dbinom{n}{\alpha+1} = \displaystyle \prod_{i=1}^{\alpha + 1} \frac{n-i+1}{i}\)

So we may conclude that the statement is true for \(k=1\) and if it is true for some \(k=\alpha\), then it must be true for \(k=\alpha+1\). The proof follows by induction.

QED

Proof #2: We will now offer an alternative proof, which is actually just a simple direct derivation:

\(\dbinom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{\displaystyle \prod_{i=0}^{n-1} (n-i)}{\displaystyle \prod_{i=0}^{k-1} (k-i) \left( \displaystyle \prod_{i=0}^{n-k-1} (n-k-i) \right)}\)

\( = \frac{\displaystyle \prod_{i=1}^k (n-i+1)}{k!} = \frac{\displaystyle \prod_{i=1}^k (n-i+1)}{ \displaystyle \prod_{i=1}^k i }\)

\( = \displaystyle \prod_{i=1}^k \frac{(n-i+1)}{i} \) Because multiplication is commutative.

Which is the intended result.

QED.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestI've been scrolling through your profile the complete morning now and am finding some really nice notes. Thanks for sharing them!

Log in to reply

Thanks!

Log in to reply

Nice note@Ethan Robinett

Log in to reply

Thanks appreciate it!

Log in to reply

Hey nice proofs! :) I did the Inductive one but didn't think of using a direct one

Log in to reply

Thanks! Yeah after I did the induction, I figured there was probably a way to directly show it, given that factorials are just products by definition, I thought the second one was pretty interesting

Log in to reply

I like the way the induction is used.

Log in to reply

Thanks man

Log in to reply