My problems- 2

The solution is edited due to contribution from Kevin Zhang (see his comments below) to shorten the solution:

Since $f(n)=n^2-f(n-1)$ and $f(19) = 94\space \Rightarrow$

$\displaystyle \begin{aligned} f(20) & = 20^2 - f(19) = 20^2 - 94 \\ f(21) & = 21^2 - 20^2 + 94 \\ f(22) & = 22^2 - 21^2 + 20^2 - 94 \\ & ... \\ f(94) & = 94^2-93^2+92^2-91^2+90^2-89^2+...+22^2- 21^2 + 20^2 - 94 \\ & = (94-93)(94+93)+(92-91)(92+91)+(90-89)(90+89)+...+(22-21)(22+21) + 20^2 - 94 \\ & = 94+93+92+91+90+89+...+22+21 + 20^2 - 94 \\ & = \sum_{k=21} ^{94} {k} + 20^2 - 94 \\ & = 4255 + 400 - 94 = \boxed{4561} \end{aligned}$

Might be a similar method.. but shorter.. f(18)=267, f(20)=306, f(22)=349.... a notable pattern is observed that of 35,39,43 (i.e. diff=4) .. therefore, for f(94) which is 37th term from f(20) we need to add 37/2(43X2+(36X4)) to the f(20) term.. therefore 306+4255=4561.. and ans =561. rather than number theory problem... better it be a functions + AP hope u liked it . :)

It is easy to verify that $f(94) = 94^2 - 93^2 + \cdots + 22^2 - 21^2 + 20^2 - 94$ . Since $a^2 - b^2 = (a+b)(a-b)$ we have $f(94) = 94 + 93 + \cdots + 22 + 21 + 20^2 - 94 = \frac{94 \cdot 95}{2} - \frac{20 \cdot 21}{2} + 20^2 - 94 = 4561$

Note that we have:

f(n) + f(n-1) = n^2, and f(n) + f(n+1) = (n+1)^2 = n^2 + 2n + 1 there for f(n+1) = f(n-1) + 2n + 1

We know f(19) = 94 =>

f(20) = 20^2 - 94 = 306

We know that f(22) = f(20) + 43, and so on which gives us an arithmetic progression with 37 terms with 43 as the first term and 43 + 4 * 36 as last term. We there get :

f(94) = f(20) + 37 (43+(43+4 36))/2 = 306 + 4255 = 4561

4561 mod 1000 = 561 hence the answer

(if any one would like to latex my solution, you are more than welcome.) Hope that my idea is explained sufficient.