Middle European Mathematical Olympiad 2010 Problem T-3

In each vertex of a regular $n$-gon there is a fortress. At the same moment each fortress shoots at one of the two nearest fortresses and hits it. The result of the shooting is the set of the hit fortresses; we do not distinguish whether a fortress was hit once or twice. Let $P(n)$ be the number of possible results of the shooting. Prove that for every positive integer $k \geq 3$, $P(k)$ and $P(k + 1)$ are relatively prime.