Let the vertices along the top of $L_{n+1}$ be $u_1,\dots,u_{n+1}$ and those along the bottom be $v_1,\dots,v_{n+1}$. There’s a bijection between spanning trees of $L_{n+1}$ that contain the edges $\{u_n,u_{n+1}\}$, $\{u_{n+1},v_{n+1}\}$, and $\{v_n,v_{n+1}\}$ and spanning trees of $L_n$ that contain the edge $\{u_n,v_n\}$. Let $s_n$ be the number of spanning trees of $L_n$ that include $\{u_n,v_n\}$. Then $t_{n+1} = 3t_n + s_n$, and $s_{n+1} =$ ?
Added: I now see how to get a recurrence for the $t_n$ directly, without using an auxiliary sequence. Start with any spanning tree of $L_n$. As you said, you can always add one of the three figures in your second picture to it to get a spanning tree of $L_{n+1}$, and that accounts for $3t_n$ spanning trees. You can add your last picture to it if and only if it contains $\{u_n,v_n\}$, in which case you must erase $\{u_n,v_n\}$; that accounts for another $t_n-k$ spanning trees, where $k$ is the number of spanning trees of $L_n$ that don’t contain $\{u_n,v_n\}$. So when does a spanning tree $T$ of $L_n$ not contain $\{u_n,v_n\}$? Exactly when $T$ does contain both $\{u_{n-1},u_n\}$ and $\{v_{n-1},v_n\}$, which is exactly when the part of $T$ in $L_{n-1}$ is a spanning tree of $L_{n-1}$. In other words, there are $t_{n-1}$ spanning trees of $L_n$ that include the edge $\{u_n,v_n\}$: $k=t_{n-1}$, and $L_{n+1}$ has $t_n-t_{n-1}$ spanning trees that include your last picture. This makes a grand total of $$t_{n+1}=3t_n+(t_n-t_{n-1})=4t_n-t_{n-1}$$ spanning trees of $L_{n+1}$.
But I found the analysis much easier with the auxiliary sequence. As long as your recurrences are linear, it’s not too hard to combine them by very elementary means. For instance, suppose that you have this system:
$$\begin{cases}
t_{n+1}=at_n+bs_n\tag{1}\\
s_{n+1}=ct_n+ds_n
\end{cases}$$
Then
$$\begin{cases}
dt_{n+1}=adt_n+bds_n\\
bs_{n+1}=bct_n+bds_n,
\end{cases}$$
so $dt_{n+1}-bs_{n+1}=(ad-bc)t_n$. As long as $ad-bc\ne 0$, you can solve this for $s_{n+1}$ to get $$s_{n+1}=\frac{d}{b}t_{n+1}-\frac{ad-bc}{b}t_n,$$ or, equivalently, $$s_n=\frac{d}{b}t_n-\frac{ad-bc}{b}t_{n-1}.$$ Substitute this into the first equation of $(1)$ to get $$t_{n+1}=(a+d)t_n+(ad-bc)t_{n-1}.$$
You strategy for the first tree is a good one. As soon as you omit an edge from the center cycle, you are left with a tree. There are four possible edges you could omit.
For the second tree, you might consider two cases: vertex $E$ either has degree one or degree two.
If $E$ has degree one, we must choose one of its two incident edges to include in our spanning tree $T$. Since $E$ is going to be a leaf in our tree, the subgraph of $T$ obtained by deleting $E$ from $T$ must also be a tree. In the original graph, the vertices $A$, $B$, $C$, and $D$ are a complete graph on four vertices. You may know a famous theorem of Cayley: the number of labeled spanning trees on $n$ vertices is $n^{n-2}$. Hence, there are $4^{4-2} = 16$ spanning trees on these four vertices. All told, that gives us $2 \cdot 16 = 32$ labeled spanning trees with vertex $E$ as a leaf.
If $E$ has degree two, then there only remain two edges to form the tree. We cannot use the edge $BC$ (this would form a cycle). Since there are only $\binom{5}{2} = 10$ ways to choose the edges, I think I would be inclined to just power through all ten possibilities. You will find that six of them result in a tree in which vertex $E$ has degree two.
Adding everything up, there are $32 + 6 = 38$ spanning trees in the second graph.
Best Answer
So we have to count all the ways to delete two edges such that remaining graph is connected. If we remove $a_{k + 1} b_{k + 1}$, then we can also remove any other edge. This gives us $2n$ spanning trees.
So now assume that we do not remove $a_{k + 1} b_{k + 1}$. Instead we have to remove two other edges. Notice that if we remove one edge to the left of $a_{k + 1}b_{k + 1}$ and one edge to the right, our graph will still be connected. Otherwise it will be disconnected. This gives us $n \cdot n$ spanning trees.
In total we have $2n + n^2$.