A recurrence to relate to

Rewrite the recurrence as $a_{n+2} - a_{n+1} = (n + 2)(a_{n+1} - a_{n}).$

The letting $b_{n} = a_{n} - a_{n-1}$ with $b_{1} = 1$ we have

$b_{n+2} = (n + 2)b_{n+1}$ for $n \ge 0.$ Then

$b_{2} = 2, b_{3} = 3*2 = 6, b_{4} = 4*3*2 = 24,$ and in general $b_{n} = n!.$

Then $a_{n} = b_{n} + a_{n-1} = b_{n} + b_{n-1} + a_{n-2} = .... = \displaystyle\sum_{m=1}^{n} m!.$

Now for $n \ge 10$ we have that the last two digits of $n!$ are $00.$ So for $10 \le k \le 2015$ we have that

$a_{k} \equiv (1! + 2! + 3! + 4! + 5! + 6! + 7! + 8! + 9!) \pmod{100} \equiv$

$(1 + 2 + 6 + 24 + 20 + 20 + 40 + 20 + 80) \pmod{100} = 13.$

So $\displaystyle\left(\sum_{k=10}^{2015} a_{k}\right) \pmod{100} \equiv (2006*13) \pmod{100} = 78.$

Next, $\displaystyle\left(\sum_{k=1}^{9} a_{k}\right) \pmod{100} \equiv$

$(9*1 + 8*2 + 7*6 + 6*24 + 5*20 + 4*20 + 3*40 + 2*20 + 1*80) \pmod{100} \equiv$

$(9 + 16 + 42 + 44 + 0 + 80 + 20 + 40 + 80) \pmod{100} = 31.$

Thus the desired answer is $78 + 31 = \boxed{9}.$

Python 2.7:

1
2
3
4
5
6
7

memo = {1:1, 2:3}
def f(n):
    if n in memo:
        return memo[n]
    memo[n] = (n+1)*f(n-1)-(n)*f(n-2)
    return memo[n]
print "Answer:", sum([f(n) for n in xrange(1,2016)]) % 100

By using direct calculations we can obtain that $a_{9} \equiv a_{10}\equiv 13 \pmod {100}$ . Then using mathematical induction we can prove that $a_{n}\equiv 13 \pmod {100}$ for all $n \geq 9$ . Indeed, it would be enough to prove that if $a_{k}\equiv a_{k+1}\equiv 13$ for $k \geq 9$ , then $a_{k+2} \equiv 13$ . This can be done by the recurrence relation: $a_{k+2}= (k+3)* a_{k+1}-(k+2)* a_{k} \equiv$ $\equiv (k+3) *13-(k+2)*13 \equiv 13 \pmod{100}$ In the other hand we can also get by direct calculations that $\sum_{k=1}^{8} a_{k}\equiv 18 \pmod {100}$ . Therefore $\sum_{k=1}^{2015} a_{k}\equiv 18 +(2015-8)*13\equiv 09 \pmod{100}.$