13
$\begingroup$

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?

$\endgroup$
6
  • 4
    $\begingroup$ There is no problem in your proof. $\endgroup$
    – Aang
    Jun 29, 2012 at 16:05
  • 7
    $\begingroup$ Actually we can prove more. We can show that $$ \frac{(2n)!}{n!2^n}$$ is an odd integer. $\endgroup$ Jun 29, 2012 at 16:28
  • 2
    $\begingroup$ The only change I would make is to simplify the proof by writing $(2n+2)!= (2n+2)(2n+1)(2n)!$. $\endgroup$ Jun 29, 2012 at 16:31
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 29, 2012 at 16:50
  • 1
    $\begingroup$ Possible duplicate of prove that $\frac{(2n)!}{(n!)^2}$ is even if $n$ is a positive integer $\endgroup$
    – Davood
    Sep 4, 2017 at 13:36

3 Answers 3

21
$\begingroup$

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$.

$\endgroup$
1
  • 2
    $\begingroup$ It's as simple as that... $\endgroup$ Jul 18, 2013 at 16:52
18
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ thanks @avatar,it was very good example $\endgroup$ Jun 29, 2012 at 16:15
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 29, 2012 at 17:22
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 9, 2012 at 12:31
13
$\begingroup$

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)$.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Jun 29, 2012 at 16:03
  • 3
    $\begingroup$ @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. $\endgroup$ Jun 29, 2012 at 16:06
  • $\begingroup$ 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)$. $\endgroup$
    – celtschk
    Jul 9, 2012 at 11:05
  • $\begingroup$ @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. $\endgroup$
    – vonbrand
    May 2, 2014 at 12:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .