 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-3/1g/a/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

4^{n} = (1 + 1)^{2 n} = \sum_{k = 0}^{2 n} (k 2 n) .

The central binomial coefficient is the largest of these

2 n + 1

(n 2 n) \geq \frac{4 ^{n}}{2 n + 1} = \frac{2 ^{2 n}}{2 n + 1} .

For the upper bound, fix a prime number

p \leq 2 n

v_{p} ((n 2 n)) = \sum_{j \geq 1} (⌊ \frac{2 n}{p ^{j}} ⌋ - 2 ⌊ \frac{n}{p ^{j}} ⌋) .

Each summand is either zero or one. Hence the P-adic valuation satisfies

v_{p} ((n 2 n)) \leq ⌊ \frac{l o g ( 2 n )}{l o g p} ⌋ .

p \leq 2 n

, this implies

p^{v_{p} ((n 2 n))} \leq 2 n .

There are at most

2 n

such prime numbers. If instead

p > 2 n

, then

p^{2} > 2 n

, so the P-adic valuation is at most one. Multiplying the prime-power contributions therefore yields

(n 2 n) \leq (2 n)^{2 n} \prod_{p \leq 2 n p prime} p .

 New to topics? Read the docs here!