Maths Olympiad Prep

Library / /155 of 520

Number theory Difficulty 5.8 AIME, harder Prove it

Lemma 9 Let x1x \geqslant 1. We have
mxψ(x/m)=ln([x]!).\sum_{m \leq x} \psi(x / m)=\ln ([x]!) .

Solution

Proof: By the definition of ψ(x)\psi(x) (Equation (33)), we have
mxψ(x/m)=mxkx/mΛ(k)=mxkmxΛ(k),\sum_{m \leq x} \psi(x / m)=\sum_{m \leq x} \sum_{k \leq x / m} \Lambda(k)=\sum_{m \leq x} \sum_{k m \leqslant x} \Lambda(k),

By making the integer variable substitution km=d,k=kk m=d, k=k, the above equation becomes
mxψ(x/m)=dxkdΛ(k)=dxlnd,\sum_{m \leqslant x} \psi(x / m)=\sum_{d \leqslant x} \sum_{k \mid d} \Lambda(k)=\sum_{d \leqslant x} \ln d,

The last step uses Equation (38). This thus proves Equation (39).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.