## Monday, April 10, 2006

### Sum Square Function. Topic: Algebra/Sequences & Series. Level: Olympiad.

Problem: A function $f$ is defined for all positive integers and satisfies $f(1)=1996$, and $f(1)+f(2)+\cdots+f(n)=n^2f(n)$ for all $n>1$. Calculate the exact value of $f(1996)$.

Solution: Checking small values, we find $f(2) = \frac{1996}{3}$, $f(3) = \frac{1996}{6}$, and $f(4) = \frac{1996}{10}$. The denominators look awfully like the triangular numbers, so we claim that

$f(n) = \frac{2 \cdot 1996}{n(n+1)}$.

We will prove the result by strong induction.

Base Case - $f(1) = 1996$.

Induction Step - Assume that $f(k) = \frac{2 \cdot 1996}{k(k+1)}$ for $k = 1, \ldots, m$. We want to show that $f(m+1) = \frac{2 \cdot 1996}{(m+1)(m+2)}$. From the given condition we have

$f(1)+f(2)+\cdots+f(m)+f(m+1) = (m+1)^2f(m+1)$

$\frac{2 \cdot 1996}{1 \cdot 2}+\frac{2 \cdot 1996}{2 \cdot 3}+\frac{2 \cdot 1996}{m(m+1)} = m(m+2)f(m+1)$.

Note that $\frac{1}{k(k+1)} = \frac{1}{k}-\frac{1}{k+1}$, so the equation becomes

$2 \cdot 1996 \left( \frac{1}{1}-\frac{1}{2}+\frac{1}{2}-\frac{1}{3}+\cdots+\frac{1}{m}-\frac{1}{m+1} \right) = m(m+2)f(m+1)$

$2 \cdot 1996 \left(1-\frac{1}{m+1}\right) = m(m+2)f(m+1)$

$2 \cdot 1996 \left(\frac{m}{m+1}\right) = m(m+2)f(m+1)$,

which rearranges to

$f(m+1) = \frac{2 \cdot 1996}{(m+1)(m+2)}$,

completing the induction. Hence $f(1996) = \frac{2 \cdot 1996}{1996 \cdot 1997} = \frac{2}{1997}$. QED.

--------------------

Comment: Usually problems like these require you to play around with the problem for a while and once you think you see a pattern, conjecture it and hopefully prove it. Induction works well especially when they ask for a large value such as $1996$.

--------------------

Practice Problem: If $f(1) = k$, evaluate $f(k)$ with the same condition in the above problem.