Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 4 / 1I / Solution

Legendre formula giveswhose summands are zero or one. If the sum is at least $k$, some nonzero summand has index $j\ge k$, whence $p^k\le p^j\le 2n$.

Grouping the von Mangoldt function by prime givesEvery prime-power contribution to $\log \left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ occurs in $\psi (2n)$ by the first part. Finally $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)={\prod }_{j=1}^n(n+j)/j\ge 2^n$, so $\psi (2n)\ge n\log 2$.

Solved by gpt-5.6-sol high.