Maths Olympiad Prep

Library / /2 of 15

Algebra Difficulty 4.3 AIME Prove it United States

Problem:
If f(1)=1f(1) = 1 and f(1)+f(2)+⋯+f(n)=n2f(n)f(1) + f(2) + \cdots + f(n) = n^{2} f(n) for every integer n≥2n \geq 2, evaluate f(2008)f(2008).

Solution

Solution:
n2f(n)−f(n)=f(1)+f(2)+⋯+f(n−1)=(n−1)2f(n−1)n^{2} f(n) - f(n) = f(1) + f(2) + \cdots + f(n-1) = (n-1)^{2} f(n-1)
hence f(n)=(n−1)2n2−1f(n−1)=n−1n+1f(n−1)f(n) = \frac{(n-1)^{2}}{n^{2} - 1} f(n-1) = \frac{n-1}{n+1} f(n-1).

Thus
f(2008)=20072009f(2007)=20072009⋅20062008f(2006)=20072009⋅20062008⋅20052007f(2005)=⋯=2007!2009⋅2008⋯4⋅3f(1)=22009⋅2008 \begin{aligned} f(2008) &= \frac{2007}{2009} f(2007) \\ &= \frac{2007}{2009} \cdot \frac{2006}{2008} f(2006) \\ &= \frac{2007}{2009} \cdot \frac{2006}{2008} \cdot \frac{2005}{2007} f(2005) \\ &= \cdots \\ &= \frac{2007!}{2009 \cdot 2008 \cdots 4 \cdot 3} f(1) \\ &= \frac{2}{2009 \cdot 2008} \end{aligned}

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.