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

Question

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?

Answer 1

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.