Maths Olympiad Prep

Library / /338 of 377

Algebra Difficulty 5.7 AIME, harder Prove it United States

Problem:

Let f(n)=k=1n1kf(n) = \sum_{k=1}^{n} \frac{1}{k}. Then there exist constants γ\gamma, cc, and dd such that
f(n)=ln(n)+γ+cn+dn2+O(1n3) f(n) = \ln(n) + \gamma + \frac{c}{n} + \frac{d}{n^{2}} + O\left(\frac{1}{n^{3}}\right)
where the O(1n3)O\left(\frac{1}{n^{3}}\right) means terms of order 1n3\frac{1}{n^{3}} or lower. Compute the ordered pair (c,d)(c, d).

Solution

Solution:

Answer: (12,112)\left(\frac{1}{2}, -\frac{1}{12}\right)

From the given formula, we pull out the term kn3\frac{k}{n^{3}} from O(1n4)O\left(\frac{1}{n^{4}}\right), making f(n)=log(n)+γ+cn+dn2+kn3+O(1n4)f(n) = \log(n) + \gamma + \frac{c}{n} + \frac{d}{n^{2}} + \frac{k}{n^{3}} + O\left(\frac{1}{n^{4}}\right). Therefore,
f(n+1)f(n)=log(n+1n)c(1n1n+1)d(1n21(n+1)2)k(1n31(n+1)3)+O(1n4) f(n+1) - f(n) = \log\left(\frac{n+1}{n}\right) - c\left(\frac{1}{n} - \frac{1}{n+1}\right) - d\left(\frac{1}{n^{2}} - \frac{1}{(n+1)^{2}}\right) - k\left(\frac{1}{n^{3}} - \frac{1}{(n+1)^{3}}\right) + O\left(\frac{1}{n^{4}}\right)
For the left hand side, f(n+1)f(n)=1n+1f(n+1) - f(n) = \frac{1}{n+1}. By substituting x=1nx = \frac{1}{n}, the formula above becomes
xx+1=log(1+x)cx21x+1dx3x+2(x+1)2kx4x2+3x+3(x+1)3+O(x4) \frac{x}{x+1} = \log(1+x) - c x^{2} \cdot \frac{1}{x+1} - d x^{3} \cdot \frac{x+2}{(x+1)^{2}} - k x^{4} \cdot \frac{x^{2} + 3x + 3}{(x+1)^{3}} + O\left(x^{4}\right)
Because xx is on the order of 1n\frac{1}{n}, 1(x+1)3\frac{1}{(x+1)^{3}} is on the order of a constant. Therefore, all the terms in the expansion of kx4x2+3x+3(x+1)3k x^{4} \cdot \frac{x^{2} + 3x + 3}{(x+1)^{3}} are of order x4x^{4} or higher, so we can collapse it into O(x4)O\left(x^{4}\right). Using the Taylor expansions, we get
x(1x+x2)+O(x4)=(x12x2+13x3)cx2(1x)dx3(2)+O(x4). x\left(1 - x + x^{2}\right) + O\left(x^{4}\right) = \left(x - \frac{1}{2} x^{2} + \frac{1}{3} x^{3}\right) - c x^{2}(1 - x) - d x^{3}(2) + O\left(x^{4}\right).
Coefficient comparison gives c=12c = \frac{1}{2} and d=112d = -\frac{1}{12}.

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.