\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{Shortlist 2007 N4}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 3}
\maketitle

\section*{Problem}
Let $n \ge 2$ be an integer and let
\[ N = \binom{2^{n+1}}{2^n} - \binom{2^n}{2^{n-1}}. \]
Compute $\nu_2(N)$ in terms of $n$.

\section*{Video}
\href{https://www.youtube.com/watch?v=L-gy9W0sY-8&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/L-gy9W0sY-8}}

\section*{External Link}
\url{https://aops.com/community/p1187214}

\newpage

\section*{Solution}
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:
\begin{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}}. \]
\end{claim*}
\begin{proof}
  Let $Y = 2^n$, so we are worning 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 tanen 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+ \left( \frac{1}{1\cdot3} + \frac{1}{1\cdot5} + \dots +
      \frac{1}{(2^n-3)(2^n-1)} \right)\\
    &= \left( \frac{1}{1^2} + \frac{1}{3^2} + \dots +
      \frac{1}{(2^{n-1}-1)^2} \right) \\
    &\qquad+ \left( \frac{1}{1\cdot3} + \frac{1}{1\cdot5} + \dots +
      \frac{1}{(2^n-3)(2^n-1)} \right) \\
    &\qquad- 2 \left( \frac{1}{1^2} + \frac{1}{3^2} + \dots +
      \frac{1}{(2^{n-1}-1)^2} \right) \\
    &\equiv \left( \frac11+\frac13+\dots+\frac{1}{2^{n-1}-1} \right)^2 \\
    &\qquad+ \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) \\
    &\qquad - \left( \frac{1}{1^2} + \frac{1}{3^2} + \dots +
      \frac{1}{(2^n-1)^2} \right) \pmod{2^n}.
  \end{align*}
  Let $T = \frac11 + \frac13 + \dots + \frac{1}{2^{n-1}-1}$.
  By a pairing argument again, it follows $2^{n-1} \mid T$,
  so actually $T^2 \equiv 0 \pmod{2^n}$.
  In conclusion, we have
  \begin{align*}
    S &\equiv - \left( \frac1{1^2} + \frac{1}{3^2} + \dots +
      \frac{1}{(2^n-1)^2} \right) \\
    &\equiv -\left( 1^2+3^2+5^2+\dots+(2^n-1)^2 \right).
  \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.
\end{proof}

\end{document}
