# Mathematical induction!

• Nov 15th 2012, 10:45 AM
Eizei
Mathematical induction!
Hi,
I could use some help with my proving. The assignment goes as follows:

"Prove with mathematical induction that

((n+1)(n+2)...(2n)) / 22

is a whole number with all values of n"

I know the basic principle of induction but I can't see how can I show the "n+1" -step.

Please excuse my inaccurate expressions, my native language is finnish :) I would REALLY appreciate the help!
• Nov 15th 2012, 11:34 AM
emakarov
Re: Mathematical induction!
Do you mean that (n+1)(n+2)...(2n) is divisible by 4? This is obvious because 2n is even and, since the number of factors is ≥ 3 for n ≥ 3, there is another even factor.
• Nov 15th 2012, 11:55 AM
HallsofIvy
Re: Mathematical induction!
What, exactly, do you mean by ((n+1)(n+ 2)...(2n)) if n= 1? I see that, for example, if n= 3, then this is 4(5)(6) but what about n= 1? Is this "2" or "2(2)"? If the first, which is what I would think because 1+ 1= 2(1), the statement is not true: $(1+ 1)/ 2^2= 1/2$

But for n= 2, this is 3(4)(4) which is divisible by $2^2= 4$ because it has a factor of 4. If $n\ge 4$, there are four consecutive numbers in that so at least one is divisible by 4.
• Nov 16th 2012, 01:18 AM
Eizei
Re: Mathematical induction!
Okay so here is a hopefully a bit better presentation of the assignment:

"Prove with mathematical induction that

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

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

First time using latex...

• Nov 16th 2012, 01:20 AM
Eizei
Re: Mathematical induction!
... and theres minor error in my first post. sorry bout that
• Nov 16th 2012, 02:46 AM
MarkFL
Re: Mathematical induction!
I chose to write the induction hypothesis $P_n$ after looking at the first several statements:

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

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

$\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)!}=$

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

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

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

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

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

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

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