I don't understand this at all I have the solution but no idea. I am suppose to find the recursion relation for consecutive 0 in a ternary string(String that contains only 0, 1 and 2) So the solution I have is : Strings starting with 1 = an(The n is the small n for recursion) - 1 Strings startring with 2 = an - 1 Strings starting with 01 = an - 2 Strings starting with 02 = an - 2 Strings starting with 00 = 3^n-2 So the relation is an = 2an-1 + 2an - 2 + 3^n-2 for n >= 3 So how did they get the relation? Why an - 1? What is the length of the String they base their calculations on? Example : I take Strings starting with 1, I can have 10, 11, 12, why an - 1? and not an - 3, all 3 do not have consecutive 0s? Or if I take the length of the String as 3, I can have 100, 110, 101, 102, 111.... so why -1? When I have so many other strings to minus off? And also for 00, Where did the 3^n come from? This is so mind confusing.