I bet you can't solve this

I claim that all of $1, 2, 3, \ldots, 2008$ can be the value of $f(2007)$ , and no others. This means the sum is $1+2+3+\ldots+2008 = 2017036$ and thus the sum of its digits is $2+0+1+7+0+3+6 = \boxed{19}$ .

First, the proof that all of them work. The following $f$ works, for $k = 0, 1, 2, \ldots, 2007$ :

$\displaystyle f(n) = k \left\lfloor \frac{n}{2007} \right\rfloor + 1$

If $k < 2007$ , then we can verify that $f(n) \le n$ for all $n$ . Also, we have the easy property $\lfloor x+y \rfloor \ge \lfloor x \rfloor + \lfloor y \rfloor$ for all reals $x,y$ . Thus,

$\displaystyle\begin{aligned} f(m+n) &= k \left\lfloor \frac{m+n}{2007} \right\rfloor + 1 \\ &\ge k \left( \left\lfloor \frac{m}{2007} \right\rfloor + \left\lfloor \frac{n}{2007} \right\rfloor \right) + 1 \\ &\ge k \left( \left\lfloor \frac{m}{2007} \right\rfloor + \left\lfloor \frac{f(n)}{2007} \right\rfloor \right) + 1 \\ &= k \left\lfloor \frac{m}{2007} \right\rfloor + 1 + k \left\lfloor \frac{f(n)}{2007} \right\rfloor + 1 - 1 \\ &= f(m) + f(f(n)) - 1 \end{aligned}$

For $k = 2007$ , we don't have the property that $f(n) \le n$ for all $n$ . We do still retain the property that $\left\lfloor \frac{n}{2007} \right\rfloor = \left\lfloor \frac{f(n)}{2007} \right\rfloor$ , though:

$\displaystyle\begin{aligned} \left\lfloor \frac{f(n)}{2007} \right\rfloor &= \left\lfloor \frac{2007 \lfloor n/2007 \rfloor + 1}{2007} \right\rfloor \\ &= \left\lfloor \left\lfloor \frac{n}{2007} \right\rfloor + \frac{1}{2007} \right\rfloor \\ &= \left\lfloor \frac{n}{2007} \right\rfloor + \left\lfloor \frac{1}{2007} \right\rfloor \\ &= \left\lfloor \frac{n}{2007} \right\rfloor \end{aligned}$

Thus we can approach exactly as the above.

Now that we have proven those $f$ work, we simply plug in $n = 2007$ to get $f(2007) = k+1$ . Since $k$ ranges from 0 to 2007, $f(2007)$ ranges from 1 to 2008.

To prove that no other value of $f(2007)$ is possible, it suffices to prove that $f(n) \le n+1$ for all $n$ , so $f(2007) \le 2008$ .

First, note that $f(f(n)) \ge 1$ (because $f$ has codomain the naturals), so $f(m+n) \ge f(m) + f(f(n)) - 1 \ge f(m) + 1 - 1 = f(m)$ . In other words, $f$ is non-decreasing.

Now, suppose there exists some $a$ such that $f(a) \ge a+2$ . We claim that $f(ka) \ge k(a+1) + 1$ for all positive integer $k$ by induction on $k$ . The base case $k = 1$ is just the assumption, and for the inductive step,

$\begin{aligned} f((k+1)a) &= f(ka + a) \\ &\ge f(ka) + f(f(a)) - 1 \\ &\ge k(a+1) + 1 + f(a+2) - 1 \\ &\ge k(a+1) + (a+2) \\ &= (k+1)(a+1) + 1 \end{aligned}$

In particular, for $k = a$ , we have $f(a^2) \ge a^2 + a + 1$ . Thus,

$\begin{aligned} f(a + a^2) &\ge f(a) + f(f(a^2)) - 1 \\ &\ge (a+2) + f(a^2 + a + 1) - 1 \\ &\ge (a+1) + f(a^2 + a) \end{aligned}$

In other words, $a \le -1$ , contradiction. Thus there can be no such $a$ , proving that $f(n) \le n+1$ for all $n$ . This completes the proof.