Proving Induction Formula for C(n,k) Using Combinatorial Relations

[evinda]

Hello! :)
Knowing that $\forall k,n \in \mathbb{Z}_{\geq 0} : C(n,0)=1, C(n,k)=0 \text{ for } k>n, C(n,k)=C(n-1,k)+C(n-1,k-1) \text{ for } 1 \leq k \leq n$

show that $\forall 1\leq k \leq n, n \in \mathbb{N}, C(n,k)=\frac{n!}{k!(n-k)!}$

That's what I have done:

For $n=1: C(1,k)=\frac{1}{k!(1-k)!} $ and as $1 \leq k \leq 1 \Rightarrow k=1$,so $C(1,k)=\frac{1}{k!(1-k)!}=1$ $\checkmark$ , because $C(1,1)=C(0,1)+C(0,0)=0+1=1$

We suppose that $C(n,k)=\frac{n!}{k!(n-k)!}, \forall 1 \leq k \leq n$

We want to show that $C(n+1,k)=\frac{(n+1)!}{k!(n+1-k)!}, \forall 1 \leq k \leq n+1$$C(n+1,k)=C(n,k)+C(n,k-1)=\frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}= \cdots =\frac{(n+1)!}{k!(n+1-k)!} \checkmark $

So, the relation $C(n,k)=\frac{n!}{k!(n-k)!} \text{ stands } \forall 1 \leq k \leq n, \forall n \in \mathbb{N}$.

Is this right? In my textbook, to show that $C(n+1,k)=\frac{(n+1)!}{k!(n+1-k)!}, \forall 1 \leq k \leq n+1$,they do it like that:

- $k=n+1$: $C(n+1,n+1)=C(n,n+1)+C(n,n)=1 \text{ and } \frac{(n+1)!}{(n+1)!0!}=1$, so $C(n+1,n+1)=\frac{(n+1)!}{(n+1)!0!}$
- $2 \leq k \leq n: C(n+1,k)=C(n,k)+C(n,k-1)= \cdots \frac{(n+1)!}{k!(n+1-k)!}$
- $k=1: C(n+1,1)=C(n,1)+C(n,0)=\frac{n!}{1!(n-1)!}+1=n+1$

 

[Evgeny.Makarov]

First, I don't understand why you always have the restriction $k\ge 1$ when it was stipulated that $\forall k\in \mathbb{Z}_{\geq 0}$. I think it is simpler (more uniform) to consider nonnegative $k$ and to make the base case for $n=0$.

The textbook is right to consider three cases. In the induction step, we are considering $C(n+1,k)$ where $n\ge0$ and $0\le k\le n+1$. We rewrite it as $C(n,k)+C(n,k-1)$ and then would like to express $C(n,k)$ and $C(n,k-1)$ as fractions, but there are two special cases. First, $k$ may have been equal to $n+1$, in which case $C(n,k)=C(n,n+1)$ is determined not by the general formula, but by the proviso that $C(n,k)=0$ for $k>n$. The second special case is $k=0$, where you can't consider $C(n,k-1)$ (unless you also define $C(n,k)=0$ for $k<0$). The remaining case is the general one, when $C(n,k)$ and $C(n,k-1)$ can be expressed by induction hypothesis.

 

[evinda]

First, I don't understand why you always have the restriction $k\ge 1$ when it was stipulated that $\forall k\in \mathbb{Z}_{\geq 0}$. I think it is simpler (more uniform) to consider nonnegative $k$ and to make the base case for $n=0$.

I was also wondering why there is always the restriction $k\ge 1$,although it is taken that $\forall k\in \mathbb{Z}_{\geq 0}$,but I found it like that in my notes..

The textbook is right to consider three cases. In the induction step, we are considering $C(n+1,k)$ where $n\ge0$ and $0\le k\le n+1$. We rewrite it as $C(n,k)+C(n,k-1)$ and then would like to express $C(n,k)$ and $C(n,k-1)$ as fractions, but there are two special cases. First, $k$ may have been equal to $n+1$, in which case $C(n,k)=C(n,n+1)$ is determined not by the general formula, but by the proviso that $C(n,k)=0$ for $k>n$. The second special case is $k=0$, where you can't consider $C(n,k-1)$ (unless you also define $C(n,k)=0$ for $k<0$). The remaining case is the general one, when $C(n,k)$ and $C(n,k-1)$ can be expressed by induction hypothesis.

Ok,I understand..Thank you very much! :)