Solution:

Let us denote each hit fortress by a black dot and each undamaged one with a white dot. Then $P(n)$ is the number of colourings of $n$ dots distributed on the circle with black and white colours in such a way, that no two white dots have exactly one dot in between them. The proof of this bijectivity is straightforward: If there are two white dots with exactly one dot in between, then obviously the fortress in between can not shoot, which is not permitted. On the other hand, if there are no such two white dots, then each fortress can shoot at least one black dot and to ensure that every black dot will be hit, we can force the one in the clockwise direction to shoot at it.

If $n$ is odd, then $P(n)$ is equal to the number $K(n)$ of colourings of $n$ dots on a circle with black and white colours in such a way, that no two neighbouring dots have white colour (we define the neighbouring dots to be the dots which have exactly one other dot in between them). For $n$ even, with the same definition of neighbours, the circle splits into two circles with $n / 2$ dots, and we have $P(n)=K(n / 2)^2$.

For $K(n)$ it is easy to derive a recurrence formula $K(n)=K(n-1)+K(n-2)$. In fact, the number of legal colourings with $n$-th dot being black is equal to the number of legal colourings of $n-1$ dots (just put the black dot in between the first dot and the $(n-1)$-th dot) plus the number of colourings of $n-1$ dots with no two neighbouring white dots except for the first and $(n-1)$-th (we can put the black dot in between two white dots to obtain legal colouring). The latter case gives the same number as the number of legal colouring with $n-2$ dots having the first dot white (just span two white dots into one white). On the other hand, the number of legal colourings with $n$-th dot being white is equal to the number of colourings of $n-1$ dots with no two neighbouring white dots and with the first and $(n-1)$-th dot black (we can put the white dot only in between two black dots), which is equal to the number of legal colouring with $n-2$ dots having the first dot black (again, span two black dots into one black). Together, we have
$$K(n)=K(n-1)+K_{w}(n-2)+K_{b}(n-2)=K(n-1)+K(n-2),$$
where $K_{w}$ and $K_{b}$ stands for the number of legal colourings with first dot white and black respectively.

Moreover we can directly count $K(2)=3, K(3)=4, K(4)=7$, which suggests
$$K(2)=F(4)-F(0), \quad K(3)=F(5)-F(1), \quad K(4)=F(6)-F(2)$$
and we can easily prove by the induction $K(n)=F(n+2)-F(n-2)$, where $F(k)$ stands for the $k$-th term of the Fibonacci sequence $(F(0)=0, F(1)=F(2)=1, \ldots)$. Further $(K(2), K(3))=1$, and for $n \geq 3$ we have
$$(K(n), K(n-1))=(K(n)-K(n-1), K(n-1))=(K(n-2), K(n-1))=\cdots=1$$
Similarly we show that for each even $n=2 a$ the number $P(n)=K(a)^2$ is relatively prime both to $P(n+1)=K(2 a+1)$ and $P(n-1)=K(2 a-1)$ :
$$\begin{aligned} (K(a), K(2 a+1)) & =(K(a), F(2) K(2 a)+F(1) K(2 a-1))= \\ & =(K(a), F(3) K(2 a-1)+F(2) K(2 a-2))=\ldots \\ & \cdots=(K(a), F(a+1) K(a+1)+F(a) K(a))=(K(a), F(a+1))= \\ & =(F(a+2)-F(a-2), F(a+1))= \\ & =(F(a+2)-F(a+1)-F(a-2), F(a+1))= \\ & =(F(a)-F(a-2), F(a+1))=(F(a-1), F(a+1))= \\ & =(F(a-1), F(a))=1 \\ (K(a), K(2 a-1)) & =(K(a), F(2) K(2 a-2)+F(1) K(2 a-3))= \\ & =(K(a), F(3) K(2 a-3)+F(2) K(2 a-4))=\ldots \\ & \cdots=(K(a), F(a) K(a)+F(a-1) K(a-1))=(K(a), F(a-1))= \\ & =(F(a+2)-F(a-2), F(a-1))=(F(a+2)-F(a), F(a-1))= \\ & =(F(a+2)-F(a+1), F(a-1))=(F(a), F(a-1))=1, \end{aligned}$$
which finishes the proof.