Generalization of the existing problem "A fly on a triangle" I encountered with special case of problem which I generalized in the following way:
Let $P_n$ be a polygon with $n$ vertexes $v_1, v_2, ..., v_n$. We denote center of $P_n$ as $O$. Let us connect each vertex with $O$. So we have $2n$ lines. Suppose that there is a fly which is, for example, in vertex $v_1$ at the moment. Also there is a spider which in $O$ and wants to eat the fly. Spider cannot move. But fly has to move always. At each vertex $v_i$ fly chooses randomly where to go. So fly has 3 options: to the left, to the right or to the spider. Therefore, each choice may emerge with equal probability equal to $\frac13.$ The question is:
What is the probability $\mathbb{S}_n$ for the fly to return to the initial vertex $v_1$? And what is the limit of $\mathbb{S}_n$ when $n \to \infty$
I have solved this for cases $n = 2, 3, 4$. But for larger $n$ my method does not work.
 A: To my great surprise, a closed form exists. First I will explain the proof and later how I found it. Note that I will be using (elementary) linear algebra. For simplicity, I will denote the vertices $v_0,\dots,v_{n-1}$, so keep that in mind.
Claim: Let $P(k,n)$ be the probability of the fly returning to $v_0$ starting from $v_k$. Then:


*

*if $n$ is even and $0\leq k\leq \frac{n}{2}$, then 
$$P(k,n)=P(n-k,n)=\frac{L_{n+1-2k}}{L_{n+1}},$$
and

*if $n$ is odd and $0\leq k<\frac{n}{2}$, then
$$P(k,n)=P(n-k,n)=\frac{F_{n+1-2k}}{F_{n+1}},$$
where $F_n$ and $L_n$ are, respectively, the Fibonacci and Lucas numbers.
Proof: Note that numbers $P(k,n)$ for $k=2,\dots,n-2$ the linear equations
$$P(k,n)=\frac{P(k-1,n)+P(k+1,n)}{3}$$
and also
$$P(1,n)=\frac{1+P(2,n)}{3}\qquad P(n-1,n)=\frac{P(n-2,n)+1}{3}.$$
Writing this system of $n-1$ linear equations in $n-1$ variables a matrix form we get
$$\left(\begin{array}{ccccc|c}
-1 & \frac{1}{3} & 0 & \cdots & 0 & \frac{1}{3} \\
\frac{1}{3} & -1 & \frac{1}{3} & \cdots & 0 & 0 \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & \dots & \frac{1}{3} & -1 & \frac{1}{3} & 0 \\
0 & \dots & 0 & \frac{1}{3} & -1 & \frac{1}{3}
\end{array}\right).$$
The block on the left is easily seen to be invertible, so this system of equations has a unique solution. Check that the numbers written in the statement of the claim satisfy the equalities (this is easy, but mildly tedious; the key formulas are $F_{n+4}=3F_{n+2}-F_n,L_{n+4}=3L_{n+2}-L_n$). $\square$
It follows that $\mathbb S_n=\frac{1}{3}P(1,n)+\frac{1}{3}P(n-1,n)$, which by the claim is either $\frac{2F_{n-1}}{3F_{n+1}}$ or $\frac{2L_{n-1}}{3L_{n+1}}$. In particular, the limit is
$$\frac{2}{3\varphi^2}=\frac{3-\sqrt{5}}{3}$$
where $\varphi$ is the golden ratio.
Now, how in the world have I came up with the numbers? The answer: I have computed them. Not by hand, of course, but with the help of SageMath, free mathematical software akin to Mathematica (you can check out the online version here).
I have written the following script which, first, builds the matrix of the system of equations described in the above proof, and then, essentially, solves it (more precisely, it reduces it to the row echelon form from which we can read of the (negatives of) the solutions in the last column).
for n in range(3,20):
M = MatrixSpace(QQ,n,n+1)
B = M([0]*(n*(n+1)))
for i in range(n):
    B[i,i] = -1
    B[i,i-1] = 1/3
    B[i,i+1] = 1/3
-B.echelon_form()

How did I then figure out that we are dealing with Fibonacci and Lucas? I have recognized Fibonacci numbers almost immediately (the slight issue is that the fractions are written in the reduced form in the output, so e.g as 1/17 instead of 2/34), and then quickly I have realized the other solutions are another recurrence sequence, which I found was the Lucas sequence. So, essentially, I was staring at the numbers until I saw the pattern.
