Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to prove that $\dfrac{(2n)!}{2^n}$ is integer. So I have tried it by induction, I have took $n=1$, for which we would have $2/2=1$ is integer. So for $n=k$ it is true, so now comes time to proof it for $k+1$, $(2(n+1))!=(2n+2)!$, which is equal to $$1 \times 2 \times 3 \times \cdots \times (2n) \times (2n+1) \times (2n+2),$$ second term would be $$2^{n+1}=2 \times 2^n$$ Finally if we divide $(1 \times 2 \times 3 \times \cdots \times (2n) \times (2n+1) \times (2n+2)$ by $2^{n+1}=2 \times 2^n$,and consider that,$(2n)!/(2^n)$ is integer, we get $(2n+1) \times (2n+2)/2=(2n+1) \times 2 \times (n+1)/2$, we can cancel out $2$, we get $(2n+1)(n+1)$ which is definitely integer. I am curious this so simple? Does it means that I have proved correctly?

share|improve this question
4  
There is no problem in your proof. –  Aang Jun 29 '12 at 16:05
7  
Actually we can prove more. We can show that $$ \frac{(2n)!}{n!2^n}$$ is an odd integer. –  sos440 Jun 29 '12 at 16:28
2  
The only change I would make is to simplify the proof by writing $(2n+2)!= (2n+2)(2n+1)(2n)!$. –  Thomas Andrews Jun 29 '12 at 16:31
    
@sos440,for $n=1$ it is clear because $2/2=1$ is an odd number,for $n+1$,we have $(2*n+1)/(2*(n+1))$,but how can we divide odd number by even? –  dato datuashvili Jun 29 '12 at 16:44
2  
I think you missed $2n+2$ factor in the numerator. Note that $$ \frac{(2(n+1))!}{(n+1)!2^{n+1}} = \frac{(2n+2)(2n+1)}{(n+1)\cdot 2} \frac{(2n)!}{n!2^n} = (2n+1) \frac{(2n)!}{n!2^n}.$$ Thus you can apply induction again. –  sos440 Jun 29 '12 at 16:50

3 Answers 3

up vote 11 down vote accepted

Yes, you have proved it correctly. Indeed the proof is not difficult. If you need to do a formal induction, fine. But the result becomes obvious if you just expand, say, $(2\cdot 5)!$. It is clear that you pick up at least five $2$'s.

If you do need to write out a formal induction, it could be written out somewhat more clearly. For example, the phrase "so for $n=k$ it is true" is not clear. I assume you mean that "so if for $n=k$ it is true." We now write out a proof.

The result is obviously true for $n=1$. We show that if it is true for $n=k$, it is true for $n=k+1$.

Note that $$(2\cdot (k+1))!=(2k)!(2k+1)(2k+2).$$ By the induction assumption, $2^k$ divides $(2k)!$. It follows that $2^{k+1}$ divides $(2k)!(2)$, and therefore $2^{k+1}$ divides $(2k)!(2k+1)(2k+2)$.

share|improve this answer
    
does generally induction works for negative numbers as well?so if i proof that something is true for some set of positive numbers,can i conclude that it is also true for negative numbers? –  dato datuashvili Jun 29 '12 at 16:03
3  
@dato: No. E.g., the statement "$n$ is positive" is true for positive integers but not negative integers. But you can use induction to prove things about negative numbers. If $P(n)$ is a statement, and you prove that $P(0)$ is true, that $P(n)$ implies $P(n+1)$, and $P(n)$ implies $P(n-1)$, then the statement is true for all integers. –  Jonas Meyer Jun 29 '12 at 16:06
    
If you have $P(n)$ implies both $P(n+1)$ and $P(n-1)$ then it doesn't matter for which integer $n_0$ you prove $P(n_0)$. –  celtschk Jul 9 '12 at 11:05
    
@celschk, this is wrong. I can define $P(n)$ as "$2 n + 1$ is even." Then $P(n + 1)$ is that $(2 n + 1) + 2$ is even, and as even + even is even, this is true. Similarly for $P(n - 1)$. All odd integers are even. –  vonbrand May 2 at 12:50

From 1 to $2n$ there are exactly $n$ even numbers. Hence the product $1\cdots 2n=(2n)!$ is divisible by $2\cdot2\cdots 2 \hbox{ ($n$ times)}= 2^n$.

share|improve this answer
1  
It's as simple as that... –  Gautam Shenoy Jul 18 '13 at 16:52

Suppose there are $n$ distinct objects in a set $D$.

Consider a set $S$ containing $2$ copies of each element from $D$. Then $S$ has total $2n$ objects.

Total number of permuatations of these objects $=\dfrac{(2n)!}{(2!)^n}=\dfrac{(2n)!}{2^n}$.

Since number of permutations is an integer, therefore, $\dfrac{(2n)!}{2^n}$ is an integer.

share|improve this answer
2  
thanks @avatar,it was very good example –  dato datuashvili Jun 29 '12 at 16:15
2  
Also simple: $(2n)!$ contains, as as factors, both $2n$ and $2n-1$, while $(2(n-1))!$ does not. One of those is an even number, so we've added at least one factor of 2. –  BlueRaja - Danny Pflughoeft Jun 29 '12 at 17:22
    
I'm not comfortable with the phrase "we take another set of same objects". I think you count the "multset permutations" of a multiset on $n$ values, each one occurring exactly twice; to me that is a clearer description, because I know what multiset permutations are (and that one cannot compose them). Another form of the same argument: if in the symmetric group $S_{2n}$ one selects $n$ disjoint $2$-cycles, then these generate a subgroup with $2^n$ elements; now it's Lagrange's thoerem. –  Marc van Leeuwen Jul 9 '12 at 12:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.