Proving the Integer Property of a Fraction Using Mathematical Induction

[MarkFL]

On another forum the following problem was posted:

"Prove with mathematical induction that

$\displaystyle \frac{(n+1)(n+2)...(2n)}{2^n}$

is an integer when $\displaystyle n\in\mathbb{N}$

My solution:

I chose to write the induction hypothesis $\displaystyle P_n$ after looking at the first several statements:

$\displaystyle \frac{(2n)!}{n!}=(2n-1)!2^n$

We easily see that $\displaystyle P_1$ is true, so next I defined:

$\displaystyle \mu(n)=\frac{(2(n+1))!}{(n+1)!}-\frac{(2n)!}{n!}=\frac{(2(n+1))!-(n+1)(2n)!}{(n+1)!}=\frac{(2n)!((2n+2)(2n+1)-(n+1))}{(n+1)!}=$

$\displaystyle \frac{(2n)!}{n!}(2(2n+1)-1)=\frac{(2n)!}{n!}(4n+1)=(2n-1)!2^n(4n+1)$

Now, adding $\displaystyle \mu(n)$ to both sides of $\displaystyle P_n$ there results:

$\displaystyle \frac{(2(n+1))!}{(n+1)!}=(2n-1)!2^n+(2n-1)!2^n(4n+1)$

$\displaystyle \frac{(2(n+1))!}{(n+1)!}=(2n-1)!2^n(4n+2)$

$\displaystyle \frac{(2(n+1))!}{(n+1)!}=(2n-1)!2^{n+1}(2(n+1)-1)$

$\displaystyle \frac{(2(n+1))!}{(n+1)!}=(2(n+1)-1)!2^{n+1}$

We have derived $\displaystyle P_{n+1}$ from $\displaystyle P_n$ thereby completing the proof by induction.

 

[Sudharaka]

Hi everyone, :)

Here's how I would do this problem. Let,

\[P_{n}=\frac{(n+1)(n+2)...(2n)}{2^n}=\frac{(2n)!}{2^{n}n!}\]

We have to show that \(P_{n}\) is an integer for each \(n\in\mathbb{N}=\mathbb{Z}^{+}\cup\{0\}\).

\(P_0=1\) and therefore the statement is true for \(n=0\). Let us assume that the statement is true for \(n=p\in\mathbb{N}\). Then,

\[P_{p}=\frac{(2p)!}{2^{p}p!}\in\mathbb{N}\]

Now,

\begin{eqnarray}

P_{p+1}&=&\frac{(2p+2)!}{2^{p+1}(p+1)!}\\

&=&\frac{(2p)!}{2^{p}p!}\frac{(2p+2)(2p+1)}{2(p+1)}\\

&=&P_{p}(2p+1)\in\mathbb{N}

\end{eqnarray}

Hence the result is true for \(n=p+1\).

\[\therefore P_{n}=\frac{(n+1)(n+2)...(2n)}{2^n}=\frac{(2n)!}{2^{n}n!}\in\mathbb{N}\mbox{ for each }n\in\mathbb{N}\]

Kind Regards,
Sudharaka.