Given a square-free integer n≥3, evaluate the sum ∑k=1(n−2)(n−1)⌊3kn⌋.
Solution
Let S be the set of lattice points in the rectangle [1,(n−2)(n−1)]×[1,n−1]. Since n is square-free, no point of S lies on the curve y=3nx, so the latter splits S into two non-empty sets. The required sum counts the points of S below the curve, while the sum ∑k=1n−1⌊k3/n⌋ counts the points of S above the curve. Since ∣S∣=(n−2)(n−1)2, it is sufficient to evaluate the latter sum.
To this end, let tk=k3/n−⌊k3/n⌋, k=1,2,…,n−1. Clearly, 0≤tk<1 for all k, and since n is square-free, the tk are, in fact, all positive. Since k3/n+(n−k)3/n=3k2−3kn+n2 is integral, so is tk+tn−k, and since 0<tk+tn−k<2, it follows that tk+tn−k=1. Hence n−1=k=1∑n−1(tk+tn−k)=2k=1∑n−1tk=2k=1∑n−1nk3−2k=1∑n−1⌊nk3⌋=2n(n−1)2−2k=1∑n−1⌊nk3⌋. Consequently, ∑k=1n−1⌊k3/n⌋=(n−2)(n2−1)/4, and k=1∑(n−2)(n−1)⌊3kn⌋=(n−2)(n−1)2−(n−2)(n2−1)/4=(n−2)(n−1)(3n−5)/4.
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: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.