We add a center $O$ to a regular hexagon and 6 rays, connecting the point O with the vertices of the hexagon. How many closed routes are there in the obtained graph of length n leading from $O$ to $O$ (edges on a route can repeat)? Arrange the appropriate recursive equation and solve it.
Let $S_n$ denote the number of closed routes closed from $O$ to $O$ of lengths $n$. I check one by one the value of $S_n$ for several initial values of n:
- $S_0 = 1$
- $S_1 = 0$
- $S_2 = 6$. It is 6 because we have six two-step routes (as many as rays: after the first step we are in a vertex and in the second step we have to return to the center)
- $S_3 = 6 \cdot 2=12$ In the first step we have $6$ possibilities and after this step we are in any of the vertices of the hexagon and the next step can be made to the right or left on the 2 possibilities, and in the next step we no longer have a choice - we have to return to the center, so there are $6 \cdot 2$ possibilities.
- $S_4 = 6 \cdot s_2 + 6 \cdot 2 \cdot 2 =60$ We can take the first step again in six ways after which we are at any of the vertices and now if in the second step we go back to the center we return to the $S_2$ possibilities which means it will already be $6 \cdot S_2$, and if in the second step we go right or left then we have two possibilities after which we are again in one of the vertices and now we can not go to the center, we have to go right or left again - that is two possibilities. So $S_4 = 6 \cdot S_2 + 6 \cdot 2 \cdot 2 = 60$.
- $S_5 = 6 \cdot S_3 + 6 \cdot 2 \cdot S_3 + 6 \cdot 2 \cdot 2 \cdot S_2 + 6 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 192$ Again, in the first step we have 6 possibilities and if in the second we go back to the middle then we get $S_3$, and if in the second step we go right or left (that is two possibilities) and then return to the center then we get $S_2$, and if in the third step we again go to the right or left (again two possibilities) and in the fourth step we no longer have a choice.
- $S_6 = 6 \cdot S_4 + 6 \cdot 2 \cdot S_3 + 6 \cdot 2 \cdot 2 \cdot S_2 + 6 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 744$ Again in the first step we have 6 possibilities and if in the second we return then we get $S_4$, and if in the second one to the right or left (2 possibilities) then if in the third one we go back we get $S_3$, and if in the third to the right or left (2 possibilities) and in the fourth we return then we get $S2$ and if in the fourth to the left or right (2 possibilities) then in the fifth we must go left or right (2 possibilities) and in the sixth we return.
Thus, it can be seen that $S_n = 6S_n - 2 + 6 \cdot 2 S_n - 3 + 6 \cdot 2 \cdot 2 \cdot S_n - 4 + (...) + 6 \cdot 2_n - 2$, but given that $S_1 = 0$,$S_0 = 1$ we can write that $S_n = 6S_{n-2} + 2 \cdot 6S_{n-3} + 2 \cdot 2 \cdot 6S_{n-4} + (...) + 2^{n-3} \cdot 6S_1 + 2^{n-2} \cdot 6S_0$. Thus, we see that the sequence will be defined recursively by $S_n = 6S_{n- 2} + 2 \cdot S_{n-1}$. That is, we predict $S_n = q^n$ and insert into the equation obtaining: $q^n - 2q^{n-1} - 6q^{n-2} = 0$ i.e. $q^2 - 2q - 6 = 0$. The solutions are $q_1 = -1 - \sqrt{7} $ and $q_2 = -1 + \sqrt{7}$. Solution $S_n$ we predict in the form $S_n = cq^n_1 + dq^n_2$. Substituting the initial conditions, we get that $S_n = \frac{7 - \sqrt{7}}{14}(-1 - \sqrt{7})^n + \frac{7 + \sqrt{7}}{14} (-1 + \sqrt{7})^n$
Is that a correct solution?
That is the recursion, but your derivation of it is neither clear or convincing. I suggest instead that you consider what happens if you have a closed path of length $n$ and remove the last two edges. Backing up the first edge leaves you out at one of the vertices. Backing up the second edge will either take you to another vertex, or else back to the center $O$.
Adding these together gives $S_n = 2S_{n-1} + 6S_{n-2}$.
If $q = -1 - \sqrt 7$, then $q^2 = 8 + 2\sqrt 7$, while $2q + 6 = 4 - 2\sqrt 7$, so this is not a root of $q^2 = 2q + 6$, and neither is the other. This is due to a simple sign error.