T(n) is the number of spanning trees for a n-ladder.
Show that $ T(n)=4×T(n−1)−T(n−2) $
As a proof, I don't really know how to solve this. Any assistance would be appreciated.
I tried to first solve for a 3 case, and drew out the ladder as such:
as $ T_n+1=3*T_n $, but I kinda dont know where to go from here.
Good start. The fourth way is to add on three blue lines shown in my diagram:
Obviously this creates a cycle, so delete the edge that I have crossed through with two blue lines.
This method can only be used if in fact the top edge is already part of a spanning tree. The number of spanning trees that include this edge is $T(n-1)-T(n-2)$.