How to prove that all of pascal's triangle is composed of integers.

Question

I want to prove that all of n choose k values, i.e. pascal's triangle values are integers.

It is pretty obvious, since it is a recursive definition with each term being the sum of its preceding elements. And the base elements are 1 and 1 if I am not mistaken.

How can I formally prove this though?

Answer 1

You’ve pretty much sketched the proof in your question. You can prove it by induction on the row number. Row $0$ contains only a $1$, so every entry in row $0$ is an integer. Suppose that every entry in row $n$ is an integer. The first and last entries in row $n+1$ are $1$ by definition, so they’re integers. Every other entry in row $n+1$ is the sum of two entries in row $n$; by the induction hypothesis they are integers, and the sum of two integers is an integer, so every entry in row $n+1$ is an integer. The result now follows by induction.

Answer 2

Here is another way: It is easy to prove by induction that the coefficients of the polynomial $(1+x)^n$ are integers. Since $(1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k$, and the coefficients are unique it follows that $\binom{n}{k}$ is an integer.