Find a recurrence relation for $h_n$. Let $h_n$ denote the number of spanning trees in the fan graph shown below. Let $h_n$ denote the number of spanning trees in the fan graph shown below. Find a recurrence relation for $h_n$.

I know it's got something to do with $h_n=F_{2n-1}$. But how else to find a recurrence relation?
 A: Assume $n \geq 2$ and considering the addition of node $x_n$ to an existing fan graph. In any new spanning tree, the new node $x_n$ can either be a leaf or non-leaf.
If $x_n$ is a leaf then it can attach to any existing spanning tree via edge $x_nx_0$ or $x_nx_{n-1}$. This provides $2h_{n-1}$ spanning trees.
If, instead, $x_n$ is a non-leaf, the new spanning tree must have both edges $x_nx_0$ and $x_nx_{n-1}$ and these edges join two otherwise-disconnected trees that between them contain all the other nodes. One tree, $A$ say, has $x_0$ and the other, $B$, has $x_{n-1}$. Trees $A$ and $B$ can have $i$ and $n-i$ nodes respectively, for all $i=1,\ldots,n-1$.
For each such $i$, tree $A$ is the spanning tree of a fan graph so it can occur in $h_{i-1}$ ways. Tree $B$ can occur in exactly one way, namely the path $x_{n-1}x_{n-2} \cdots x_{i}$. Thus, the number of spanning trees with $x_n$ as a non-leaf is $\sum_{i=0}^{n-2}{h_i}$.
Summing these two results, we have, for $n \geq 2$,
$$h_n = h_{n-1} + \sum_{i=0}^{n-1}{h_i}.$$
Initial values are: $h_0 = 1,\; h_1 = 1$.
Now to take that result to a Fibonacci sequence:
I make out that for $n \geq 1, h_n = F_{2n}$ rather than $F_{2n-1}$ but perhaps that's just a difference in our indexing. I have
$$
\begin{array}{c|ccc}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
\hline
F_n & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 \\
h_n & 1 & 1 & 3 & 8 & 21
\end{array}
$$
That $h_n=F_{2n}$ for $n\geq 1$ can be proved by induction:
Initial case: $h_1 = 1 = F_2.\;\; \checkmark$
Now assume the claim is true for all $1\leq n \leq k$ for some $k\geq 1$. Then for $k+1$:
\begin{eqnarray*}
h_{k+1} &=& h_k + \sum_{i=0}^{k}{h_i} \\
&=& F_{2k} + h_0 + \sum_{i=1}^{k}{F_{2i}} \qquad\text{by inductive assumption} \\
&=& F_{2k} + h_0 + (F_3-F_1) + (F_5-F_3) + (F_7-F_5) + \cdots + (F_{2k+1}-F_{2k-1}) \\
&=& F_{2k} + h_0 + F_{2k+1} - F_1 \\
&=& F_{2k} + F_{2k+1} \\
&=& F_{2k+2}.
\end{eqnarray*}
This proves the case for $n=k+1$ and the proof is complete.
