ISL 1988 Problem 45

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