Making reccurence relation

Question

I have trouble in understanding how to make recurrence relations. I read some of the questions on stack exchange but this stuff is not intuitive to me. For example, when we want to find a number of ternary string that don't contain 00 sequence the solution is a $a_n=2b_{n-1}+2b_{n-2}$. To not have two consecutive zeros our last number should be 1 or 2 and our two last numbers should be any number except the one that ends in 0. Somehow we arrive at the recurrence relation mentioned earlier. Thank you!

Answer 1

Assuming that we know $b_{n-1}$ and $b_{n-2}$, consider a ternary string of length $n$. Counting the ternary strings of length $n$ satisfying the conditions, we consider two cases.

1) the last number is a zero. Since we cannot have consecutive zeroes, the $n-1$th number must be either 1 or 2. So we have $2b_{n-2}$ string ending in 10 or 20, since there are no troubles with consecutive zeroes when we add these numbers to a sequence of length $n-2$

2) The last number is either 1 or 2. Again, we can just take any ternary string of length $n-1$ which satisfy the conditions and add 1 or 2 at the end, since there are no zeroes which cause troubles. So there are $2b_{n-1}$ choices in this case.

It easily follows that $b_n=2b_{n-1}+2b_{n-2}$.

My general advice for proving reccurence relations is to consider all possible cases very carefully and/or rephrasing the problem into smaller problems (divide-and-conquer). You should always try lots of small examples to see what's happening. Once one spots the pattern, it is often easier to generalize.