Chapter 12.6, Problem 54E

To determine

To Prove: $\left(\begin{array}{c}n\\ r\end{array}\right)$ is an integer for all natural numbers $n$ and for $0\le r\le n$ .

Explanation of Solution

Given information:

Use Mathematical induction to prove the above-mentioned formula.

Concept used:

1.By using Mathematical induction technique we need to prove that this formula holds True for all the natural numbers. The first step is to prove True for $n=1$ .

2.Second step by using induction hypothesis of mathematical induction we assume for $n=k$ given formula is True.

3.Third step is we need to prove that above formula is True for $n=k+1$ by using formula is True for $n=k$ .

Proof:

First, we need to prove the above formula is True for $n=1$ .

Given formula is

  $\left(\begin{array}{c}n\\ r\end{array}\right)$ is an integerfor all the natural numbers $n$ and for $0\le r\le n$ .

Put $n=1$

Then $r=0$ or $r=1$

Take $r=1$

We get

  $\begin{array}{l}\left(\begin{array}{c}n\\ r\end{array}\right)=\left(\begin{array}{c}1\\ 1\end{array}\right)\\ \Rightarrow \left(\begin{array}{c}n\\ r\end{array}\right)=\frac{1!}{\left(1-1\right)!1!}\\ \Rightarrow \left(\begin{array}{c}n\\ r\end{array}\right)=\frac{1!}{\left(0\right)!1!}\\ \Rightarrow \left(\begin{array}{c}n\\ r\end{array}\right)=1\end{array}$ .

It True for $n=1$ .

Let us assume it is True for $n=k$

So

  $\left(\begin{array}{c}k\\ r\end{array}\right)$ is an integer for all $0\le r\le k$ .

We need to prove it is True for $n=k+1$

We know that,

  $\left(\begin{array}{l}n\\ r-1\end{array}\right)+\left(\begin{array}{l}n\\ r\end{array}\right)=\left(\begin{array}{l}n+1\\ r\end{array}\right)$

  $\Rightarrow \left(\begin{array}{l}k\\ r-1\end{array}\right)+\left(\begin{array}{l}k\\ r\end{array}\right)=\left(\begin{array}{l}k+1\\ r\end{array}\right)$ ---------(1)

Since $\left(\begin{array}{l}k\\ r\end{array}\right)$ is an integer for $0\le r\le k$ .

So $\left(\begin{array}{l}k\\ r-1\end{array}\right)$ is also an integer.

Therefore,

From equation (1),

  $\Rightarrow$ integer + integer = $\left(\begin{array}{l}k+1\\ r\end{array}\right)$

Since sum of two integers is also an integer.

Therefore, $\left(\begin{array}{l}k+1\\ r\end{array}\right)$ is also an integer.

  $\left(\begin{array}{c}n\\ r\end{array}\right)$ is True for $n=k+1$ .

And hence the proof by Mathematical induction.