51st Ukrainian National Mathematical Olympiad, 3rd Round

Question

Sequence (a_n) is defined as follows: a_1 = 1, a_2 = 2, a_n+2 = (n+1)(a_n + a_n+1) for each natural n. How many zeros does a_2011 end with?

Accepted Answer

We first prove that a_n = n! by PMI: a_n+2 = (n+1)(n! + (n+1)!) = n!(n+1)(n+2) = (n+2)! One can now find the number of zeros using the well-known formula: [ 20115 ] + [ 20115^2 ] + [ 20115^3 ] + = 402 + 80 + 16 + 3 = 501.