Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Original source of question and solution. Question is on the left, answer is on the right.

Question: Notice that all the 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 entire proof by induction will, in a sense, be summed up in a glance by Pascal's triangle.)

Solution: Clearly $\binom{1}{1}$ is a natural number. Suppose that $\binom{n}{p}$ is a natural number for all $p \leq n$. Since

$$\binom{n+1}{p} = \binom{n}{p-1} + \binom{n}{p},\qquad \text{for}\ p \leq n,$$

it follows that $\binom{n+1}{p}$ is a natural number for all $p \leq n$, while $\binom{n+1}{n+1}$ is also a natural number. So $\binom{n+1}{p}$ is a natural number for all $p \leq n + 1$.

I tried to prove it by doing $C(n + 1, k) - C(n, k -1)$ and substituting that for $C(n, k)$. I thought everything would sort of end up equaling $\frac{n!}{k!(n-k)!}$. Thinking about it, I'm not sure why I thought that would prove it to be a natural number. I don't really know how to start. I think I need to prove that $n!$ is divisible by $k!(n-k)!$ but I have no idea how to show that. Seeing as how I already looked at the answer, I would really appreciate an explanation of the answer.

Thanks.

Sorry if the question is vague or whatever, you can fix it if you like.

EDIT: I understand what I did not before. Closure under addition says that if I add two natural number to each other, I get a natural number. So I need to prove that $C(n + 1, k)$ and $C(n, k - 1)$ are natural numbers.

share|improve this question
    
The proof depends on the fact that sums of natural numbers are natural numbers. –  Tunococ Oct 8 '13 at 1:08
    
@Tunococ But I don't understand how I would prove n! and k! are natural numbers? –  Kat Oct 8 '13 at 1:12
    
What do you mean "I don't really know how to start"? Isn't the solution in the image? –  Michael Albanese Oct 8 '13 at 1:14
    
I don't think you need that for this problem. Evaluating the base case manually would be enough. –  Tunococ Oct 8 '13 at 1:15
    
@MichaelAlbanese It is, but I don't understand the solution. –  Kat Oct 8 '13 at 1:34

1 Answer 1

up vote 1 down vote accepted

The solution is by induction. First, establish the base case. Clearly $${1 \choose 1} = \frac{1!}{1!(1-1)!} = \frac{1!}{1!0!} = \frac{1}{1\times 1} = 1$$ is a natural number. Now the inductive step, suppose ${n \choose p}$ is a natural number for all $0 \leq p \leq n$ (we are assuming that every entry the first $n+1$ rows of Pascal's triangle are natural numbers).

For all $0 \leq p \leq n+1$ we have Pascal's rule $${n+1 \choose p} = {n\choose p-1}+{n\choose p}.$$ By the inductive step, both numbers on the right hand side are natural numbers, so ${n+1\choose p}$ is a natural number for $0 \leq p \leq n+1$ (that is, all the entries in the $(n+2)^{\text{nd}}$ row are natural numbers). Note, the proof in the link treats the case $p = n+1$ separately but this isn't necessary as ${n \choose p} = 0$ for $p > n$.

Added Later: The base case here is the second row of Pascal's triangle. It would be better to start with the first row which is ${0\choose 0} = 1$. The reason why knowing ${1 \choose 1} = 1$ is enough to show that every entry in the second row of Pascal's triangle is a natural number is that there is only one other entry, ${1 \choose 0}$, which is $1$.

share|improve this answer
    
Why are both numbers on RHS natural numbers? Is that just given? Where did 0 <= p <= n come from? –  Kat Oct 8 '13 at 2:02
    
They are natural numbers by the inductive step. Are you familiar with induction? I wrote $0 \leq p \leq n$ because ${n \choose p} = 0$ for $p$ outside this range. Note ${n \choose p}$ for $0 \leq p \leq n$ are the $n+1$ entries in the $(n+1)^{\text{st}}$ row of Pascal's triangle. –  Michael Albanese Oct 8 '13 at 2:08
    
Induction is like prove that it's true for least value and then prove it's true for that value + 1? I don't get how any how the inequalities relate to it? –  Kat Oct 8 '13 at 2:19
    
We are doing induction on the row of Pascal's triangle (that is $n$). We prove every element of the first row is a natural number (that's the base case), then we assume every element of the $(n+1)^{\text{st}}$ row is a natural number (the inductive step), and use that to prove every element of the $(n+2)^{\text{nd}}$ row is a natural number. The inequality refers to the elements within a given row. The elements of the $(n+2)^{\text{nd}}$ row, from left to right are ${n+1\choose 0}, {n+1\choose, 1}, \dots, {n+1\choose n}, {n+1\choose n+1}$. Instead of having to check that each of these is a ... –  Michael Albanese Oct 8 '13 at 2:23
    
... natural number individually, we can actually show that ${n+1\choose p}$ is a natural number for any choice of $p$ between $0$ and $n+1$ (that is, any entry in the row). –  Michael Albanese Oct 8 '13 at 2:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.