Find explicit expression of $P_n$ for a given 'graph' Given this image:   



For each positive integer $n$ we will define $P_n$ the number of series of length $n$ from the group $\{a,b,c,d,e\}$ so that the first element is $a$ and $2$ consecutive elements are connected by a line (In the image above).  

For example: $a-e-d-a-c-a-b-e$ is a legal series of length $8$  

Question: Find an explicit form of $P_n$  

I tried to think about it, if the first element is $a$ so for the second element we have $4$ options, then we have to choose whether to go back to $a$ or go to the other $3$ options we have.  

But I don't think I get it, it has many forms... maybe I alternate between $a$ and $d$ - $n$ times? or maybe go from $a-d-e-a-d-e-a$ etc.. ?  

Thank you very much for helping!
The solution below is not related to graph theory, but given the ugly-ish results, it might be the easier one.
Let $A_n$ be the number of path starting and ending at $a$, and $B_n$ be the number of path starting at $a$ but ending at another vertex. So that
$$ P_n=A_n+B_n$$
We have the following recursive equations :
$$\left\{\begin{align}
A_{n+1}&amp;=B_n\\
B_{n+1} &amp;= 4 A_n+2 B_{n}
\end{align}\right.$$
Leading to
$$ B_{n+1} = 2 B_n + 4 B_{n-1}$$
Therefore $B_n$ is of the form
$$ B_n = \lambda r_1^{n-1} + \mu r_2^{n-1}$$
Where $r_1$ and $r_2$ are the solution to $X^2-2X-4=0$, and $\lambda$ and $\mu$ might be found using $B_1=0$ and $B_2=4$.
Finally (I skiped the full calculation, you should be able to do them by yourself), using $P_n=A_n+B_n$ we end up with (note that the expression might be reducible),

$P_1=1$ and for any $n\geq 2$
$$ P_n=\frac{2}{\sqrt{5}}(1+\sqrt 5)^{n-2}(2+\sqrt 5)-\frac{2}{\sqrt{5}}(1-\sqrt 5)^{n-2}(2-\sqrt 5)$$

Yielding the values $(4,12,40,128,416,...)$
Edit The reduced version would be

$P_1=1$ and for any $n\geq 2$
$$ P_n=\frac{-(1-\sqrt 5)^{n+1} + (1 + \sqrt 5)^{n+1}}{4 \sqrt 5}$$

As noted by @bof, we can refer to the Fibonacci sequence, with $\phi = \frac{1+\sqrt{5}}{2}$ and $\psi = \frac{1-\sqrt{5}}{2}$,
$$P_n=2^{n+1} \frac{\phi^{n+1} - \psi^{n+1}}{4 \sqrt 5} = 2^{n-1}F_{n+1}$$
Edit : Complement on order-$2$ homogeneous linear recurrence with constant coefficients
Let a and b be two constant, and the linear recurrence
$$u_{n + 2} = au_{n+1} + bu_n\quad(R)$$
The polynomial $X^2-aX-b$ is called the characteristic polynomial of the recurrence. It can be shown that $u_n$ verifies
$$u_n = \lambda r_1^{n} + \mu r_2^{n} \quad (*)$$
Where $r_1$ and $r_2$ are the roots of the characteristic polynomial (this works also for higher orders). Indeed if you plug $(*)$ into $(R)$ you get
\begin{align}
u_{n + 2} - au_{n+1} - bu_n &amp;=(\lambda r_1^{n+2} + \mu r_2^{n+2}) - a(\lambda r_1^{n+1} + \mu r_2^{n+1})-b(\lambda r_1^{n} + \mu r_2^{n}) \\
&amp;= \lambda r_1^n (\underbrace{r_1^2-ar_1-b}_{=0}) + \mu r_2^n (\underbrace{r_2^2-ar_2-b}_{=0})\\
&amp;=0
\end{align}
Where the $=0$ statements are directly because $r_1$ and $r_2$ are the roots of the characteristic polynomial.
The Adjacency matrix of this graph is $A$=\begin{bmatrix} 0, 1, 1, 1, 1\\1, 0, 1, 0, 1\\1, 1, 0, 1, 0\\1, 0, 1, 0, 1\\1, 1, 0, 1, 0 \end{bmatrix} and what you need is just the sum of the first row of $n$-th power of $A$. By defining $v=[1,1,1,1,1]^{T}$ and $e_1=[1,0,0,0,0]^T$, we have $Av=3v+e_1$ and $Ae_1=v-e_1$. Then $A^2v=3(3v+e_1)+(v-e_1)=10v+2e_1$, $A^3v=10(3v+e_1)+2(v-e_1)=32v+8e_1$, $A^4v=32(3v+e_1)+8(v-e_1)=104v+24e_1$, etc. Now $P_n$ is exactly $e_1^TA^nv$, and we get the sequence (4,12,40,128,...).