orl wrote: For every integer $ k \geq 2,$ prove that $ 2^{3k}$ divides the number \[ \binom{2^{k + 1}}{2^{k}} - \binom{2^{k}}{2^{k - 1}} \] but $ 2^{3k + 1}$ does not. Author: unknown author, Poland It is from Russian journal Qvant - 1970-1975. $ p^{3n + t_p}|\binom{p^{n + 1}}{p^n} - \binom{p^n}{p^{n - 1}}$. Where $ t_2 = 0$, $t_3 = 1$, $t_p = 2$ if $p$ is not a Wolstenholme's prime. If $p$ is a Wolstenholm's prime, then $ t_p\ge 3$. For 2 known Wolstenholme's primes, $ t_p = 3$.

In email exchange Rustem says the problem is based on the article by Fuchs, D. B. and Fuchs., M.B: Arithmetic of binomial coefficients, Kvant, #6,1970 whose Russian Фукс Д., Фукс М. Фрифметика биномиальных коэффициентов. Квант №6, 1970. which can be found at http://kvant.mirror1.mccme.ru/1970/06/arifmetika_binomialnyh_koeffic.htm.

It is not hard to prove: $ v_p(\binom{pc}{pa} - \binom{c}{a}) = 2 + t_p + v_p(c) + v_p(a) + v_p(b),b = c - a$. In these case $ c = p^n,a = p^{n - 1}$.

(For odd integers $n$, $(2n-1)!! = 1 \cdot 3 \cdots (2n-1)$.) Lemma 1: $v_2((2^n)!) = 2^n - 1$. Proof: \begin{align*} v_2((2^n)!) &= \left \lfloor \frac{2^n}{2^1} \right \rfloor + \left \lfloor \frac{2^n}{2^2} \right \rfloor + \cdots + \left \lfloor \frac{2^n}{2^n} \right \rfloor \\ &= 2^{n-1} + 2^{n-2} + \ldots + 1 \\ &= 2^n - 1. \end{align*} Corollary 1: $v_2((2^{k-1} + 1)(2^{k-1} + 2) \cdots (2^{k-1} + 2^{k-1})) = 2^{k-1}$. Proof: \begin{align*} v_2((2^{k-1} + 1)(2^{k-1} + 2) \cdots (2^{k-1} + 2^{k-1})) &= v_2 \left(\frac{(2^k)!}{(2^{k-1})!}\right) \\ &= (2^k - 1) - (2^{k-1} - 1) \\ &= 2^{k-1}. \end{align*} Lemma 2: $\frac{(2^{k-1} + 1)(2^{k-1} + 2) \cdots (2^{k-1} + 2^{k-1})}{2^{2^{k-1}}} = (2^k - 1)!!$. Proof: For every positive odd integer $i$ less than $2^k$, there exists a unique integer $b_i$ such that $2^{k-1} < i 2^{b_i} < 2^k$. Conversely, for every integer $c$ between $2^{k-1}$ and $2^k$, there exists a unique odd integer $i$ such that $i 2^{b_i} = c$. Furthermore, $b_1 + b_3 + \ldots + b_{2^k - 1}$ must be equal to the exponent of the greatest power of 2 dividing $(2^{k-1} + 1)(2^{k-1} + 2) \cdots (2^{k-1} + 2^{k-1})$, which by corollary 1 equals $2^{k-1}$. It follows that \begin{align*} (2^{k-1} + 1)(2^{k-1} + 2) \cdots (2^{k-1} + 2^{k-1}) &= (1 \cdot 2^{b_1})(3 \cdot 2^{b_3}) \cdots (2^{k-1} \cdot 2^{b_{2^k - 1}}) \\ &= (2^k-1)!! 2^{b_1 + b_2 + \ldots + b_{2^k - 1}} \\ &= (2^k - 1)!! 2^{2^{k-1}} \end{align*} which completes our proof. Let $P_1 = (2^k + 1)(2^k + 2) \cdots (2^k + 2^k)$, let $P_2 = (2^{k-1} + 1)(2^{k-1} + 2) \cdots (2^{k-1} + 2^{k-1})$, and let $P_3 = (2^k + 1)(2^k + 3) \cdots (2^k + 2^k - 1)$. Note that \begin{align*} P_1 &= (2^k + 1)(2^k + 2) \ldots (2^k + 2^k) \\ &= \left((2^k + 1)(2^k + 3) \ldots (2^k + 2^k - 1)\right) \left(2(2^{k-1} + 1) \cdot 2(2^{k-1} + 2) \cdots 2(2^{k-1} + 2^{k-1}) \right) \\ &= 2^{2^{k-1}} P_2 P_3 \end{align*} Now, \begin{align*} \binom{2^{k+1}}{2^k} - \binom{2^k}{2^{k-1}} &= \frac{(2^{k+1})!}{(2^k)!^2} - \frac{(2^k)!}{(2^{k-1})!^2} \\ &= \frac{(2^{k+1})!}{(2^k)!^2} - \frac{(2^k)!((2^{k-1} + 1)(2^{k-1} + 2) \cdots (2^{k-1} + 2^{k-1}))^2 }{(2^k)!^2} \\ &= \frac{(2^k)! ((2^k + 1)(2^k + 2) \cdots (2^k + 2^k)) - (2^k)! ((2^{k-1} + 1)(2^{k-1} + 2) \cdots (2^{k-1} + 2^{k-1}))^2}{(2^k)!^2} \\ &= \frac{P_1(2^k)!- (2^k)! P_2^2}{(2^k)!^2} \\ &= \frac{P_1 - P_2^2}{(2^k)!} \\ &= \frac{2^{2^{k-1}} P_2 P_3 - P_2^2}{(2^k)!} \\ &= \frac{2^{2^{k-1}} P_2}{(2^k)!} \left(P_3 - \frac{P_2}{2^{2^{{k-1}}}}\right) \end{align*} By lemma 1 and corollary 1, $v_2 \left(\frac{2^{2^{k-1}} P_2}{(2^k)!}\right) = 1$. Also, by lemma 2, $\frac{P_2}{2^{2^{k-1}}} = (2^k - 1)!!$, so we want to show that \[2^{3k-1} || (2^k + 1)(2^k + 3) \cdots (2^k + 2^k - 1) - (2^k - 1)!!.\] Let $S_1 = \frac{1}{1} + \frac{1}{3} + \ldots + \frac{1}{2^k - 1}$, let $S_2 = \sum_{1 \leq i < j \leq 2^{k-1}} \frac{1}{(2i - 1)(2j - 1)} = \frac{1}{1 \cdot 3} + \frac{1}{1 \cdot 5} + \cdots + \frac{1}{1 \cdot (2^k - 1)} + \frac{1}{3 \cdot 5} + \cdots + \frac{1}{(2^k - 3) \cdot (2^k - 1)}$, and let $S_3 = \frac{1}{1 \cdot (2^k - 1)} + \frac{1}{3 \cdot (2^k - 3)} + \cdots + \frac{1}{(2^k - 1) \cdot 1}$. Note that \begin{align*} S_1 &= \frac{2S_1}{2} \\ &= \frac{\left(\frac{1}{1} + \frac{1}{2^k - 1}\right) + \left(\frac{1}{3} + \frac{1}{2^k - 3}\right) + \ldots + \left( \frac{1}{2^k - 1} + \frac{1}{1}\right)}{2} \\ &= 2^k \frac{S_3}{2} \\ &= 2^{k-1} S_3 \end{align*} We have that \begin{align*} P_3 - (2^k - 1)!! &= (2^k + 1)(2^k + 3) \cdots (2^k + 2^k - 1) - (2^k - 1)!! \\ &= 2^{3k}(\mbox{some terms}) + (2^k - 1)!!(2^{2k} S_2 + 2^{k-1} S_1) \\ &= 2^{3k}(\mbox{some terms}) + (2^k - 1)!!(2^{2k} S_2 + 2^{2k-1} S_3) \end{align*} We wish to show that $2^{3k-1} || 2^{3k}(\mbox{some terms}) + (2^k - 1)!!(2^{2k} S_2 + 2^{2k-1} S_3)$, i.e., $2^{k-1} || S_2 + \frac{S_1}{2}$. This is clearly equivalent to $S_2 + \frac{S_1}{2} \equiv 2^{k-1} \pmod{2^k}$. Since $\{\frac{1}{1}, \frac{1}{3}, \cdots, \frac{1}{2^k - 1}\}$ is a permutation of $\{1, 3, \cdots, 2^k - 1\}$ modulo $2^{k}$ and $2^k - a \equiv -a \pmod{2^k}$, we have: \begin{align*} S_2 &\equiv 1 \cdot 3 + 1 \cdot 5 + \cdots + 1 \cdot (2^n - 1) + 3 \cdot 5 + \cdots + (2^k - 3)(2^k - 1) \\ &\equiv \frac{(1 + 3 + \cdots + 2^k - 1)^2 - (1^2 + 3^2 + \cdots + (2^k-1)^2)}{2} \pmod{2^k} , \end{align*} and $S_3 \equiv -(1^2 + 3^2 + \cdots + (2^k - 1)^2) \pmod{2^k}$. $2^k | 2^{2k-1} = \frac{(1 + 3 + \cdots + 2^k - 1)^2}{2}$, so $S_2 + \frac{S_3}{2} \equiv -(1^2 + 3^3 + \cdots + (2^n - 1)^2) \pmod{2^k}$. Hence, \begin{align*} -\left(S_2 + \frac{S_3}{2}\right) &\equiv 1^2 + 3^2 + \cdots + (2^k - 1)^2 \\ &= 1^2 + 2^2 + \cdots + (2^k - 1)^2 - 2^2(1^2 + 2^2 + \cdots + (2^{k-1} - 1)^2) \\ &= \frac{2^k (2^k-1) (2^{k+1} - 1)}{6} - 4 \frac{2^{k-1}(2^{k-1}-1)(2^k - 1)}{6} \\ &= \frac{2^{k-1} (2^k - 1)(2^{k+1} - 1) - 2 \cdot 2^{k-1}(2^{k-1}-1)(2^k - 1)}{3} \\ &= 2^{k-1}(2^k - 1) \left(\frac{2^{k+1} - 1 - 2(2^{k-1}-1)}{3} \right) \\ &= (2^k - 1)(2^{k-1}) \left(\frac{2^{k+1} - 1 - 2^k + 2}{3} \right) \\ &= (2^k - 1)(2^{k-1}) \left(\frac{2^k + 1}{3} \right) \\ &= 2^{k-1} \left(\frac{4^k - 1}{3}\right) \\ &\equiv 2^{k-1} \pmod{2^k} \end{align*} which is congruent to $2^{k-1}$ modulo $2^k$, as desired.

Zhero wrote: We wish to show that $2^{3k-1} || 2^{3k}(\mbox{some terms}) + (2^k - 1)!!(2^{2k} S_2 + 2^{2k-1} S_3)$, i.e., $2^{k-1} || S_2 + \frac{S_1}{2}$. This is clearly equivalent to $S_2 + \frac{S_1}{2} \equiv 2^{k-1} \pmod{2^k}$. Since $\{\frac{1}{1}, \frac{1}{3}, \cdots, \frac{1}{2^k - 1}\}$ is a permutation of $\{1, 3, \cdots, 2^k - 1\}$ modulo $2^{k}$ and $2^k - a \equiv -a \pmod{2^k}$, we have: \begin{align*} S_2 &\equiv 1 \cdot 3 + 1 \cdot 5 + \cdots + 1 \cdot (2^n - 1) + 3 \cdot 5 + \cdots + (2^k - 3)(2^k - 1) \\ &\equiv \frac{(1 + 3 + \cdots + 2^k - 1)^2 - (1^2 + 3^2 + \cdots + (2^k-1)^2)}{2} \pmod{2^k} , \end{align*}and $S_3 \equiv -(1^2 + 3^2 + \cdots + (2^k - 1)^2) \pmod{2^k}$. $2^k | 2^{2k-1} = \frac{(1 + 3 + \cdots + 2^k - 1)^2}{2}$, so $S_2 + \frac{S_3}{2} \equiv -(1^2 + 3^3 + \cdots + (2^n - 1)^2) \pmod{2^k}$.

Also, a slightly different way to find the binomial coefficient difference, noting that $v_2\left(\binom{2^{i+1}}{2^i}\right)=1$, is \begin{align*} \binom{2^{k+1}}{2^k} = \frac{(2^{k+1})!}{(2^k)!^2} &= \frac{(2^{k+1}-1)!!}{(2^k-1)!!^2}\cdot\frac{2^{2^k}}{(2^{2^{k-1}})^2}\binom{2^k}{2^{k-1}}\\ &= \frac{(2^{k+1}-1)!!}{(2^k-1)!!^2}\binom{2^k}{2^{k-1}}\\ &= \frac{(2^k+1)(2^k+3)\cdots(2^k+(2^k-1))}{(2^k-1)!!}\binom{2^k}{2^{k-1}}\\ &= \left(\frac{\binom{2^k}{2^{k-1}}}{2}\right)\left(\frac{2^{3k+1}(\text{stuff})}{(2^k-1)!!}+\sum_{1\le i<j\le2^{k-1}}\frac{2^{2k+1}}{(2i-1)(2j-1)}+\sum_{i=1}^{2^{k-1}}\frac{2^{k+1}}{2i-1}\right)+\binom{2^k}{2^{k-1}}. \end{align*}

Rust wrote: It is not hard to prove: $ v_p(\binom{pc}{pa} - \binom{c}{a}) = 2 + t_p + v_p(c) + v_p(a) + v_p(b),b = c - a$. In these case $ c = p^n,a = p^{n - 1}$. Hey, can anyone furnish a proof of this proposition? (BTW I can't even understand the definition of $t_p$ given in post #2...)

Rust wrote: It is not hard to prove: $ v_p(\binom{pc}{pa} - \binom{c}{a}) = 2 + t_p + v_p(c) + v_p(a) + v_p(b),b = c - a$. In these case $ c = p^n,a = p^{n - 1}$. I don't think the solving this lemma is simple! Can anyone solve it?

I think Rust's statement is wrong : $\dbinom{14}{8} - \dbinom{7}{4} = 2968$, and $v_2(2968) = 3$. However, his formula says it's should be $4$.

dinoboy wrote: I think Rust's statement is wrong : $\dbinom{14}{8} - \dbinom{7}{4} = 2968$, and $v_2(2968) = 3$. However, his formula says it's should be $4$. But i was taking $c=p^n,a=p^{n-1}$. I think this lemma is true in this case!

Just an useful step towards the proof of what Rust claimed is that $v_p\binom{pc}{pa}=v_p\binom{c}{a}$. I am giving the proof(though its easy to prove): Let $a=(a_1a_2 \cdots a_k)_p,c-a=(c_1c_2 \cdots c_k)_p$,Then clearly we have $pa=(a_1a_2 \cdots a_k0)_p$ and $pc-pa=(c_1c_2 \cdots c_k0)_p$ so the result follows directly from Kummer's theorem. BTW Rust can you tell me what is $t_p$ here?I think it would be of some help.

I have a long proof. It is equivalent to proving $v_2\left( \frac{2^{k+1}!}{2^k!} - \left( \frac{2^k!}{2^{k-1}!} \right)^2 \right) = 3k+2^k-1$, which is equivalent to proving $v_2((2^{k+1})!!/(2^k)!! - 2^k!!) = 3k-1$, next reduce it to proving $v_2\left( \sum 1/i + 2^k\left( \sum 1/ij \right) \right)=2k-1$ where the sums run over $i \neq j$ odd numbers $\le 2^k-1$. Now use squaring identity to reduce it to $v_2\left( \sum_{i \text{ odd}}^{2^k-1} \frac{1}{i} - \sum_{i \text{ odd}}^{2^k-1} \frac{2^{k-1}}{i^2} \right) = 2k-1$ which is equivalent to $\left( \sum_{i \text{ odd}}^{2^{k-1}-1} \left( \frac{1}{i} +\frac{1}{(2^k-i)} - \frac{2^{k-1}}{i^2}- \frac{2^{k-1}}{(2^k-i)^2} \right) \right) = 2^{2k-1} (\text{mod }2^{2k})$ which is equivalent to $\sum_{i=1}^{2^{k-1}-1} \frac{i^2}{i^4} = 2^{k-2} (\text{mod } 2^{k-1})$, which can be done immediately by induction on $k$.

If the following solution is correct and I didn't screw up again like the last time I tried algebra, I think this significantly shortens the above solutions. Proof: Let $(2n-1)!!$ denote $(2n-1)(2n-3)...(1)$. It is easy to see that since $(2n)! = 2^n \cdot n! \cdot (2n-1)!!$, we have $\frac {\binom{2^{n+1}}{2^n}} {\binom{2^n}{2^{n-1}}} = \frac {(2^{n+1}-1)!!} {(2^n-1)!!^2} = \frac {(2^n+1)(2^n+3)...(2^n+2^n-1)} {(2^n-1)(2^n-3)...(1)} = Q$. Now, $v_2 (\binom{2^{n+1}}{2^n} - \binom{2^n}{2^{n-1}}) = v_2 \binom {2^n}{2^{n-1}} + v_2(Q-1) = 1 + v_2(Q-1)$, since by Legendre $v_2 \binom {2^n}{2^{n-1}} = v_2 (2^n)! - 2v_2 (2^{n-1})! = 2^n-1 - 2(2^{n-1}-2) = 1$. It suffices to prove $v_2(Q-1) = 3n-1$. Now note $v_2(Q-1) = v_2((2^n+1)(2^n+3)...(2^n+2^n-1) - (2^n-1)!!)$. Consider the polynomial $P(X) = (X+1)(X+3)...(X+2^n-1) - (X-1)(X-3)...(X-(2^n-1))$, and it is clear that our $v_2$ expression is $P(2^n)$. Now note $P(X)$ is an odd polynomial, since the coefficients of even powered terms cancel. Then if $N$ denotes the coefficient of the $x$ term in $P(x)$, we must show that $v_2 (N \cdot 2^n) = 3n-1$, or $v_2 (N) = 2n-1$, since all other terms are divisible by $2^{3n}$. Then clearly $N = 2 \cdot (2n-1)!! \cdot (\frac {1}{1} + \frac{1}{3} + ... + \frac{1}{2^n-1})$, so it suffices to show $v_2 (\frac {1}{1} + \frac{1}{3} + ... + \frac{1}{2^n-1}) = 2n-2$. $\frac {1}{1} + \frac{1}{3} + ... + \frac{1}{2^n-1} = \frac {{\left(\frac{1}{1} + \frac{1}{2^n - 1}\right) + \left(\frac{1}{3} + \frac{1}{2^n - 3}\right) + \ldots + \left( \frac{1}{2^n - 1} + \frac{1}{1}\right)}} {2} = 2^{n-1} \cdot (\frac{1}{1 \cdot (2^n - 1)} + \frac{1}{3 \cdot (2^n - 3)} + \cdots + \frac{1}{(2^n - 1) \cdot 1}) = 2^{n-1} \cdot N'$. Then we want $v_2(N') = n-1$, so we will show $N' \equiv 2^{n-1} \pmod{2^n}$ $N' \equiv -(1^2 + 3^2 + \cdots + (2^n - 1)^2) \pmod{2^n}$, so $(1^2 + 3^2 + \cdots + (2^n - 1)^2) \equiv (1^2 +2^2 + ... + (2^n-1)^2) - (2^2 + 4^2 +...+(2^n-2)^2 \equiv \frac {(2^n-1)(2^n)(2^{n+1}-1)}{6} - 4 \cdot \frac {(2^{n-1}-1)(2^{n-1})(2^n-1)}{6} \pmod{2^n} $. But $\frac {(2^n-1)(2^n)(2^{n+1}-1)}{6} - 4 \cdot \frac {(2^{n-1}-1)(2^{n-1})(2^n-1)}{6} = 2^{n-1} (\frac{(2^n-1)(2^{n+1}-1)}{3} - \frac{2^{n-1}-1)(2)(2^n-1)}{3})$. The latter part is an odd number, so indeed $(1^2 + 3^2 + \cdots + (2^n - 1)^2) \equiv 2^{n-1} \pmod{2^n}$, whence $N' \equiv 2^{n-1} \pmod{2^n}$. Thus, $v_2(N') = n-1$, so indeed, $v_2 (\binom{2^{n+1}}{2^n} - \binom{2^n}{2^{n-1}}) = 3n$, as desired.

Solution from Twitch Solves ISL: We will prove $\nu_2(N) = 3n$. First, for the ``factor out all the unnecessary stuff'' part, \begin{align*} \frac{N}{\binom{2^n}{2^{n-1}}} = \frac{\binom{2^{n+1}}{2^n}}{\binom{2^n}{2^{n-1}}}-1 &= \frac{(2^n+1)(2^n+2)\dots(2^n+2^n)} {\left[ (2^{n-1}+1)(2^{n-1}+2) \dots (2^{n-1}+2^{n-1}) \right]^2} - 1 \\ &= \frac{2^{2^n} \cdot \left[ (2^n+1)(2^n+3)(2^n+5)\dots(2^n+(2^n-1)) \right]} {(2^{n-1}+1)(2^{n-1}+2) \dots (2^{n-1}+2^{n-1})} - 1 \\ &= \frac{2^{2^n} \cdot \left[ (2^n+1)(2^n+3)(2^n+5)\dots(2^n+(2^n-1)) \right]}{2^{2^n} \cdot (2^n-1)!!} - 1 \\ &= \frac{\left[ (2^n+1)(2^n+3)(2^n+5)\dots(2^n+(2^n-1)) \right] - (2^n-1)!!}{(2^n-1)!!}. \end{align*}Legendre's formula (or just direct calculation) shows $\nu_2 \left[ \binom{2^n}{2^{n-1}} \right] = 1$. Therefore it is sufficient to show that: Claim: We have \[ (2^n+1)(2^n+3)(2^n+5)\dots(2^n+(2^n-1)) \equiv 2^{3n-1} + (2^n-1)!! \pmod{2^{3n}}. \]Proof. Let $Y = 2^n$, so we are working modulo $Y^3$. Expanding $(Y+1)(Y+3)(Y+5)\dots(Y+(2^n-1))$ modulo $Y^3$ gives \begin{align*} (2^n-1)!! &+ (2^n-1)!! \cdot Y \cdot \left( \frac11 + \frac13 + \frac15 + \dots + \frac{1}{2^n-1} \right) \\ &+ (2^n-1)!! \cdot Y^2 \cdot \left( \frac{1}{1\cdot3} + \frac{1}{1\cdot5} + \dots + \frac{1}{(2^n-3)(2^n-1)} \right) \\ = (2^n-1)!! \cdot \bigg[ 1 &+ Y \cdot \left( \frac{2^n}{1 \cdot (2^n-1)} + \frac{2^n}{3 \cdot (2^n-3)} + \frac{2^n}{5 \cdot (2^n-5)} + \dots + \frac{2^n}{(2^{n-1}-1)(2^{n-1}+1)} \right) \\ &+ Y^2 \left( \frac{1}{1\cdot3} + \frac{1}{1\cdot5} + \dots + \frac{1}{(2^n-3)(2^n-1)} \right) \bigg] \\ = (2^n-1)!! \cdot \Bigg[ 1 &+ Y^2 \cdot \bigg( \frac{1}{1 \cdot (2^n-1)} + \frac{1}{3 \cdot (2^n-3)} + \frac{1}{5 \cdot (2^n-5)} + \dots + \frac{1}{(2^{n-1}-1)(2^{n-1}+1)} \\ &+ \frac{1}{1\cdot3} + \frac{1}{1\cdot5} + \dots + \frac{1}{(2^n-3)(2^n-1)} \bigg) \Bigg] \end{align*}Let $S$ denote the portion inside the round parentheses above. It can be taken modulo $2^n$ without penalty, so we compute \begin{align*} S &= -\left(\frac{1}{1^2} + \frac{1}{3^2} + \frac{1}{5^2} + \dots + \frac{1}{(2^{n-1}-1)^2} \right) \\ &\qquad+ \underbrace{\left( \frac{1}{1\cdot3} + \frac{1}{1\cdot5} + \dots + \frac{1}{(2^n-3)(2^n-1)} \right)}_{\text{$\binom{2^{n-1}}{2}$ terms}} \\ &\equiv -\left(\frac{1}{1^2} + \frac{1}{3^2} + \frac{1}{5^2} + \dots + \frac{1}{(2^{n-1}-1)^2} \right) \\ &\qquad+ \underbrace{\left( \frac11+\frac13+\dots+\frac{1}{2^{n-1}-1} \right) \left( \frac{1}{2^{n-1}+1}+\dots+\frac{1}{2^n-1} \right)}_{\text{$2^{n-2} \cdot 2^{n-2}$ terms}} \\ &\qquad+ \underbrace{2 \left( \frac{1}{1\cdot3} + \frac{1}{1\cdot5} + \dots + \frac{1}{(2^{n-1}-3)(2^{n-1}-1)} \right)}_{\text{$2 \binom{2^{n-2}}{2}$ terms}} \pmod{2^n}. \end{align*}If we abbreviate \[ T \coloneqq \frac11 + \frac13 + \dots + \frac{1}{2^{n-1}-1} \]then the above calculation becomes \begin{align*} S &\equiv -\left(\frac{1}{1^2} + \frac{1}{3^2} + \frac{1}{5^2} + \dots + \frac{1}{(2^{n-1}-1)^2} \right) \\ &\qquad+ T \cdot (-T) \\ &\qquad+ 2 \left( \frac{1}{1\cdot3} + \frac{1}{1\cdot5} + \dots + \frac{1}{(2^{n-1}-3)(2^{n-1}-1)} \right) \pmod{2^n} \\ &\equiv -\left(\frac{1}{1^2} + \frac{1}{3^2} + \frac{1}{5^2} + \dots + \frac{1}{(2^{n-1}-1)^2} \right) \\ &\qquad+ T \cdot (-T) \\ &\qquad+ \left( T^2 -\left(\frac{1}{1^2} + \frac{1}{3^2} + \frac{1}{5^2} + \dots + \frac{1}{(2^{n-1}-1)^2} \right) \right) \pmod{2^n} \\ &= -2\left(\frac{1}{1^2} + \frac{1}{3^2} + \frac{1}{5^2} + \dots + \frac{1}{(2^{n-1}-1)^2} \right) \\ &\equiv - \left( \frac1{1^2} + \frac{1}{3^2} + \dots + \frac{1}{(2^n-1)^2} \right) \pmod{2^n} \\ &\equiv -\left( 1^2+3^2+5^2+\dots+(2^n-1)^2 \right) \pmod{2^n}. \end{align*}Using the identity $1^2 + 3^2 + \dots + (2m-1)^2 = \frac{m(m^2-1)}{6}$, we conclude $S \equiv 2^{n-1} \pmod{2^n}$. Putting $S$ back into the main calculation finally gives \[ (Y+1)(Y+3)(Y+5)\dots(Y+(2^n-1)) = (2^{n-1})!! \left( 1 + 2^{n-1} \right) \pmod{2^{3n}} \]and the proof ends here. $\blacksquare$

First, note that for all positive integers $n$, we have\[v_2\left[\binom{2^{n+1}}{2^n}\right] = v_2[2^{n+1}!] - 2v_2[2^n!] = (2^{n + 1} - 1) - 2(2^n - 1) = 1\]for all positive integers $n$ by Legendre. So it remains to show that\[v_2\left[\frac{\binom{2^{n+1}}{2^n}}{\binom{2^{n}}{2^{n-1}}} - 1\right] = v_2[N] - v_2\left[\binom{2^{n}}{2^{n-1}}\right] = 3n-1.\]Using the property that $2k! = k! \times 2^k \times (2k-1)!!$ for all positive integers $k$ where we let $m = 2^{n-1}$, we may rewrite\begin{align*} \frac{\binom{2^{n+1}}{2^n}}{\binom{2^{n}}{2^{n-1}}} - 1&= \frac{(4m)!}{(2m)!^2} \times \frac{m!^2}{(2m)!} - 1\\&= \frac{(2m)! \times 2^{2m} \times (4m - 1)!!}{(2m)!^2} \times \frac{m!^2}{m! \times 2^m \times (2m - 1)!!} - 1\\&= \frac{2^m \times m!}{(2m)!} \times \frac{(4m-1)!!}{(2m-1)!!} - 1\\&= \frac{(4m - 1)!!}{(2m - 1)!!^2} - 1\\&= \frac{(2^{n + 1} - 1)\ldots (2^n + 1)}{(2^n - 1)!!} - 1\\&= \frac{(2^{n + 1} - 1)\ldots (2^n + 1) - (2^n - 1)!!}{(2^n - 1)!!} \end{align*}and since the denominator is odd, it suffices to show that $v_2[(2^{n + 1} - 1)\ldots (2^n + 1) - (2^n - 1)!!] = 3n - 1$. Define the polynomial $P(x) = (x + 1)(x + 3)\ldots (x + (2^n - 1)) - (x - 1)(x - 3)\ldots (x - (2^n - 1))$. Note that $P(2^n)$ is the expression in question so we wish to prove that $v_p[P(2^n)] = 3n-1$. Note that $P$ is odd since even degree terms cancel out. Clearly, we need only prove that $v_2[C \times 2^n] = 3n - 1 \implies v_2[C] = 2n - 1$ where $C$ is the coefficient of the $x$ term since all other terms have degree $\geq 3$ and hence $v_2$ of them is $\geq 3n$. Upon a little bit of expansion we see that\[C = 2\times (2n-1)!! \times \left(\frac11 + \frac13 + \ldots + \frac{1}{2^n - 1}\right)\]so it remains to show that $v_2\left[\frac11 + \frac13 + \ldots + \frac{1}{2^n - 1}\right] = 2n - 2$. We can pair terms whose denominators add to $2^n$ as follows:\[\frac11 + \frac13 + \ldots + \frac{1}{2^n - 1} = 2^n \left(\frac{1}{1 \times (2^n - 1)} + \ldots + \frac{1}{(2^{n-1} - 1) \times (2^{n - 1} + 1)}\right) = 2^{n-1}\left(\frac{1}{1 \times (2^n - 1)} + \ldots + \frac{1}{(2^n - 1) \times 1}\right)\]so it suffices to show $v_2\left[\frac{1}{1 \times (2^n - 1)} + \ldots + \frac{1}{(2^n - 1) \times 1}\right] = n - 1 \iff \frac{1}{1 \times (2^n - 1)} + \ldots + \frac{1}{(2^n - 1) \times 1} \equiv 2^{n-1} \pmod{2^n}$. Rewrite this as\[\sum_{\text{odd } k = 1}^{2^n - 1} \frac{1}{k \times(2^n - k)} \equiv \sum_{\text{odd } k = 1}^{2^n - 1} -(k^{-1})^2 \equiv -(1^2 + 3^2 + \ldots + (2^n - 1)^2) \pmod{2^n}\]Upon evaluation using sum of consecutive squares we get $\tfrac{(2^n - 1)(2^n)(2^{n+1} - 1)}{6} - \tfrac{4(2^{n-1} - 1)(2^{n-1})(2^n - 1)}{6} = 2^{n-1} \times \text{odd}$ hence indeed the expression is $2^{n-1}$ modulo $2^n$ so we are done. $\blacksquare$

Let $O$ be the set of odd integers. Note that \[\binom{2^{k}}{2^{k - 1}} = 2\prod_{i=1}^{k-1}\prod_{2^i < m < 2^{i+1},m\in O}m^{i-k+2}\]and \[\binom{2^{k+1}}{2^{k}} = 2\prod_{i=1}^{k}\prod_{2^i < m < 2^{i+1},m\in O}m^{i-k+1} = \binom{2^{k}}{2^{k - 1}} \cdot \frac{\displaystyle\prod_{2^k<m<2^{k+1},m\in O}m}{\displaystyle\prod_{m<2^k,m \in O}m},\]so it suffices to show that the $2$-adic value of \[\displaystyle\prod_{2^k<m<2^{k+1},m\in O}m-\displaystyle\prod_{m<2^k,m \in O}m\]is $3k-1$. Some computation gives that \[\displaystyle\prod_{2^k<m<2^{k+1},m\in O}m-\displaystyle\prod_{m<2^k,m \in O}m=\displaystyle\prod_{0 \le m <2^{k-1}}(2m+1+2^k)-\displaystyle\prod_{0 \le m <2^{k-1}}(2m+1) =\]\[2^{3k}A + 2^{2k}\sum_{0\le m<n<2^{k-1}}\frac{1}{(2m+1)(2n+1)}\displaystyle\prod_{0 \le m <2^{k-1}}(2m+1)+2^{k}\sum_{0\le m<2^{k-1}}\frac{1}{2m+1}\displaystyle\prod_{0 \le m <2^{k-1}}(2m+1)\]for some integer $A$. It is enough to show that the $2$-adic value of \[2^{k}\sum_{0\le m< n<2^{k-1}}\frac{1}{(2m+1)(2n+1)}+\sum_{0\le m<2^{k-1}}\frac{1}{2m+1}\]is $2k-1$. Now, let \[\sum_{0\le m<2^{k-1}}\frac{1}{2m+1} = S.\]Remark that by PFTB 3.11, $\nu_2(S)=2k-2$. Then, it is sufficient to show that \[2^k\sum_{0\le m< n<2^{k-1}}\frac{1}{(2m+1)(2n+1)} \equiv S\pmod{2^{2k}}.\]Observe that \[2^{k+1}\sum_{0\le m\le n<2^{k-1}}\frac{1}{(2m+1)(2n+1)}\equiv 2^kS^2 - 2^k\sum_{0\le m<2^{k-1}}\frac{1}{(2m+1)^2}\pmod{2^{2k+1}}.\]As $\nu_2(2^kS^2) = k+2(2k-2)=5k-4>2k+1$, it suffices to demonstrate \[\sum_{0\le m<2^{k-1}}\frac{2^k}{(2m+1)(2^k-2m-1)} \equiv 2S\equiv -2^k\sum_{0\le m<2^{k-1}}\frac{1}{(2m+1)^2}\pmod{2^{2k+1}}.\]Equivalently, it suffices to demonstrate \[\sum_{0\le m<2^{k-1}} \frac{1}{2m+1}\left(\frac{1}{2^k-2m-1}+\frac{1}{2m+1}\right)\equiv 0\pmod{2^{k+1}}.\]Alternatively, it suffices to demonstrate \[\sum_{0\le m<2^{k-1}}\frac{1}{(2m+1)(2^k-2m-1)(2m+1)}\equiv 0\pmod{2}.\]This final result is trivial because the sum is simply $2^{k-1}\equiv 0\pmod{2}$, so we are done.

Let $2^{k-1}=n$ and let the given expression be $N.$ Note that for any $m,$ we have $(2m)!=2^m\cdot m!\cdot (2m-1)!!.$ It follows that \[N=\binom{4n}{2n}-\binom{2n}{n}=\binom{2n}{n}\Bigg(\binom{4n}{2n}\binom{2n}{n}^{-1}-1\Bigg)=\]\[=\binom{2n}{n}\Bigg(\frac{2^{2n}\cdot (2n)!\cdot (4n-1)!!}{2^n\cdot n!\cdot (2n-1)!!}\cdot\bigg(\frac{2^n\cdot n!\cdot (2n-1)!!}{n!}\bigg)^{-1} -1\Bigg)=\]\[=\binom{2n}{n}\Bigg(\frac{(4n-1)!!}{(2n-1)!!^2}\cdot\frac{(2n)!}{2^n\cdot n!\cdot (2n-1)!!}-1\Bigg)=\binom{2n}{n}\Bigg(\frac{(4n-1)!!}{(2n-1)!!^2}-1\Bigg).\]We want to compute $\nu_2\big(N\big).$ Begin by observing that since $\nu_2(m!)=m-s_2(m)$ then because $n=2^{k-1}$ we have \[\nu_2\Bigg(\binom{2n}{n}\Bigg)=\big(2^k-s_2(s^k)\big)-2\big(2^{k-1}-s_2(2^{k-1})\big)=1.\]Therefore, to show that $\nu_2\big( N\big)=3k$ it only remains to prove the folliowing assertion \[3k-1=\nu_2\Bigg(\frac{(4n-1)!!}{(2n-1)!!^2}-1\Bigg)=\nu_2\big((4n-1)!!-(2n-1)!!^2\big)\iff\]\[\iff 3k-1=\nu_2\big((2n+1)(2n+3)\cdots (4n-1)-(2n-1)!!\big).\]Recall that $n=2^{k-1}$ and notice that $(2n+1)(2n+3)\cdots (4n-1)-(2n-1)!!$ can be rewritten as such: \[\prod_{i=1}^{2^{k-1}}\big(2^k+(2i-1)\big)-\prod_{i=1}^{2^{k-1}}\big(2^k-(2i-1)\big)=2^{3k}\cdot C_0+2^{k}\cdot C_1\]for some constants $C_0$ and $C_1.$ But $C_1$ is the coefficient of $X$ in the above expression viewed as a polynomial. Hence $C_1$ can be computed to \[C_1=2\cdot (2n-1)!!\cdot\bigg(\frac{1}{1}+\frac{1}{3}+\cdots+\frac{1}{2^k-1}\bigg).\]Now, to show that $\nu_2\big(2^{3k}\cdot C_0+2^k\cdot C_1\big)=3k-1$ we only have to show that $\nu_2(C_1)=2k-1.$ Or, in other words, we want to show that \[\nu_2\bigg(\frac{1}{1}+\frac{1}{3}+\cdots+\frac{1}{2^k-1}\bigg)=2k-2.\]This can be easily be seen by pairing the terms $1/i$ and $1/(2^k-i),$ summing, and analysing modulo $2^k.$

Replace $k$ with $n$, just because. By Kummer's theorem we have $\nu_2\left(\binom{2^{i+1}}{2^i}\right)=1$ for all $i$. Hence by dividing out all powers of $2$ it suffices to show that the $\nu_2$ of $$\frac{(2^1-1)!!\ldots(2^{n+1}-1)!!}{((2^1-1)!!\ldots(2^n-1)!!)^2}-\frac{(2^1-1)!!\ldots(2^n-1)!!}{((2^1-1)!!\ldots(2^{n-1}-1)!!)^2}=\frac{(2^{n+1}-1)!!}{(2^1-1)!!\ldots(2^n-1)!!}-\frac{(2^n-1)!!}{(2^1-1)!!\ldots(2^{n-1}-1)!!},$$where we count individual terms in the product by their $\nu_2$. Since all of these terms are odd, by multiplying through it suffices to show that the $\nu_2$ of $(2^{n+1}-1)!!-((2^n-1)!!)^2$ is $3n-1$, which is equivalent to $$\nu_2((2^n+(2^n-1))(2^n+(2^n-3))\ldots(2^n+1)-(2^n-1)(2^n-3)\ldots(1))=3n-1.$$ Considering the expansion of this product as a "polynomial in $2^n$" and then dividing by $(2^n-1)!!$, this is equivalent to saying that $$2^n\left(\sum_{\substack{1 \leq i \leq 2^n\\i\text{ odd}}} \frac{1}{i}\right)+2^{2n}\left(\sum_{\substack{1 \leq i<j<2^n\\i,j\text{ odd}}} \frac{1}{ij}\right) \equiv 2^{3n-1} \pmod{2^{3n}} \iff \sum_{\substack{1 \leq i \leq 2^n\\i\text{ odd}}} \frac{1}{i}+2^{n-1}\left(\sum_{\substack{1 \leq i \leq 2^n\\i\text{ odd}}} \frac{1}{i}\right)^2-2^{n-1}\sum_{\substack{1 \leq i \leq 2^n\\i\text{ odd}}} \frac{1}{i^2} \equiv 2^{2n-1} \pmod{2^{2n}}.$$We now turn to evaluating $$\sum_{\substack{1 \leq i \leq 2^{n-1}\\i\text{ odd}}} \frac{1}{i^2} \pmod{2^n}.$$Since $x^2=(-x)^2$, this quantity is $$\sum_{\substack{1 \leq i \leq 2^{n-1}\\i\text{ odd}}} i^2=\sum_{j=1}^{2^{n-2}} (2j-1)^2=\sum_{j=1}^{2^{n-2}} (4j^2-4j+1)=\frac{2(2^{n-2})(2^{n-2}+1)(2^{n-1}+1)}{3}-2(2^{n-2})(2^{n-2}+1)+2^{n-2}=2^{n-1}(2^{n-2}+1)\left(\frac{2^{n-1}-2}{3}\right)+2^{n-2} \equiv 2^{n-2} \pmod{2^n}.$$Thus, \begin{align*} \sum_{\substack{1 \leq i \leq 2^n\\i\text{ odd}}} \frac{1}{i}=\sum_{\substack{1 \leq i \leq 2^{n-1}\\i\text{ odd}}} \left(\frac{1}{i}+\frac{1}{2^n-i}\right)=\sum_{\substack{1 \leq i \leq 2^{n-1}\\i\text{ odd}}} -\frac{2^n}{i^2-2^ni}&=-2^{2n-2} \pmod{2^{2n}}\\ 2^n \mid \sum_{\substack{1 \leq i \leq 2^n\\i\text{ odd}}} \implies 2^{n-1}\left(\sum_{\substack{1 \leq i \leq 2^n\\i\text{ odd}}} \frac{1}{i}\right)^2&\equiv 0 \pmod{2^{2n}}\\ -2^{n-1}\sum_{\substack{1 \leq i \leq 2^n\\i\text{ odd}}} \frac{1}{i^2} \equiv -2^{n-2} \pmod{2^{2n}}. \end{align*}Hence the desired quantity is $-2^{2n-1} \equiv 2^{2n-1} \pmod{2^{2n}}$; done. $\blacksquare$

For some reason, this would make a great HMMT A8/A9/A10 or something like that. I claim that $N = {2^{k+1} \choose 2^k} - {2^k \choose 2^{k-1}}$ is congruent to $2^{3k}$ modulo $2^{3k+1}$, which will imply the problem statement. Note that \begin{align*} N = \frac{(2^{n+1})!}{(2^n)!^2} - \frac{(2^n)!}{(2^{n-1})!^2} &\equiv 2^{3n} \pmod {2^{3n+1}} \\ \iff \frac{(2^{n+1})! - ((2^{n-1}+1)\cdots(2^n))^2 (2^n)!}{(2^n)!^2} &\equiv 2^{3n} \pmod {2^{3n+1}} \\ \iff \frac{2^{2^{n+1} - 1} \cdot \prod_{i=0}^n (2^{i+1} - 1)!! - 2^{2^n - 1} \cdot \prod_{i=0}^{n-1} (2^{i+1}-1)!! \cdot 2^{2^n} \cdot (2^n - 1)!!^2}{2^{2^{n+1} - 2} \prod_{i=0}^{n-1} (2^{i+1}-1)!!^2} &\equiv 2^{3n} \pmod {2^{3n+1}} \\ \iff \prod_{i=0}^n (2^{i+1} - 1)!! - \prod_{i=0}^{n-1} (2^{i+1} - 1)!! \cdot (2^n - 1)!!^2 &\equiv 2^{3n-1} \pmod {2^{3n}} \\ \iff (2^{n+1} - 1)!! - (2^n - 1)!!^2 &\equiv 2^{3n-1} \pmod {2^{3n}} \\ \iff (2^n+1)(2^n + 3) \cdots (2^n + (2^n-1)) - (2^n-1)!! &\equiv 2^{3n-1} \pmod {2^{3n}} \\ \iff 2^{2n} \sum_{k < \ell} \frac 1{(2k+1)(2\ell + 1)} + 2^n \sum_{k=1}^{2^{n-1}} \frac 1{2n-1} &\equiv 2^{3n-1} \pmod {2^{3n}} \\ \iff 2^n \sum_{k < \ell} \frac 1{(2k+1)(2\ell + 1)} + \frac{2^n}{1 \cdot (2^n - 1)} + \frac {2^n}{3 \cdot (2^n- 3)} + \cdots + \frac{2^n}{(2^{n-1}-1)(2^{n-1}+1)} &\equiv 2^{2n-1} \pmod {2^{2n}} \\ \iff \sum_{k \neq \ell} \frac 1{(2k+1)(2\ell+1)} + 2\left(\frac 1{1 \cdot (2^n- 1)} + \frac 1{3 \cdot (2^n-3)} + \cdots + \frac 1{(2^{n-1}-1)(2^{n-1}+1)}\right) &\equiv 2^n \pmod {2^{n+1}} \\ \iff \sum_{i=1}^{2^n} \frac 1{2i-1}\left(\frac 11+ \frac 13 + \frac 15 + \cdots + \frac 1{2^n - 1} - \frac 1{2i+1} \right) + 2\sum_{i=1}^{2^{n-2}} \frac 1{(2i+1)(2^n - 2i-1)} &\equiv 2^n \pmod {2^{n+1}} \\ \iff 2\left(\frac 1{1^2} + \frac 1{3^2} + \cdots + \frac 1{(2^n - 1)^2}\right) &\equiv 2^n \pmod {2^{n+1}} \\ \iff 1^2+3^2+5^2+\cdots+(2^n - 1)^2 &\equiv 2^{n-1} \pmod {2^n} \\ \iff \frac{2^n \cdot (2^n+1) \cdot (2^{n+1}+1)}6 - \frac{4(2^{n-1}) \cdot (2^{n-1}+1) \cdot (2^n + 1)}6 &\equiv 2^{n-1} \pmod {2^n} \\ \iff \frac{(2^n+1) \cdot (2^{n+1} + 1) - 2(2^{n-1} + 1)(2^n + 1)}3 &\equiv 1 \pmod 2. \end{align*}This is obviously true.

Let $n=2^{k-1}$. Note that \begin{align*} \binom{4n}{2n} &= \frac{(4n)!}{(2n)!^2} = \frac{2^{2n}(2n)!(4n-1)!!}{(2n)!^2} = \frac{2^{2n}}{(2n)!}(4n-1)!! \\ \binom{2n}{n} &= \frac{(2n)!}{(n!)^2} = \frac{1}{(2n)!}\left(\frac{(2n)!}{n!}\right)^2 = \frac{2^{2n}}{(2n)!}(2n-1)!!^2 \end{align*}so \[\binom{4n}{2n} = (2n-1)!!\left(\frac{2^{2n}}{(2n)!}\right)((4n-1)(4n-3)\dots(2n+1)-(2n-1)(2n-3)\dots(1))\]Clearly, $\nu_2((2n-1)!!\left(\tfrac{2^{2n}}{(2n)!}\right))=1$ so it suffices to show that \[\nu_2((4n-1)(4n-3)\dots(2n+1)-(2n-1)(2n-3)\dots(1))=3k-1\]To do this, we take $\pmod {2^{3k}}$. Let $P(x)=(2x-1)(2x-3)\dots(x+1)-(x-1)(x-3)\dots(1)$ then note that $P$ is odd. Furthermore, note that since we can take $\pmod {2^{3k}}$, and $x=2^k$, we only need to worry about the constant coefficient of $P$. We need to show that \[\nu_2\left(2(x-1)!!\left(\frac{1}{1}+\frac{1}{3}+\dots+\frac{1}{x-1}\right)\right)=2k-1\]But note that \[2\left(\frac{1}{1}+\frac{1}{3}+\dots+\frac{1}{x-1}\right)=\left(\frac{1}{1}+\frac{1}{x-1}\right)+\left(\frac{1}{3}+\frac{1}{x-3}\right)+\dots+\left(\frac{1}{x-1}+\frac{1}{1}\right)\]and $\tfrac{1}{a}+\tfrac{1}{x-a}=\tfrac{x}{a(x-a)}\equiv -xa^{-2}\pmod 2^{2k}$. The sum of the inverses of $a^2$ is the same as the sum of $a^2$ so we can calculate that and we're done.

My solution is fairly different from the others in this thread so far—I'm posting it because I really like my main claim.

The answer is $\boxed{3n}.$ We have $$N = \frac{(2^{n+1})!(2^{n-1})!^{2}-(2^{n})!^{3}}{(2^{n})!^{2}(2^{n-1})!^{2}} = \frac{\prod_{\lceil \log _{i}\rceil = n+1} i-\left(\prod_{\lceil \log _{i}\rceil = n}i\right)^2}{(2^{n})!}.$$Then, \begin{align*} \left(\prod_{i = 2^{n}+1}^{2^{n+1}} i\right)-\left(\prod_{i=2^{n-1}+1}^{2^{n}} i\right)^{2} & = \left(\prod_{i=2^{n-1}+1}^{2^{n}} i\right)\left(2^{2^{n-1}} \cdot \prod_{\overset{\lceil \log_{2}(i) \rceil = n+1}{i \equiv 1 \pmod 2}}i-\prod_{i=2^{n-1}+1}^{2^{n}}i\right) \\ & = \left(\prod_{i=2^{n-1}+1}^{2^{n}} i\right)\left(2^{2^{n-1}}\right)\left(\prod_{\overset{\lceil \log_{2}(i) \rceil = n+1}{i \equiv 1 \pmod 2}}i - \prod_{\overset{\lceil \log_{2}(i) \rceil \le n}{i \equiv 1 \pmod 2}}i\right) \\ & = \frac{(2^{n})!}{(2^{n-1})!} \cdot 2^{2^{n-1}} \cdot \left(\prod_{\overset{\lceil \log_{2}(i) \rceil = n+1}{i \equiv 1 \pmod 2}}i - \prod_{\overset{\lceil \log_{2}(i) \rceil \le n}{i \equiv 1 \pmod 2}}i\right). \end{align*} The factor $\frac{(2^{n})!}{(2^{n-1})!}$ has $2^{n-1}$ factors of two by Legendre's. So, we need to find the number of factors of two of the last expression. Notice that $$\prod_{\overset{\lceil \log_{2}(i) \rceil = n+1}{i \equiv 1 \pmod 2}}i - \prod_{\overset{\lceil \log_{2}(i) \rceil \le n}{i \equiv 1 \pmod 2}}i = \prod_{\overset{2^{n}+1\le i \le 2^{n+1}}{i \equiv 1 \pmod 2}}i-\prod_{\overset{1 \le i \le 2^{n}}{i \equiv 1 \pmod 2}}i=\prod_{\overset{1 \le i \le 2^{n}}{i \equiv 1 \pmod 2}}(i+2^{n})-\prod_{\overset{1 \le i \le 2^{n}}{i \equiv 1 \pmod 2}}i.$$So, we get $$\prod_{\overset{1 \le i \le 2^{n}}{i \equiv 1 \pmod 2}}(i+2^{n})-\prod_{\overset{1 \le i \le 2^{n}}{i \equiv 1 \pmod 2}}i = \sum_{j=1}^{2^{n-1}} 2 ^{nj}S_{j}(1,3,5,\dots, 2^{n}-1),$$where $S_{j}$ is the symmetric sum. For $j=1,$ we get $2^{n} \cdot (1+3+\cdots+2^{n}-1) = 2^{n} \cdot (2^{n-1})^{2} = 2^{3n-2}.$ For $j=2,$ we get $$2^{2n} \cdot S_{2}(1,3,\dots, 2^{n}-1) = \frac{2^{2n} \cdot [(1+3+\cdots+2^{n}-1)^{2} - (1^{2}+3^{2}+\cdots+(2^{n}-1)^{2})]}{2} $$$$= 2^{2n-1} \cdot \left[2^{4n-4} - \frac{2^{n-1}(2^{n}-1)(2^{n}+1)}{3}\right].$$So, $$\sum_{j=1}^{2} 2 ^{nj}S_{j}(1,3,5,\dots, 2^{n}-1) = 2^{3n-2}+2^{6n-3} - \frac{2^{3n-2}(2^{2n}-1)}{3} = 2^{6n-3}+2^{3n-2} \cdot \frac{2-2^{2n}}{3},$$so this has $3n-1$ factors of $2.$ For $j \ge 3,$ the terms are all multiples of $2^{3n},$ so $$\nu_{2}\left(\prod_{\overset{\lceil \log_{2}(i) \rceil = n+1}{i \equiv 1 \pmod 2}}i - \prod_{\overset{\lceil \log_{2}(i) \rceil \le n}{i \equiv 1 \pmod 2}}i\right) = 3n-1.$$Hence, \begin{align*} \nu_{2}(N) &= 2^{n-1}+\nu_{2}\left(\frac{(2^{n})!}{(2^{n-1})!}\right)+\nu_{2}\left(\prod_{\overset{\lceil \log_{2}(i) \rceil = n+1}{i \equiv 1 \pmod 2}}i - \prod_{\overset{\lceil \log_{2}(i) \rceil \le n}{i \equiv 1 \pmod 2}}i\right)-\nu_{2}(2^{n})\\ & = 2^{n-1}+2^{n-1}+3n-1-(2^{n}-1)\\ &= 3n, \end{align*}as desired.