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!
 A: 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}&=B_n\\
B_{n+1} &= 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 &=(\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}) \\
&= \lambda r_1^n (\underbrace{r_1^2-ar_1-b}_{=0}) + \mu r_2^n (\underbrace{r_2^2-ar_2-b}_{=0})\\
&=0
\end{align}
Where the $=0$ statements are directly because $r_1$ and $r_2$ are the roots of the characteristic polynomial.
A: $P_n$ is the number of words of length $n$ over the alphabet $\{a,b,c,d,e\}$ subject to the conditions: no consecutive occurrences of the same letter; the letters $b,d$ may not occur consecutively; the letters $c,e$  may not occur consecutively; and the first letter must be an $a$. As in Paul Hudford's answer, let $P_n=A_n+B_n$, where $A_n$ is the number of words ending in $a$ and $B_n$ is the number of words ending in some other letter.
We will find an expression for $B_n$ by a direct combinatorial argument. Let's consider the pattern of $a$'s in a word of length $n\ge3$ which does not end in $a$. So the first letter is $a$, the second letter and the last letter are not $a$, and in between we have a word of length $n-3$ where the only restriction on the placement of $a$'s is that they may not occur consecutively. Now, the number of bitstrings of length $m$ with no consecutive $1$'s is the Fibonacci number $F_{m+2}$. Therefore, there are $F_{n-1}$ ways to distribute the $a$'s in our word. Now, for each slot not occupied by an $a$, there are $4$ ways to fill it if the preceding slot has an $a$, and $2$ ways otherwise (working from left to right); and the last slot does not have an $a$. Therefore, regardless of the number of $a$'s, there are $2^n$ ways to fill in the non-$a$ slots, and so $B_n=2^nF_{n-1}$ for $n\ge3$. For some mysterious reason that identity also holds for $n=1,2$, and so we have $B_n=2^nF_{n-1}$ for all $n\ge1$.
It follows that, for all $n\ge2$, we have $A_n=B_{n-1}=2^{n-1}F_{n-2}$, and finally
$$P_n=A_n+B_n=2^{n-1}F_{n-2}+2^nF_{n-1}=2^{n-1}(2F_{n-1}+F_{n-2})=2^{n-1}(F_{n-1}+F_n)=2^{n-1}F_{n+1}.$$
We only proved it for $n\ge2$, but for some mysterious reason our final answer also holds for $n=1$:
$$\boxed{P_n=2^{n-1}F_{n+1}}$$
A: 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,...).
