In each vertex of a regular
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
-gon, there is a fortress. At the same moment, each fortress shoots 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)](/media/m/f/6/8/f680d9bbded52866a9815281ae83c905.png)
be the number of possible results of the shooting. Prove that for every positive integer
![k\geqslant 3](/media/m/6/1/c/61c0127006c797eb3a3821dad3fd7a19.png)
,
![P(k)](/media/m/7/a/7/7a7612f7e4c71ae8a2124110866cfbd2.png)
and
![P(k+1)](/media/m/e/0/5/e05ac30c4192b0efb78f9cfa2f7949f2.png)
are relatively prime.
%V0
In each vertex of a regular $n$-gon, there is a fortress. At the same moment, each fortress shoots 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\geqslant 3$, $P(k)$ and $P(k+1)$ are relatively prime.