MHB Proving the Integer Property of a Fraction Using Mathematical Induction

  • Thread starter Thread starter MarkFL
  • Start date Start date
  • Tags Tags
    Induction Proof
AI Thread Summary
The discussion focuses on proving that the expression (n+1)(n+2)...(2n)/2^n is an integer for natural numbers n using mathematical induction. The initial step confirms that the base case P_1 holds true. The induction hypothesis is established, and the proof progresses by demonstrating that if P_p is true, then P_{p+1} also holds. The final derivation shows that the expression can be simplified to confirm its integrality for all n in the natural numbers. The proof is successfully completed, affirming the integer property of the fraction.
MarkFL
Gold Member
MHB
Messages
13,284
Reaction score
12
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.
 
Mathematics news on Phys.org
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.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Is it possible to arrange six pencils such that each one touches the other five? If so, how? This is an adaption of a Martin Gardner puzzle only I changed it from cigarettes to pencils and left out the clues because PF folks don’t need clues. From the book “My Best Mathematical and Logic Puzzles”. Dover, 1994.
Back
Top