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

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Induction
AI Thread Summary
The discussion focuses on proving the induction formula for combinations, specifically that C(n, k) = n! / (k!(n-k)!) for all 1 ≤ k ≤ n. The initial base case for n=1 confirms the formula holds true, and the induction step shows that if the formula is valid for n, it also holds for n+1 by using the recursive relation C(n+1, k) = C(n, k) + C(n, k-1). Participants clarify the reasoning behind restrictions on k, noting that for k=0 and k=n+1, special cases arise where C(n, k) equals zero or is defined differently. The conversation concludes with an acknowledgment of understanding the reasoning behind these restrictions and the induction process.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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$
 
Physics news on Phys.org
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.
 
Evgeny.Makarov said:
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..

Evgeny.Makarov said:
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! :)
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top