How to derive recursive formula in combinatoric problems? I know that certain combinatorics problems (I will provide example at the end of the post) can be solved by figuring out recursive formula. However I seem to fail everytime I try to do that. Could anybody of you show me how is it done generally?
Example:
How many sequences of length n, consisting of 1 and 0, which don´t contain string "000" are there?
Formula: f(n+1)=f(n)+f(n-1)+f(n-2)
How was it derived?
 A: You can do this by cases. For the rest of this post I will call a string "000" a triplet. Such sequences $S$ of length $(n+1)$ split into 3 categories:


*

*The last term of $S$ is a 1. Then the only restriction you have is that there must be no triplet in the first $n$ digits, because you cannot create a triplet with the last digit. So there are as many sequences of this kind as there are sequences of length $n$ with no triplets: $f(n)$.

*The last terms of $S$ are 10. Then with the same line of reasoning, you have no restriction on the other $(n-1)$ terms, so there are $f(n-1)$ such sequences.

*The last terms of $S$ are 00.
Then you must end with 100, or you would have a triplet. Now the same reasoning as before applies: you can choose the other $(n-2)$ digits in $f(n-2)$ ways.


Putting this all together gives you the result.
This kind of method generally works when you just have a sum: look at how many terms you have, and try to divide in as many cases, then make every case equivalent to one of a previous step in the recursion.
A: One way to do it is to build a generating function for it by looking at a regular expression.
A regular expression for strings that don't contain $000$ is
$$ \{1,01,001\}^*\{\varepsilon,0,00\}. $$
This says that every string without $000$ can be obtained by taking $1, 01, 001$ and repeating them some number of times (the Kleene star means repeat 0 or more times) followed by adding the empty string ($\varepsilon$) or $0$ or $00$ to the end. For instance $011110010101$ is $01$ then $1$ three times then $001$ then $01$ twice with the empty string on the end.
The generating function for $\{1,01,001\}$ is $x + x^2 + x^3$ (the coefficient of $x^k$ tells you how many strings there are of length $k$; e.g. $4x^3$ means $4$ strings of length $3$). The generating function for $\{\varepsilon,0,00\}$ is $1 + x + x^2$. If $A(x)$ is the generating function for a set $S$ then $\frac{1}{1 - A(x)}$ is the generating function for $S^* = \{\text{elements of $S$ repeated 0 or more times}\}$ (the Kleene star of $S$).
Thus the generating function for $\{1,01,001\}^*\{\varepsilon,0,00\}$ is
$$ \frac{1}{1 - (x + x^2 + x^3)} \cdot (1 + x + x^2) = \frac{1 + x + x^2}{1 - x - x^2 - x^3}. $$
The correspondence between recurrence relations and rational generating functions (see e.g. Stanley EC1, Theorem 4.1.1) says that:

A rational generating function with denominator $1 + a_1x + a_2x^2 + \dots + a_d x^d$ gives a recurrence relation
  $$f(n + d) + a_1f(n + d - 1) + a_2f(n + d - 2) + \dots + a_d f(n) = 0.$$

Thus we get the recurrence relation
$$ f(n + 3) - f(n + 2) - f(n + 1) - f(n) = 0 $$
Since $d = 3$ and $a_1 = a_2 = a_3 = -1$. This is of course equivalent to what you have.
