5
$\begingroup$

I am an engineering student and am trying to prove the following combinatorics identity in math:

$$\sum_{{m=k}}^{N} C(m,k) = C(N+1, K+1)$$

It was suggested to me to use Proof By Induction so I tried to do this problem.

  • Step 1: Show this identity is true for a specific choice of $N=K$

LHS:

$$\sum_{{m=K}}^{N} C(m,k) = \sum_{{m=k}}^{k} C(m,k) = C(k,k) = 1$$

RHS: $$C(N+1, k+1)$$ $$\text{Substitute } N=k $$ $$C(k+1, k+1) = C(K+1, K+1) = 1$$

  • Step 2: Assume this identity is true for any $N$

  • Step 3: Prove this identity is true for $N=N+1$:

LHS: $$\sum_{{m=k}}^{N} C(m,k)$$ $$\text{Substitute } N=N+1 $$ $$ \sum_{{m=k}}^{N+1} C(m,k)$$

RHS:

$$C(N+1, K+1)$$ $$\text{Substitute } N=N+1 $$ $$C(N+1+1, k+1) = C(N+2, K+1)$$

Now, prove that LHS=RHS, i.e. $$\sum_{{m=k}}^{N+1} C(m,k) = C(N+1+1, k+1) = C(N+2, K+1)$$

We start by showing:

$$\sum_{{m=k}}^{N+1} C(m,K) = \color{red}{\sum_{{m=k}}^{N} C(m,k)} + \sum_{{m=N+1}}^{N+1} C(m,k) = \color{red}{C(N+1, k+1)} + C(N+1, k)$$

Note that $\color{red}{\sum_{{m=k}}^{N} C(m,k)} = \color{red}{C(N+1, k+1)}$ is assumed to be true because of Step 2.

Next, we continue the proof to show: $${C(N+1, k+1)} + C(N+1, k)$$

$$ = \frac{(N+1)!}{(K+1)!(N-K)!} + \frac{(N+1)!}{(K)!(N+1-K)!}$$

Using the idea that in general, $n! = n \cdot (n-1)!$, we write:

$$\frac{(N+1)!}{(K+1)!K!(N-k)!} + \frac{(N+1)!}{K!(N-k)!(N+1-k)}$$

Looking for common terms, we write:

$$\frac{(N+1)!}{K!(N-k)!} \left[ \frac{1}{(K+1)} + \frac{1}{(N+1-k)} \right]$$ $$= \frac{(N+1)!}{K!(N-K)!} \left[ \frac{N+1-K + K+1}{(K+1)(N+1-k)} \right]$$ $$=\frac{(N+1)!}{K!(N-K)!} \left[ \frac{N+2}{(K+1)(N+1-k)} \right]$$

Now, using the following identities based on $n! = n \cdot (n-1)!$ :

$$(N+1)! (N+2) = (N+2)!$$ $$K!(K+1) = (K+1)!$$ $$(N-k)!(N+1-K) = (N+1-k)!$$

We can now write:

$$\frac{(N+1)!}{K!(N-K)!} \left[ \frac{N+2}{(K+1)(N+1-k)} \right] = \frac{(N+2)!}{(K+1)!(N+1-k)!} = C(N+2, K+1)$$

And this is exactly what we were trying to show in Step 3:

$$\text{Original Identity: } $$ $$\sum_{{m=k}}^{N} C(m,k) = C(N+1, k+1)$$ $$\text{Substitute } N=N+1 $$ $$\sum_{{m=k}}^{N+1} C(m,k) = C(N+1+1, k+1) = C(N+2, K+1)$$

Thus, this concludes the proof. Note that Step 3 was not possible to prove without the assumption in Step 2 being a valid assumption (i.e. Step 3 serves to validate the assumption taken in Step 2).

Now, here is where my question begins: My prof told me that my work looks correct (the prof didn't do a full review, but looked at it quickly), but I personally don't agree with this proof. In general, I am confused how mathematical induction proofs work in general.

Here is my attempt to justify this proof:

  • In Step 1, we proved that this identity true for a specific choice of $N=K$, e.g. $N=1$
  • In Step 2, we assumed that this identity is true for any $N$. The way I see it as that suppose we took the case of $N=5$, we use $N=1$ as stepping stones to reach $N=5$
  • But I am confused about Step 3. It seems the main argument is that Step 3 can only be true if our assumption about Step 2 is true.

But isn't the $N+1$ case contained within the $N$ case? If we assume this identity is true for the general $N$ case (as we did in Step 2), are we not forced to accept it must also be true for the $N+1$ case? When we say any $N$, isn't $N+1$ also "any $N$"? Is $N+1$ a general case? Can someone please help me understand how the argument of mathematical induction serves to prove this identity?

$\endgroup$
9
  • 1
    $\begingroup$ In the inductive step, you don't assume it's true for "any $N$". You assume it's true "for some particular $N$". Then you prove this implies it's also true for $N+1$. $\endgroup$
    – Nick
    Apr 20 at 4:28
  • $\begingroup$ I have taken the liberty to retag the question as simply "induction" (the edit is in the queue), since this looks to me as a question about proof by induction in general, the specific problem being just an example. $\endgroup$ Apr 20 at 4:30
  • $\begingroup$ No. That isn't what we are doing at all. Step 1: is to prove that proposition is true for the very first first base case. Step 2: is to prove that for any case where it is true (and at this point we only know of one case where it is true-- the very first base case) it must therefore follow it will be true for the next case. We conclude that as it true for the first case, and for every case where it is true it is true for the next, it logically follows it is true for all (as we can get to them all by starting at the first and going to the next... and the next... and the next...) $\endgroup$
    – fleablood
    Apr 20 at 6:42
  • $\begingroup$ Sometimes... I think it may be better to teach induction this way: Step 1: Admit we have no idea if it is ever true. Step 2: Prove that IF it is ever true for any $k$ then it must also be true for $k+1$ (but admit we still don't know if it is ever true). Step 3: Prove it is sometimes true by proving it is true for $1$. Conclude that since every time it is true for $k$ it is true for $k+1$ and we now know it is true for $1$... it must be true for $1+1$... and for $1+1+1$ .... and $1+1+1+1$ ... and so on. $\endgroup$
    – fleablood
    Apr 20 at 6:52
  • $\begingroup$ Does this answer your question? the concept of Mathematical Induction $\endgroup$ Apr 20 at 7:16

2 Answers 2

3
$\begingroup$

Can someone please help me understand how the argument of mathematical induction serves to prove this identity?

There is no such thing as a step 2 separate from step 3. In ordinary induction, the principle is that a statement is true, i.e. holds, if 1) it is true for the base case (or, base cases, plural, depending on the underlying inductive structure: anyway, let's stick to $\mathbb{N}$ here); and, 2) it is true for the successor case, i.e., if it is true for any $n$, then it is true for $n+1$.

More formally, for $P$ any property on the natural numbers, the induction principle looks like:

$$ (P(0) \land (\forall m \in \mathbb{N}, P(m) \to P(m+1))) \to \forall n \in \mathbb{N}, P(n) $$

so, it is sufficient to prove $P(0)$, the base case, and $\forall m \in \mathbb{N}, P(m) \to P(m+1)$, the successor case, then Modus Ponens from the induction principle gives $\forall n \in \mathbb{N}, P(n)$, though drawing this last conclusion is usually left implicit in informal argument under the heading of "proof by induction".

$\endgroup$
2
$\begingroup$

Seems to me that your confusion comes from the ideia of the induction itself, and not from this particular proof. Hence, I wil try to give you a insight on what is going on in the induction process.

The first step in a proof by induction is to prove the base case, for example, the case $n=1$. Then, as you pointed, our next step is to suppose that our statment is true for some $n \in \mathbb{N}$, and using this assumption we prove that it is true for $n+1$, in other words it is possible to see this process as a kind of "recursion": We know that it is true for $n=1$, and if the statment is true for $n\in\mathbb{N}$ it is true for $n+1$, then it is true for $n=2$, the same reasoning holds for $n=2$, thus it is true for $n=3$, and so on. Hence, it is true for every $n\in \mathbb{N}$.

I hope it helps. If you wanna learn induction in the correct way, I recommend you to take a look at the construction of natural numbers, where induction arises from one of the Peano Axioms.

As pointed by @Julio Di Egidio, this is not the right way to understand induction, but I believe that gives an insight on whats happening, specially for beginners. Once you have this initial intuition, it is important to understand the formal construction of natural number by Peano Axioms.

$\endgroup$
3
  • $\begingroup$ This answer is essentially wrong: the whole point of an induction principle, or of an axiom of infinity, is that "and so on" does not cut it... $\endgroup$ Apr 21 at 5:29
  • $\begingroup$ Thanks for your correction! I made some changes. I avoided talking about logic or Peano Axioms, because it is probably someone who isn't familiar with such things, and I believe that he may benefit from some kind of direction before going in to more formal stuff. $\endgroup$
    – peE_
    Apr 22 at 0:23
  • $\begingroup$ Thank you for your consideration. I have no qualms with the intuition you have provided, I just think the last but crucial step was missing, as for an actual understanding of "induction": the whole point indeed is that we cannot simply go from any finite collection of examples/facts to a universal statement, not for free. -- For the chronicle, "and so on" is common in informal speech/presentation, but it is always just an abbreviation, and always after the fact. $\endgroup$ Apr 22 at 6:09

You must log in to answer this question.

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