0

I'm a high school graduate, who has started doing Spivak's Calculus, for fun. I was struggling a bit with a certain question on proving the above stated fact using Principle of Mathematic Indutction. I came up with the following proof, but am unsure since it is very unlike previous PMI questions I've done.

$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k - 1}$$ For $n = 1$ $$\binom{1}{k} = \binom{1}{0}\space or \space \binom{1}{1} = 1$$ Therefore $\binom{n}{k}$ is a natural number when $n = 1$.

Assumption: $\binom{n}{k}$ is a natural number for all $k\in \{1, 2, \dots,n\}$ $$\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}$$. $\binom{n}{k}$ is a natural number from the previous argument. The same applies to $\binom{n}{k - 1}$. The remaining two possible values of $k$ are $n + 1$, $0$. $$\binom{n+1}{0} = \binom{n+1}{n+1} = 1$$. Therefore all the possible values of $\binom{n + 1}{k}$ are natural numbers. Therefore, $\binom{n}{k}$ is always a natural number by induction.

Shahe Ansar
  • 157
  • 1
    With this rule, it is clear that Pascal's triangle can be constructed upto any level and the entries must all be positive integers. So, you can consider it to be a proof. – Peter Apr 10 '17 at 11:07
  • You seem to be confusing induction on $n$ with induction on $k$. How are the binomial coefficients defined, is it a factorial definition or another? Edit: Sorry, I can see you are actually inducting on $n$ now, I got confused by the wording. – Arby Apr 10 '17 at 11:07
  • State your hypotheses more clearly at the beginning. – marty cohen Apr 10 '17 at 11:09
  • @Arby I was unable to find a way to properly induct on $k$, which is why I resorted to $n$, but then $k$ has to be accounted for, so I resorted to proving that $\binom{n + 1}{k}$ was an integer for all possible $k$ assuming that $\binom{n}{k}$ was an integer for all $k$. If you have any suggestions on how to improve the above mentioned proof, please mention them/ – Shahe Ansar Apr 10 '17 at 11:12
  • We need to know what can be assumed. "Given this definition of binomial coefficients, prove they are always natural numbers." – Arby Apr 10 '17 at 11:13
  • By the way, I was wrong when I initially said you inducted wrongly on $k$. You didn't say something like "Assume the proposition is true for all natural numbers up to $n$, so I got confused. My bad. – Arby Apr 10 '17 at 11:16
  • @Arby I don't quite understand your previous comment. Could you elaborate? – Shahe Ansar Apr 10 '17 at 11:18
  • I mean you inducted on $n$ correctly. – Arby Apr 10 '17 at 11:21
  • I got confused initially by your wording in the second induction step. Perhaps a better way to phrase it would be "Assume for every natural number up to $n$, $\binom n k$ is a natural number for all $k\in {1, 2, \dots,n}$". If you have already proved the addition property you have used, $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k - 1}$, the rest of the proof looks good to me. – Arby Apr 10 '17 at 11:31
  • 1
    @Arby Oh, got it. Thanks – Shahe Ansar Apr 10 '17 at 11:32

1 Answers1

1

Structurally your proof is correct(*). However what's missing is the definition of the binomial coefficient, that is what do $\binom{n}{k}$ mean? There's two ways to do that (perhaps more). One is to define it using the pascal triangle rule (recursive definition):

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

With that definition your proof is straight forward as it relies on these identities.

Another way to define binomial coefficients is to define it as

$$\binom{n}{k} = {n!\over k! (n-k)!}$$

with this definition you must prove that the required identities hold, especially that $\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$. However that is quite straight forward:

$$\binom{n}{k} + \binom{n}{k-1} = {n! \over k! (n-k)!} + {n!\over (k-1)!(n-k+1)!} \\ = {n! (n-k+1) \over k! (n-k+1)!} + {n!k\over k!(n-k+1)!} \\ = {n! (n-k+1) + n!k\over k! (n-k+1)!} \\= {(n+1)!\over k! (n-k+1)!} = \binom{n+1}{k}$$

(*) well almost, you have that it's allowed for $n=0$ in $\binom{n}{k}$, so you should have included the fact that $\binom{0}{0} = 1$ is a natural number.

skyking
  • 16,654