3
$\begingroup$

I have verified this for many values of $n$, but I have no idea how to prove it. Does anyone know how I could go about showing that: $$\frac{((2n)!)^2(i)!(j)!}{((n)!)^2(2i)!(2j)!}$$ is an integer when $n$, $i$, and $j$ are all integers and $n \geq i,j$

$\endgroup$
2
  • $\begingroup$ Either directly, by cancelling out common factors, which could get messy, or by induction on $n$. $\endgroup$ – Johanna Jan 20 '15 at 4:11
  • $\begingroup$ Can you elaborate on how an inductive proof would work? $\endgroup$ – ASKASK Jan 20 '15 at 4:21
4
$\begingroup$

First note that

$$\frac{(2n)!^2i!j!}{n!^2(2i)!(2j)!}=\frac{n!\binom{2n}n}{i!\binom{2i}i}\cdot\frac{n!\binom{2n}n}{j!\binom{2j}j}\;,\tag{1}$$

so we need only show that each of the factors on the righthand side of $(1)$ is an integer.

For any $k$, $k!\binom{2k}k$ is the number of ways of selecting $k$ of the members of the set $\{1,2,\ldots,2k\}$ and arranging them in some order; let $S_k$ be the set of $k$-tuples that result from this process.

Take any sequence $\langle r_1,\ldots,r_i\rangle\in S_i$. Let $\langle r_{i+1},\ldots,r_n\rangle$ be any $(n-i)$-tuple of elements of the set $\{1,\ldots,2n\}\setminus\{r_1,\ldots,r_i\}$. There are $(n-i)!\binom{2n-i}{n-i}$ such $(n-i)$-tuples, and there are $\binom{n}i$ ways to merge one of them with $\langle r_1,\ldots,r_i\rangle$, so each member of $S_i$ is a substring of $(n-i)!\binom{2n-i}{n-i}\binom{n}i$ members of $S_n$. Thus,

$$\frac{n!\binom{2n}n}{i!\binom{2i}i}=\frac{|S_n|}{|S_i|}=(n-i)!\binom{2n-i}{n-i}\binom{n}i$$

is an integer, and similarly

$$\frac{n!\binom{2n}n}{j!\binom{2j}j}=\frac{|S_n|}{|S_j|}=(n-j)!\binom{2n-j}{n-j}\binom{n}j\;.$$

$\endgroup$
3
  • $\begingroup$ Cool proof! I personally prefer the one I added because it does not require a knowledge of combinatorics, but I like the alternate perspective! $\endgroup$ – ASKASK Jan 21 '15 at 5:30
  • $\begingroup$ @ASKASK: I've a liking for combinatorial arguments, but yours is certainly a nice, straightforward calculation -- nicer than I would have expected. $\endgroup$ – Brian M. Scott Jan 21 '15 at 5:37
  • $\begingroup$ Thank you. I think you should take a look at the link at the bottom of my answer, as it is trying to prove a rather complicated expression (involving combinations), and I think that the way to go about doing it is through combinatorial arguments, and I think you may have some nice insight as to how I could proceed. $\endgroup$ – ASKASK Jan 21 '15 at 5:51
3
$\begingroup$

First lets define $f(n)$ to be equal to the product of the first n positive odd integers. We have $f(n)=\frac{(2n)!}{2^n (n)!}$ (explanation here). Logically, if $n \geq a$, then $\frac{f(n)}{f(a)}$ is an integer because all of the terms of $f(a)$ exist in $f(n)$.

Since $f(n)=\frac{(2n)!}{2^n (n)!}$, we also have $\frac{(2n)!}{(n)!}=2^n f(n)$ and likewise $\frac{n!}{(2n)!}=\frac{1}{2^n f(n)}$

Now, we can rewrite our original expression as: $$\frac{(2n)!}{(n)!}\frac{(2n)!}{(n)!}\frac{(i)!}{(2i)!}\frac{(j)!}{(2j)!} = 2^n f(n) \cdot 2^n f(n) \cdot \frac{1}{2^i f(i)} \cdot \frac{1}{2^j f(j)}$$ $$=\frac{2^n}{2^i} \frac{2^n}{2^j} \frac{f(n)}{f(i)} \frac{f(n)}{f(j)}$$

And since $n \geq i$ and $n \geq j$, each fraction is an integer and thus the product is an integer.

If you were interested in this, they maybe you would be interested in trying to help out with the problem that this was a subproblem of: Proving an identity involving factorials

$\endgroup$
0
$\begingroup$

let $V_{p}(a)$ is the exponent of the prime number $p$ in the prime factorization of $a$,then we know $$v_{p}(n!)=[\dfrac{n}{p}]+[\dfrac{n}{p^2}]+[\dfrac{n}{p^3}]+\cdots=\sum_{i=1}^{\infty}[\dfrac{n}{p^k}]$$ so Now we only prove $$2\sum_{k=1}^{\infty}[\dfrac{2n}{p^k}]+\sum_{k=1}^{\infty}[\dfrac{i}{p^k}]+\sum_{k=1}^{\infty}[\dfrac{j}{p^k}]\ge 2\sum_{k=1}^{\infty}[\dfrac{n}{p^k}]+\sum_{k=1}^{\infty}[\dfrac{2i}{p^k}]+\sum_{k=1}^{\infty}[\dfrac{2j}{p^k}]$$ let $$x=\dfrac{n}{p^k},y=\dfrac{i}{p^k},z=\dfrac{j}{p^k}$$ then we only prove $$2[2x]+[y]+[z]\ge 2[x]+[2y]+[2z],x\ge y,z$$ use $x=[x]+\{x\}$,then we only prove $$2[2([x]+\{x\})]+[y]+[z]\ge 2[x]+[2[y]+2\{y\}]+[2[z]+2\{z\}]$$ $$\Longleftrightarrow 2[x]+2[2\{x\}]\ge [y]+[z]+[2\{y\}]+[2\{z\}]$$ It is clear,we onlt consider following two case

since $x\ge y,z$,then if $\{x\}>0.5$,and $[x]=[y]=[z]=m$,then $$LHS=2m+2\cdot 1=2m+2,RHS=m+m+2=2m+2$$ if $\{x\}<0.5$,and $[x]=m,[y]=[z]=m-1,\{y\},\{z\}>0.5$,then we have $$LHS=2m+0=2m,RHS=m-1+m-1+1+1=2m$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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