Number of spanning trees in a ladder graph

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}.$$

I don't know whether this is the simplest solution, but this is how I'd go about it:

Let $s_n$ be the number of spanning subgraphs of $L_n$ that have two connected components each containing one of the two right-most vertices; let's call such subgraphs $2$-graphs for short. Then we can write down a joint recurrence for $s_n$ and $t_n$: To each $2$-graph of $L_n$ we can add two horizontal edges to extend it to a $2$-graph of $L_{n+1}$, and we can add the three-edge figure in your last image to extend it to a spanning tree of $L_{n+1}$. To each spanning tree of $L_n$, we can add one of two horizontal edges to extend it to a $2$-graph of $L_{n+1}$, and we can add one of the three figures in your second image to extend it to a spanning tree of $L_{n+1}$. Thus we have the joint recurrence

$$\pmatrix{s_{n+1}\\t_{n+1}}=\pmatrix{1&2\\1&3}\pmatrix{s_n\\t_n}\;.$$

[Edit:]

I see you had a question in a comment about how to solve this recurrence. Brian showed how to do this by converting it into a second-order recurrence for $t$. That's analogous to converting a system of two linear first-order differential equations into one second-order equation. As for systems of linear differential equations, you can also solve the system directly by diagonalizing it. The eigenvalues of $\pmatrix{1&2\\1&3}$ coincide with the characteristic values of Brian's second-order recurrence. Using the eigensystem of the matrix, you can transform to

$$\pmatrix{s_n\\t_n}=\pmatrix{\sqrt3-1&-\sqrt3-1\\1&1}\pmatrix{u_n\\v_n}$$

with $u_n$ and $v_n$ satisfying the recurrences $u_{n+1}=(2+\sqrt3)u_n$ and $v_{n+1}=(2-\sqrt3)v_n$, respectively. The initial values are $s_1=t_1=1$, so $u_1=(2+\sqrt3)/(2\sqrt3)$ and $v_1=-(2-\sqrt3)/(2\sqrt3)$. The solutions are $u_n=(2+\sqrt3)^n/(2\sqrt3)$ and $v_n=-(2-\sqrt3)^n/(2\sqrt3)$, so

$$t_n=\frac{(2+\sqrt3)^n-(2-\sqrt3)^n}{2\sqrt3}=2^{n-1}\sum_{\scriptstyle k=0}^{\lfloor\frac{n-1}2\rfloor}\binom n{2k+1}\left(\frac34\right)^k\;.$$