## Factorial Divisibility

#### Problem

Given that `n` is a positive integer, prove that (2^{n})! is divisible by 2^{2n 1}

#### Solution

Firstly we write, 2^{2n 1} = 2^{n + n 1} = 2^{n} 2^{n 1}

Then, (2^{n})! = 1 2 3 ... (2^{n} 1) 2^{n}

Clearly, (2^{n})! is divisible by 2^{n}, but as 2^{n 1} 2^{n}, one of the earlier factors of (2^{n})! must be 2^{n 1}.

Hence (2^{n})! is divisible by 2^{2n 1}.

Problem ID: 40 (Mar 2001) Difficulty: 3 Star