Proving natural numbers in Pascal's Triangle

[Seydlitz]

Homework Statement

Taken from Spivak's Calculus, Prologue Chapter, P.28

b) Notice that all numbers in Pascal's Triangle are natural numbers, use part (a) to prove by induction that $\binom{n}{k}$ is always a natural number. (Your proof by induction will be be summed up by Pascal's Triangle)

Homework Equations

$$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$$

The Attempt at a Solution

I'm quite disoriented to be honest in applying this method of proof in completely new situation like this. Moreover I'm not that comfortable yet with manipulating binomial coefficient, though I've managed to prove (a) using the definition given and I've no problem so far in doing proof by induction to sum of series and the first problem in the chapter.

It's very clear to me that binomial coefficient will only be composed of natural numbers, I just need to build the logical framework in which to prove it. I need your help guys, what is your view to the problem. I'll be very verbose in doing this.

So following the step of the proof by induction that goes like this:
(1) 1 is in A
(2) k+1 is in A, whenever k is in A

Ok so $$\binom{1}{1}$$ is 1 according to the definition. So I assume I've completed step (1).

Now let's try step (2). I can imagine that this equation adds two number one line above, and it is in fact true.
$$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$$
Maybe $$\binom{n}{k}$$ will always give natural number, and it does in fact give 1 if n=k, or if k=0. Suppose k=1, then $$\binom{n}{k-1}$$ will give 1, a natural number. Hence the same will happen to $$\binom{n+1}{k}$$ Better than that, by step (2), I have also shown that binomial coefficient will always give natural number.

Secondly I want to ask what do you think of the problem no.3 in general in this chapter? Is it trivial? Is it normal for beginning students to stumble a bit in this type of question? I'm quite happy actually to be able to finish most of the problems in the preceding chapter before this.

Thank You!

 

[micromass]

This is a pretty tricky problem. It requires a clever induction. Why is this problem different from a regular induction problem? Because here you have two variables $n$ and $k$ instead of one.

So, a right move in the right direction would be to say exactly which statement to prove through induction. I propose the following:

P(n): The binomial coefficient $\binom{n}{k}$ is an integer for any $k$.

So, the first thing we need to do is to prove $P(0)$. This is rather easy.

Next, assume that $\binom{n}{k}$ is an integer for any $k$. Then you need to prove that $\binom{n+1}{k}$ is an integer for any $k$. So take an arbitrary $k$, apply $(a)$ and see what you get.

 

[reenmachine]

Can I ask some questions about this problem here? I'm curious because I'm currently studying this formula...

Don't want to disturb the conversation , if not I will just bring it to my thread.

 

[micromass]

Can I ask some questions about this problem here? I'm curious because I'm currently studying this formula...

I think it's probably better to do it in your own thread.

 

[reenmachine]

No problem!

 

[micromass]

No problem!

Once the OP solved his problem here (or doesn't return), then you can ask questions in this thread. But before that, I think it might be a "hijack" of the thread, and we might give away solutions to the problem.

 

[Seydlitz]

Ok thanks Micromass,

So I think this fact is true. $$\binom{n}{k}$$ will give integers if $k=0$ or if $n=k$. But k must always be $n \geq k$

Applying this to (a), we already accept the second term in the right will give integer. But in order for the first term to be defined then $(n+1) \geq k$ If that's so the second term will give at least $\binom{n+1}{n+1}$. Well this is supposed to give integers no doubt.

So are we there yet? I think we have already proved n and n+1, and k indirectly with n. Though I'm still feeling, I've not grasped all.

 

[micromass]

Ok thanks Micromass,

So I think this fact is true. $$\binom{n}{k}$$ will give integers if $k=0$ or if $n=k$.

Why?

Applying this to (a), we already accept the second term in the right will give integer. But in order for the first term to be defined then $(n+1) \geq k$ If that's so the second term will give at least $\binom{n+1}{n+1}$.

Sorry, I don't get your last sentence. Why can you assume $k=n+1$ ? (you can't by the way).

Also, the induction hypothesis says that $\binom{n}{k}$ is an integer for all $k$ such that $0\leq k\leq n$. Don't forget the crucial word "all".

 

[Seydlitz]

Why?

Sorry, I don't get your last sentence. Why can you assume $k=n+1$ ? (you can't by the way).

Also, the induction hypothesis says that $\binom{n}{k}$ is an integer for all $k$ such that $0\leq k\leq n$. Don't forget the crucial word "all".

They all give 1 according to the raw definition that includes factorial. So it will give integer right?

I'm assuming $n+1$ because it's the max value k can be in (a). I want to show that if that's true then as you said all k below that will give integer. If I just write k, I don't know what (k-1) will give with the first term in the right side.

 

[micromass]

They all give 1 according to the raw definition that includes factorial. So it will give integer right?

I'm assuming $n+1$ because it's the max value k can be in (a). I want to show that if that's true then as you said all k below that will give integer.

I never said that all $k$ below give integers. Why is this true?

 

[Seydlitz]

I never said that all $k$ below give integers. Why is this true?

It is all k right? If k in $\binom{n}{k}$ will give integer then so does where $n+1=k$ in (a). If all k is true then $k-1$ will be true also.

 

[Seydlitz]

Edit: I just realized that I was false. I cannot assume n+1 = k in a. Because that will make k larger than n in the second term in the right.

I am not quite sure how to show the part you say for all k micromass.

I can execute instruction like take the square root of x and materialize that on to paper. But I am not quite sure when you say take arbitrary x. Yes x can take any value. But how do you symbolize it? Does it mean that I've to impose a condition instead in such a way for x to be arbitrary?

 

[Seydlitz]

I'm going to do the second try of the proof.

If $0 \leq k \leq n$, the binomial coefficient $\binom{n}{k}$ is defined by:
$$\binom{n}{k}=\frac{n!}{k!(n-k)!}$$ if $k \neq 0,n$
$$\binom{n}{0}=\binom{n}{n}=1$$ considering that $0!=1$

Clearly the binomial coefficient will give an integer of 1 in case
$$\binom{0}{0}=\binom{n}{n}=1$$
This $\binom{0}{n}$ will only be possible if $n=0$, in that case it will also give 1.

For any $k$ in $0 \leq k \leq n$ I assume $\binom{n}{k}$ is an integer.
Then for any $k$, $\binom{n+1}{k}$ is supposed to be an integer.

We apply the formula (a), which has been proven previously in previous problem, and is assumed to be true.
$$\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$$
Then it is clear that for any $k$ in $0 \leq k \leq n$,$\binom{n+1}{k}$ is an integer and the proof is complete. █

 

[Theorem.]

You have got the right idea here. The main part of your argument is just about spot on. The whole thing just needs a little cleaning up. First, what is your base case?
If you are proving by induction on k for $0\leq k \leq n$ then your base case should be the statement $n \choose 0$ regardless of the value of n, what does this give you? is it a natural number? you have answered these questions but in a somewhat confusing manner. After the base case your argument is a lot clearer and I understand it well.

 

[Theorem.]

I should add something: It is probably better to state that you are doing strong induction here. You need to justify why $n \choose {k-1}$ is also an integer. Your inductive hypothesis also isn't correct. You are assuming the statement holds for all n choose k. You need to say suppose $n \choose k$ is a natural number for all $k<l$ for some natural number l. Then you show that $n\choose l$ is also a natural number using the argument you used. Does this make sense to you?

 

[Seydlitz]

You have got the right idea here. The main part of your argument is just about spot on. The whole thing just needs a little cleaning up. First, what is your base case?
If you are proving by induction on k for $0\leq k \leq n$ then your base case should be the statement $n \choose 0$ regardless of the value of n, what does this give you? is it a natural number? you have answered these questions but in a somewhat confusing manner. After the base case your argument is a lot clearer and I understand it well.

Yes it is indeed missing something, I can't feel it right yet. The task is to prove by induction that $\binom{n}{k}$ is always a natural number. So the base case as suggested by Micromass, is to prove first that $\binom{n}{0}$ is a natural number. According to the definition whatever $n$ is, the value is always 1. 1 is a natural number.

Afterwards I've to prove $\binom{n+1}{k}$ is true for all $k$ in $0 \leq k \leq n$. But this seems to be the problematic part as I cannot get the necessary argument right.

I should add something: It is probably better to state that you are doing strong induction here. You need to justify why $n \choose {k-1}$ is also an integer. Your inductive hypothesis also isn't correct. You are assuming the statement holds for all n choose k. You need to say suppose $n \choose k$ is a natural number for all $k<l$ for some natural number l. Then you show that $n\choose l$ is also a natural number using the argument you used. Does this make sense to you?

Ok it's getting better, but how to justify precisely that $n \choose {k-1}$ is an integer? By going back to the definition? $$\binom{n}{k-1}=\frac{n!}{(k-1)!(n+1-k)!}=\frac{n(n-1)...(n+2-k)}{(k-1)!}$$

I still don't understand the last part entirely, I assume the hypothesis can be proven if I show $\binom{n+1}{k}$ is an integer.

 

[Theorem.]

I still don't understand the last part entirely, I assume the hypothesis can be proven if I show $\binom{n+1}{k}$ is an integer.

Once you have rewritten your induction hypothesis as strong induction, the statement would actually be automatic. EXCEPT I have noticed a flaw that I initially glanced over. If you are doing induction on k, your hypothesis should read as follows (strong induction) :
Assume $n\choose l$ is a natural number for all $l<k$ for some natural number k. Then in order to prove by induction we must show it is also true that $n \choose k$ is a natural number.

you mixed up what you are doing induction on. Are you doing induction on n or k? in your base case it is definitely k, but you seems to switch to n for your induction step. Think this through and decide what works best as MICROmass suggested. I think I may have confused you because I read your induction base step and thought you were doing induction on k but really you were doing induction on n as micromass suggested. I apologize for that.

 

[Theorem.]

To clarify:
Base Case: $0 \choose k$ is a natural number (show this as you did).
Inductive hypothesis: suppose for some natural number l $l \choose k$ is a natural number for all natural numbers k.

Inductive step: Show that then ${l+1} \choose k$ is also a natural number for any k.
You have $$\binom{l+1}{k} =\binom{l}{k-1} + \binom{l}{k}$$
Why is $l \choose {k-1}$ a natural number? HINT: your inductive hypothesis.
Why is $l \choose {k}$ a natural number? HINT: same reasoning.

SORRY for the confusion earlier, i really wasn't sure what you were applying induction to (n or k). This post should fix that. DISREGARD everything i said before!

 

[Seydlitz]

Once you have rewritten your induction hypothesis as strong induction, the statement would actually be automatic. EXCEPT I have noticed a flaw that I initially glanced over. If you are doing induction on k, your hypothesis should read as follows (strong induction) :
Assume $n\choose l$ is a natural number for all $l<k$ for some natural number k. Then in order to prove by induction we must show it is also true that $n \choose k$ is a natural number.

you mixed up what you are doing induction on. Are you doing induction on n or k? in your base case it is definitely k, but you seems to switch to n for your induction step. Think this through and decide what works best as MICROmass suggested. I think I may have confused you because I read your induction base step and thought you were doing induction on k but really you were doing induction on n as micromass suggested. I apologize for that.

No problem Theorem, you're helping me, I should thank you for your time instead.

And yes I'm doing induction on $n$ with arbitrary $k$. I think that is right. I just don't know how to write it down for arbitrary k. Should I just say it like this crudely:

"Okay so this is arbitrary k, believe it, as long as it is not equal or greater than $n$, then I propose $\binom{n}{k}$ to be integer, then I show afterwards using formula that $\binom{n+1}{k}$ with arbitrary k is in fact an integer. Ok I've shown you. Then the proof is complete.

Edit: I have not read post 18 when writing this.

 

[Theorem.]

No problem Theorem, you're helping me, I should thank you for your time instead.

And yes I'm doing induction on $n$ with arbitrary $k$. I think that is right. I just don't know how to write it down for arbitrary k. Should I just say it like this crudely:

"Okay so this is arbitrary k, believe it, as long as it is not equal or greater than $n$, then I propose $\binom{n}{k}$ to be integer, then I show afterwards using formula that $\binom{n+1}{k}$ with arbitrary k is in fact an integer. Ok I've shown you. Then the proof is complete.

I think i clarified this in the last post I managed to sneak in before you posted this. Basically by the inductive hypothesis $\binom{l}{k-1}\in \mathbb{N}$ (we assumed this) and
also $\binom{l}{k}\in \mathbb{N}$ for the same reasoning.
Recall that the assumption was that $\binom{l}{k} \in \mathbb{N}$ for ANY k, so it works for k-1 as well as k. Then the final result is obtained because the sum of two natural numbers is a natural number! As you have suggested

 

[Seydlitz]

I think i clarified this in the last post I managed to sneak in before you posted this. Basically by the inductive hypothesis $\binom{l}{k-1}\in \mathbb{N}$ (we assumed this) and
also $\binom{l}{k}\in \mathbb{N}$ for the same reasoning.
Recall that the assumption was that $\binom{l}{k} \in \mathbb{N}$ for ANY k, so it works for k-1 as well as k. Then the final result is obtained because the sum of two natural numbers is a natural number! As you have suggested

I'm quite overwhelmed by the peculiarity and perhaps the strangeness I encountered. I've never seen or done this before. What you may think is pretty evident is not the same with me. I'm grateful to do this before the university stated.

To realize what micromass and you have suggested, that is take arbitrary $k$, I just need to write, "ok assume the binomial coefficient is true for any natural number $k$". (k in Z) Like that? I almost can't believe it. I mean I don't need to do anything else then? I thought I need to take different complicated cases and do further proofing and other difficult manipulation using the definition so you will believe me.

I can't believe the fact that I only need to say the right things and wording to solve this problem, instead of doing complicated manipulation, like factorizing things, moving symbols left and right, or doing 93x12. It's amazing.

By that reasoning this $\binom{l}{k}\in \mathbb{N}$ and this $\binom{l}{k-1}\in \mathbb{N}$ is integer clearly. Then so does, finally, $\binom{l+1}{k}$

I've also realized the helpfulness of set, it clearly make things less ambiguous in this case, and it should make any proof better. I should probably learn it before doing more complicated proof.

Thank you very much guys, I'll sleep for a while after this.

 

[Theorem.]

can't believe the fact that I only need to say the right things and wording to solve this problem, instead of doing complicated manipulation, like factorizing things, moving symbols left and right, or doing 93x12. It's amazing.
s.

Well, Induction works like this. The base Case is the starting point in an induction argument. It is usually (but not restricted to) $n=1, 0$. We then assume that the statement is true for some natural number $n=k$. Can we use this to show the statement is true for $n=k+1$? if we can, then we can set $k=$our base case (usually 1). since we have shown $k+1$ holds, the statement must also be true for $k+1=1+1=2$. We now set $k=2$ and using our induction step, we get the statement holds for k=3. The point of induction is that you show that the statement holds for some arbitrary natural number, it must also hold for the next natural number in line.

Since part of every induction proof is to show the statement in question is true for a base case, you can apply the above bolded statement to the base case repeatedly to get that it must be true for all natural numbers!

EDIT: so when you really think about induction proofs are only natural. If we know that if a statement holds for a specific number it holds for the next number, an we know the statement holds for 1. Then it must hold for 2. Then it must also hold for 3 ... and so forth. yes math can make you feel quite powerful, but it is important to understand what is going on here. It isn't just magical tricks, these are logical statements. Maybe try reading a bit more on induction if you don't fully understand why induction works the way it does in this case and then consider it again :) but get some rest first!