# A spiffy proof by induction

#### MarkFL

Staff member
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

##### Well-known member
MHB Math Helper
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.