1
$\begingroup$

While going through Spivak, i encountered the problem of proving that every number in pascal's triangle is positive via induction. Another property that was proven before this was $\left( {\begin{array}{*{20}c} n+1 \\ k \\ \end{array}} \right)=\left( {\begin{array}{*{20}c} n \\ k-1 \\ \end{array}} \right)+\left( {\begin{array}{*{20}c} n \\ k \\ \end{array}} \right)$

I figured that i can do this by proving that if the nth row consists of natural numbers, so must the (n+1)th row. I also proved that the first row consists of natural numbers through simple evaluation of $({\begin{array}{*{20}c} 1 \\ 1 \\ \end{array}})$

The problem is, how do i prove the part about how the nth row being natural implies that the (n+1)th row is also natural? I can deduce that every element in the (n+1)th row is a sum of two elements of the nth row, and hence, should be the sum of two natural numbers, i.e a natural number of their own. But this is just an english statement and does not sound like a proper proof to me. How do i state this properly?

$\endgroup$
4
  • 2
    $\begingroup$ Proof by induction. $\endgroup$
    – fleablood
    Commented Jan 14, 2016 at 9:03
  • 1
    $\begingroup$ The induction hypothesis will state that a row of the triangle holds naturals only; you will also need the fact that the values at both endpoints are $1$. $\endgroup$
    – user65203
    Commented Jan 14, 2016 at 9:16
  • $\begingroup$ "The sum of two natural numbers is a natural number" is a true statement which you can surely take without proof except in a context where you are defining the rational numbers. (Addition within the rationals is defined using addition and multiplication within the natural numbers: $a/b +_{\mathbb{Q}} c/d = (ad +_{\mathbb{Z}} bc)/bd$, etc. Just about the first thing you would then prove is that the natural embedding of the naturals into the rationals preserves addition.) $\endgroup$
    – HTFB
    Commented Jan 14, 2016 at 9:48
  • $\begingroup$ In other words, your proof method and statement are fine. As Yves says, you need to take care at the endpoints of a row. $\endgroup$
    – HTFB
    Commented Jan 14, 2016 at 9:52

2 Answers 2

Reset to default
1
$\begingroup$

Base:

$$\binom00=1\in\mathbb N.$$

Induction hypothesis:

$$\forall k: 0\le k\le n:\binom nk\in\mathbb N.$$

Induction step: (mind the strict inequalities)

$$\forall k: 0< k<n+1:\binom {n+1}k=\binom n{k-1}+\binom nk\land\binom n{k-1}\in\mathbb N\land \binom nk\in\mathbb N\\\implies\\ \forall k: 0< k<n+1:\binom {n+1}k\in\mathbb N.$$

As in addition $$\binom{n+1}0=\binom{n+1}{n+1}=1\in\mathbb N,$$ we have

$$\forall k: 0\le k\le n+1:\binom{n+1}k\in\mathbb N.$$

Then by induction

$$\forall n,k:n\ge0,0\le k\le n:\binom nk\in\mathbb N.$$

Note that the Base is actually never used in the induction step, as the endpoints are handled differently. We just added it for the property to hold even with $n=0$.

$\endgroup$
10
  • $\begingroup$ I'm sorry for posting this so late, but why is the first column assumed to be zero? I.e, why does the column count start from zero? Especially when the row count doesn't? Also, i tried to compare with a answer book for some reference, and the author there considered both (1,0) and (1,1) to prove that the base case is correct. I don't think that was the correct approach, was it? $\endgroup$
    – Aayush Agrawal
    Commented Jan 14, 2016 at 13:39
  • $\begingroup$ @AayushAgrawal: indeed, both $(1,0)$ and $(1,1)$ are required. But one can also use $(0,0)$. Fixing. $\endgroup$
    – user65203
    Commented Jan 14, 2016 at 14:40
  • $\begingroup$ But why are we even considering zero? The 0th row and the 0th column don't make any sense unless we're starting the row and column count from zero. $\endgroup$
    – Aayush Agrawal
    Commented Jan 14, 2016 at 17:20
  • $\begingroup$ @AayushAgrawal: the triangle is nicer with its tip. $\endgroup$
    – user65203
    Commented Jan 14, 2016 at 17:23
  • $\begingroup$ Yes i understand that, but why is the tip not (1,1)? There should be only one element at the top, and i'm guessing that we should start the count from 1? Why do we consider both (1,0) and (1,1)? $\endgroup$
    – Aayush Agrawal
    Commented Jan 14, 2016 at 18:00
0
$\begingroup$

The first row consist of $R_1(1) = 1$;

Each row $R_n$ consists of terms $R_n(i); i = 1...n$ where $R_n(1) = R_{n-1}(1)$, $R_n(i) = R_{n-1}(i) + R_{n-1}(i -1);i>1$ and $i < n$ and $R_n(n) = R_{n-1}(n-1)$.

Initial step: $R_1 = \{1\}$ consist of only natural numbers.

Induction step: If $R_n$ consists of only natural numbers then $R_{n+1}$ consists of only natural numbers.

Proof: $R_{n+1}(1) = R_n(1) \in \mathbb N$. $R_{n+1}(n+1) = R_n(n) \in \mathbb N$. And for all others $R_{n+1}(i)= R_{n}(i) + R_{n}(i -1)$ which is the sum of two natural numbers and so a natural number.

So $R_{n+1}$ consists of natural numbers.

Hence via induction we can conclude all rows consists of only natural number.

$\endgroup$
3
  • $\begingroup$ Your indexing scheme is not compatible with the usual definition (that of the OP). $\endgroup$
    – user65203
    Commented Jan 14, 2016 at 9:52
  • $\begingroup$ Meh, probably not. But the point I wanted was to show that if s/he had proven his/her results then he is done, as a proof by induction is valid. And isn't it compatible? $R_n(k) = {n \choose k}$, doesn't it? I didn't want to use ${n \choose k}$ because I didn't want to prove that it's definition was compatible with the property of Pascal triangle which is a distraction from the question asked. $\endgroup$
    – fleablood
    Commented Jan 14, 2016 at 10:46
  • $\begingroup$ With the "standard" definition of $R_n(k)$, there are $n+1$ values per row, you drop $R_n(0)$ and $R_{n+1}(1)\ne R_n(1)$. $\endgroup$
    – user65203
    Commented Jan 14, 2016 at 11:01

You must log in to answer this question.

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