Discrete math Please write your answer neatly so that I can

Discrete math. Please write your answer neatly so that I can read it.

T(n) is the number of spanning trees for the n-ladder. Show that T(n) = 4. T(n - 1) - T(n - 2).

Solution

solution -:

You can verify that there are 6+9=15 spanning trees of the 3-ladder graph.

To see this, note that you must remove 2 edges.

For part b, which techniques have you seen for solving recurrence relations?

You can find the characteristic polynomial to find the general solution. In this case we get r24r+1=0, so r=4±sqrt12/2=2±sqrt3–. Then, T(n)=c1(2+sqrt3)^n+c2(2sqrt3)^n. Solve for the constants using the initial values T(1)=1 and T(2)=4.

T(n)=4T(n1)T(n2)

T(1)=4*T(0)-T(-1)