1. ## Number Theory (2)

Find all $n \in \mathbb{N}$ such that $4 \mid \binom{2n}{n}.$

2. Spoiler:

$4 \mid \binom{2n}{n}$ if and only if $n$ is not of the form $2^k$.
Proof:

Using $n!!$ as the double factorial of $n$:

$\binom{2n}{n} = \frac{(2n)!}{n!^2} = \frac{(2n)!! (2n-1)!!}{n!^2} = \frac{2^n n!(2n-1)!!}{n!^2} = \frac{2^n(2n-1)!!}{n!}$

$2 \nmid (2n-1)!!$ and therefore $4 \mid \binom{2n}{n}$ if and only if $d \le n-2$, where $d$ satisfies $2^d \mid \mid n!$ (that is, $2^d \mid n!$, but $2^{d+1} \nmid n!$).
We'll use the fact that $n! = \prod_{p \le n} p^{\sum_{k=1}^{\infty} \lfloor n/p^k \rfloor}$ ( $p$ prime) (Legendre's formula). The exponent of $2$ in $n!$ is:
$d = \sum_{k=1}^{\infty} \lfloor \frac{n}{2^k} \rfloor = \sum_{k=1}^{\lfloor \log_2 n \rfloor} \lfloor \frac{n}{2^k} \rfloor \le \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{n}{2^k} = n (1-2^{- \lfloor \log_2 n \rfloor}) \le n(1-2^{- \log_2 n}) = n-1$
Where the equality signs of $\le$ are taken if and only if $n$ is a power of two. Thus, $d \le n-2$ if and only if $n$ is not a power of $2$, and so $4 \mid \binom{2n}{n}$ if and only if $n$ is not of the form $2^k$.
Q.E.D

3. Originally Posted by Unbeatable0
Spoiler:

$4 \mid \binom{2n}{n}$ if and only if $n$ is not of the form $2^k$.
Proof:

Using $n!!$ as the double factorial of $n$:

$\binom{2n}{n} = \frac{(2n)!}{n!^2} = \frac{(2n)!! (2n-1)!!}{n!^2} = \frac{2^n n!(2n-1)!!}{n!^2} = \frac{2^n(2n-1)!!}{n!}$

$2 \nmid (2n-1)!!$ and therefore $4 \mid \binom{2n}{n}$ if and only if $d \le n-2$, where $d$ satisfies $2^d \mid \mid n!$ (that is, $2^d \mid n!$, but $2^{d+1} \nmid n!$).
We'll use the fact that $n! = \prod_{p \le n} p^{\sum_{k=1}^{\infty} \lfloor n/p^k \rfloor}$ ( $p$ prime) (Legendre's formula). The exponent of $2$ in $n!$ is:
$d = \sum_{k=1}^{\infty} \lfloor \frac{n}{2^k} \rfloor = \sum_{k=1}^{\lfloor \log_2 n \rfloor} \lfloor \frac{n}{2^k} \rfloor \le \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{n}{2^k} = n (1-2^{- \lfloor \log_2 n \rfloor}) \le n(1-2^{- \log_2 n}) = n-1$
Where the equality signs of $\le$ are taken if and only if $n$ is a power of two. Thus, $d \le n-2$ if and only if $n$ is not a power of $2$, and so $4 \mid \binom{2n}{n}$ if and only if $n$ is not of the form $2^k$.
Q.E.D
that's an unbeatable solution!

4. Originally Posted by Unbeatable0
Spoiler:

$4 \mid \binom{2n}{n}$ if and only if $n$ is not of the form $2^k$.
Proof:

Using $n!!$ as the double factorial of $n$:

$\binom{2n}{n} = \frac{(2n)!}{n!^2} = \frac{(2n)!! (2n-1)!!}{n!^2} = \frac{2^n n!(2n-1)!!}{n!^2} = \frac{2^n(2n-1)!!}{n!}$

$2 \nmid (2n-1)!!$ and therefore $4 \mid \binom{2n}{n}$ if and only if $d \le n-2$, where $d$ satisfies $2^d \mid \mid n!$ (that is, $2^d \mid n!$, but $2^{d+1} \nmid n!$).
We'll use the fact that $n! = \prod_{p \le n} p^{\sum_{k=1}^{\infty} \lfloor n/p^k \rfloor}$ ( $p$ prime) (Legendre's formula). The exponent of $2$ in $n!$ is:
$d = \sum_{k=1}^{\infty} \lfloor \frac{n}{2^k} \rfloor = \sum_{k=1}^{\lfloor \log_2 n \rfloor} \lfloor \frac{n}{2^k} \rfloor \le \sum_{k=1}^{\lfloor \log_2 n \rfloor} \frac{n}{2^k} = n (1-2^{- \lfloor \log_2 n \rfloor}) \le n(1-2^{- \log_2 n}) = n-1$
Where the equality signs of $\le$ are taken if and only if $n$ is a power of two. Thus, $d \le n-2$ if and only if $n$ is not a power of $2$, and so $4 \mid \binom{2n}{n}$ if and only if $n$ is not of the form $2^k$.
Q.E.D
Wow! Where did you learn how to do all that?