II_Question13_Prob

Keen to know if this works or not.

Writting down the recurrence relations:

A(n+1) = (1/2)A(n) + (1/4)B(n) + (1/4)D(n)
B(n+1) = (1/4)A(n) + (1/2)B(n) + (1/4)C(n)
C(n+1) = (1/4)B(n) + (1/2)C(n) + (1/4)D(n)
D(n+1) = (1/4)A(n) + (1/4)C(n) + (1/2)D(n)

Notice that A(0) = 1, B(0) = C(0) = D(0) = 0.

Then B(n+1) + D(n+1) = 1/2 and therefore B(n) = D(n) = 1/4 by symmetry with the starting condition

and then C(n) = (1/4)(B(n)+D(n)) + (1/2) C(n) = (1/8) + (1/2)C(n-1)

which is a nice simple recurrence relation with solution C(n) = (1/2^(n+2))(2^n - 1)

1 Like