Find $d_n$ which is number of all spanning tree of $G_n$ where $V = \left\{ 0,1,...,n \right\} $ and $$E = \left\{ \left\{ 0,i \right\} : i \in [n] \right\} \cup \left\{ \left\{ i,i+1 \right\} : i \in [n-1] \right\} $$
This is our graph
And I found that
$$ d_n = 2d_{n-1} \text{ for } n \ge 4$$
$d_1 = 1$
$d_2 = 1$
$d_3 = 3$
But the pattern looks too simple, can somebody verify that?
I think you messed up the indices. $d_0=1, d_1=1, d_2=3$. Looking for a recursion is a good idea (probably the right approach). But again, you made a small mistake.
Case 1: the edge $(0,n+1)$ is in the tree but $(n,n+1)$ is not. Then there are $d_n$ solutions.
Case 2: the edge $(0,n+1)$ is not in the tree but $(n,n+1)$ is there. Then there are $d_n$ solutions.
Cse 3: both edges containing $(n+1)$ is in the tree. I claim that there are $d_0+d_1+\cdots +d_{n-1}$ solutions in this case. (Think about it.)
So the recursive rule is $d_{n+1}=d_0+\cdots +d_{n-1}+2d_n$. (This also works for $n=2$.)
Seems to me that this gives $d_n= F_{2n}$ for $n\geq 1$.