I'm working my way through basic combinatorics questions with recurrence relation, and can't quite get my head about the right way of solving them.
For example, I have two following examples in my Uni text-book:
1) Strings formed from 0,1,2 characters, needed to calculate amount of possible strings without combinations 00 and 01.
The solution is: $$f(n)=2f(n-1) + f(n-2)$$ i.e. taking only allowed characters
2) Strings formed from A,B,C characters, needed to calculate amount of possible strings without AB combination.
The solution is: $$f(n)=3f(n-1) - f(n-2) $$i.e. taking all characters and subtracting the forbidden ones.
The idea is very clear, but what I can't understand is why in first solution only valid cases are taken, and in second case all cases taken then one invalid is subtracted.
It seems that I can solve it in reverse, i.e.:
1) $f(n)=3f(n-1) - 2f(n-1)$ //i.e. 0,1,2 minus 00 and 01 case
2) $f(n)=2f(n-1)+2f(n-2)$ //i.e. B,C + AA,AC case
But when translated to difference equations, the results are different.
Anything I'm missing here?