IMO 1988 LL IRE50

Let g(n) be defined as follows:

IMO 1988 LL IRE50

Origin: IRE

Problem

Let g(n) be defined as follows: g(1) = 0, g(2) = 1, g(n + 2) = g(n) + g(n + 1) + 1 (n \geq1). Prove that if n > 5 is a prime, then n divides g(n)(g(n) + 1).