3

I am working on this proof from my book, and I believe to have solved it. However, proof by inductions still feel funny to me and this question uses more than one variable, so I'm not sure if I have done it correctly. I could not find the answer on the internet, so here I go:

Question

Prove by induction that $\binom{n}{k}$ is always a natural number in Pascals triangle.

My Assertion

$\binom{n}{k}$ will always be a natural number if every $k$ in $[0...n]$ for $\binom{n}{k}$ is a natural number, where n is the row and k is the index.

My Attempted Proof

$$P(x) = \binom{x-1}{k}, k = 0...(x-1)$$

$$P(1) = \binom{0}{0} = 1$$

$$P(z) = \binom{z-1}{k} = \frac{(z-1)(z-2)...((z-1) - k + 1)}{k!}$$

$$P(z+1) = \binom{(z+1)-1}{k} = \frac{z(z-1)...(z-k+1)}{k!}$$

As shown above, $P(1) = 1$ is in $A$ and $P(z+1)$ is in $A$ whenever $P(z)$ is in $A$.

Is this correct? Proof by inductions still seem funny to me, and I couldn't find the answer on the internet nor in my book.

EDIT: The triangle shown in the book is like this one: enter image description here

Jason
  • 3,563
  • What proof to use depends on how one defines Pascal's Triangle. If one does it in the classical way, it is defined essentially by the recurrence $P(n,k)=P(n-1,k-1)+P(n-1,k)$. – André Nicolas Jun 17 '14 at 20:19
  • So then for P(z) and P(z+1) I would have to sum all of P(n, k) from k = 0 to k = n? (if I count the rows starting from 0) Also, would I count the rows starting from 0 or from 1, or does it not matter? – Jason Jun 17 '14 at 20:24
  • If one approaches it this way, then for the induction step one proves that if $P(n-1,w)$ is an integer for all $w$, then $P(n,w)$ is an integer for all $w$. One only has to add two things. – André Nicolas Jun 17 '14 at 20:28
  • But don't we have to check P(n, w) for all w values to see if they are an integer? I.e. start from w = 0, then w = 1, then w = 2 , then w = 3, all the way to n? – Jason Jun 17 '14 at 20:33
  • Let $A(n)$ be the assertion that for all $w$, the $w$-th element in the $n$-th row is an integer. We want to prove that $A(n)$ holds for all $n$. You can show using the Pascal identity I referred to above that if $A(n-1)$ holds, then $A(n)$ holds. Because we are using the Pascal identity, we need to treat separately the first element of row $n$, which by definition is $1$, an integer. – André Nicolas Jun 17 '14 at 20:41

1 Answers1

2

Hint: Prove by induction that $\displaystyle\binom{n+1}{k+1}=\binom nk+\binom n{k+1}$, and use $\displaystyle\binom00=1\in\Bbb N$ and $\displaystyle\binom nm=0$ if $m>n$.

Berci
  • 90,745