Borbas wrote: Prove that the number $A=\frac{(4n)!}{(2n)!n!}$ is an integer and divisible by $2^{n+1}$, where $n$ is a positive integer. We have that $$A=\dfrac{(2n+1)(2n+2)\cdots (4n-1)(4n)}{n!}=2^{n+1}\dfrac{n(n+1)(n+2)\cdots (2n-1)}{n!}\cdot (2n+1)(2n+3)\cdots (4n-1)$$But the product of $n$ consecutive integers is divisible by $n!$. The conclusion follows.

Or $\displaystyle{\frac{n(n+1)...(2n-1)}{n!}=\binom{2n-1}{n-1}(n)!}$ which is definitely an integer.

Let $A(n)=\frac{(4n)!}{(2n)! \cdot (n)!}$ Then, Clearly it is an integer because $$A(n)=\underbrace {\binom{3n}{n}}_{\text{integer}} \cdot \underbrace{\frac{(4n)!}{(3n)!}}_{\text{integer}}$$For the other part, We can also use induction. $$A(n+1)=A(n) \cdot \frac{(4n+1)(4n+2)(4n+3)(4n+4)}{(2n+1)(2n+2)(n+1)}$$ For $n \mapsto n+1$ step $\bullet$ If $n$ is even it directly follows from $n \to n+1$ $\bullet$ If $n$ is odd then we move from $n-1 \to n+1$ Then we compare the highest power of $2$ that divides the numerator and the denominator of $\frac{A(n+1)}{A(n)}$ when $n$ is even. and $\frac{A(n+1)}{A(n-1)}$ when $n$ is odd.

No we can't, we have a problem if $n\equiv 3 (\mod 4)$

We can do that because adityaguharoy wrote: Let $A(n)=\frac{(4n)!}{(2n)! \cdot (n)!}$ Then, Clearly it is an integer because $$A(n)=\binom{3n}{n} \cdot \frac{(4n)!}{(3n)!}$$For the other part, We can also use induction. $$A(n+1)=A(n) \cdot \frac{(4n+1)(4n+2)(4n+3)(4n+4)}{(2n+1)(2n+2)(n+1)}$$ For $n \mapsto n+1$ step $\bullet$ If $n$ is even it directly follows from $n \to n+1$ $\bullet$ If $n$ is odd then we move from $n-1 \to n+1$ Then we compare the highest power of $2$ that divides the numerator and the denominator. in this method I think we don't see a problem.

I think I have another idea for a solution : Actually $$A(n)=\binom{4n}{2n} \cdot \binom{2n}{n} \cdot (n)!$$which is another proof of why it is an integer. I thought of applying Legendre here, but then it seems it will only become very complicated and the result won't be easy to derive from here. EDIT : Yes, it is possible from there to derive the result. See below the post of @Catalin.

Using Legendre's formula we have $v_2(4n)!=3n+\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots$ and $v_2(2n)!=n+\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots$ and also $v_2(n!)=\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots$ So $v_2 \left( \frac{(4n)!}{(2n)!n!} \right) = 2n-\left(\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots \right)$. It remains to prove that $$2n- \left(\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots \right) \geq n+1 \iff 1+\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots \leq n$$Let's suppose that the sum ends at some exponent $2^i$, i.e. $i$ is the greatest exponent such that $2^i \leq n$. Using $\lfloor k \rfloor \leq k$ we have $$1+\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots \lfloor \frac{n}{2^i} \rfloor \leq 1+n \sum_{k=1}^i \frac{1}{2^k}=1+n\left( \frac{\frac{1}{2^{i+1}}-1}{\frac{1}{2}-1}-1 \right)=1+\frac{2^i-1}{2^i}n$$What's left to prove is $$1+\frac{2^i-1}{2^i}n \leq n \iff 2^i \leq n$$which is true

Very nice adityaguharoy and knm2608. Well done!

hint

It is obivous integer for next part: $V_2(A)=4n-s_2(4n)-2n-n+s_2(2n)+s_n = n+s_2(2n)+s_2n-s_2(4n) \geq n+1$ Note: we know $s_2(n)=s_2(2^bn)$ so if $s_2(n)=x \rightarrow s_2(2n)+s_2n-s_2(4n)=x>0$ (Attention We use this formula in proof: $V_p(n!)=\frac{n-s_p(n)}{p-1}$)

Here is an easier solution: lemma 1:$v_p(n!)=\frac{n-s_p(n)}{p-1}$ where $s_p(n)$ is the sum of digits of $n$ in bace $p$(for prime p). lemma 2(Kummer):the highest exponent of prime $p$ in binomial coefficient $\binom{m}{n}$ is the number of carries in the sum $(m-n)+n$ in base $p$. proof of both lemmas is easy and we ignore it. back to problem: we have $A=\frac{(2n)!}{n!} \binom{4n}{2n}$ by lemma 1:$v_2((2n)!)-v_2(n1)=n$($2n=(n0)_2$ by lemma 2:$S=v_2(\binom{4n}{2n}) \geq 1$(since every non-zero number has at least one non-zero digit in base 2) so we have $v_2(A)=n+S \geq n+1$.equality occurs if $n$ is a power of 2

adityaguharoy wrote: I think I have another idea for a solution : Actually $$A(n)=\binom{4n}{2n} \cdot \binom{2n}{n} \cdot (n)!$$which is another proof of why it is an integer. I thought of applying Legendre here, but then it seems it will only become very complicated and the result won't be easy to derive from here. EDIT : Yes, it is possible from there to derive the result. See below the post of @Catalin. What is Legendre?

Catalin wrote: Using Legendre's formula we have $v_2(4n)!=3n+\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots$ and $v_2(2n)!=n+\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots$ and also $v_2(n!)=\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots$ So $v_2 \left( \frac{(4n)!}{(2n)!n!} \right) = 2n-\left(\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots \right)$. It remains to prove that $$2n- \left(\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots \right) \geq n+1 \iff 1+\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots \leq n$$Let's suppose that the sum ends at some exponent $2^i$, i.e. $i$ is the greatest exponent such that $2^i \leq n$. Using $\lfloor k \rfloor \leq k$ we have $$1+\lfloor \frac{n}{2} \rfloor + \lfloor \frac{n}{4} \rfloor+\dots \lfloor \frac{n}{2^i} \rfloor \leq 1+n \sum_{k=1}^i \frac{1}{2^k}=1+n\left( \frac{\frac{1}{2^{i+1}}-1}{\frac{1}{2}-1}-1 \right)=1+\frac{2^i-1}{2^i}n$$What's left to prove is $$1+\frac{2^i-1}{2^i}n \leq n \iff 2^i \leq n$$which is true

$$ A\cdot \frac{1}{2^{n+1}}=\frac{(4n)!}{(2n)!\cdot [n\cdot (n-1)\cdot \dots\cdot 3\cdot 2\cdot 1]\cdot 2^{n+1}}=\frac{(4n)!}{(2n)!\cdot [2n\cdot (2n-2)\cdot \dots\cdot 6\cdot 4\cdot 2]\cdot 2}= $$$$ =\frac{(4n)!}{(2n)!\cdot \frac{(2n)!}{(2n-1)\cdot (2n-3)\cdot \dots\cdot 5\cdot 3\cdot 1}\cdot 2}=\frac{(4n)!}{(2n)!\cdot (2n)!}\cdot \frac{(2n-1)\cdot (2n-3)\cdot \dots\cdot 5\cdot 3\cdot 1}{2}= $$$$ =\frac{1}{2}\cdot {4n\choose {2n}}\cdot (2n-1)\cdot (2n-3)\cdot \dots \cdot 5\cdot 3\cdot 1 $$And indeed ${4n\choose{2n}}={2k\choose k}$ is even, because it corresponds to the number of ways in which $k$ elements can be chosen among a set of $2k$ elements, but for every choice of elements $a_1,a_2, \dots, a_k$ there exists another choice where $a_1,a_2,\dots,a_k$ are precisely the non-chosen elements.

We have $A=\frac{(4n)!}{(2n)! \cdot (n)!}=\frac{(1.3.5....(4k-1))(2.4.6...4k)}{(2n)! \cdot (n)!}=\frac{(1.3.5....(4k-1))2^{2n}(1.2.3...2n)}{(2n)! \cdot (n)!}=\frac{(1.3.5....(4k-1))2^{2n}(2n)!}{(2n)! \cdot (n)!}=t\frac{2^{2n}}{n!}$ Now case 1: if $n$ is even, say $n=2k$, then $\frac{2^{4k}}{(2k)!}=\frac{2^{4k}}{(1.3.5...(2k-1))(2.4.6...(2k))}=\frac{2^{4k}}{(1.3.5...(2k-1))2^kk!}=\frac{2^{3k}}{(1.3.5...(2k-1))k!}=\frac{2^{n+k}}{(1.3.5...(2k-1))k!}$ So $A=t\frac{2^{n+k}}{(1.3.5...(2k-1))k!}$ hence $2^{n+k}|A$ and $k\ge 1$ Case 2: if $n=2k-1$ then $\frac{2^{2n}}{n!}=\frac{2^{4k-2}}{(2k-1)!}=\frac{2^{4k-2}}{(1.3.5..(2k-1))(2.4.6...(2k-2))}=\frac{2^{4k-2}}{(1.3.5..(2k-1))2^{k-1}(1.2.3...(k-1))}=\frac{2^{3k-1}}{(1.3.5..(2k-1))(k-1)!}$ so $A=t\frac{2^{2k-1+k}}{(1.3.5..(2k-1))(k-1)!}=t\frac{2^{n+k}}{(1.3.5..(2k-1))(k-1)!}$ so $2^{n+k}|A$, where $k\ge 1$