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! :)
 
Hello, I'm joining this forum to ask two questions which have nagged me for some time. They both are presumed obvious, yet don't make sense to me. Nobody will explain their positions, which is...uh...aka science. I also have a thread for the other question. But this one involves probability, known as the Monty Hall Problem. Please see any number of YouTube videos on this for an explanation, I'll leave it to them to explain it. I question the predicate of all those who answer this...
I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law of Excluded Middle (LEM) p ∨ ¬p is no longer a theorem. My question: aside from the logic formal perspective, is IPL supposed to model/address some specific "kind of world" ? Thanks.
I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
Back
Top