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.
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Back
Top