Amount of binary strings i `ve got this problem, can you help me ?
I can solve subquestion a) but i really don`t have a clue how to find recursive formula.
S_n is the amount of binary strings with size n, which don’t include substring 010.


*

*Find some of S_n for small values of n. 

*Find recursive formula for S_n.

 A: $S(n) = 2S(n-1) - S(n-2) + S(n-3)$ 
(Start on a large whiteboard)
Draw a binary tree with the possible cases. Left for 0 right for 1. Three or Four levels are enough to get an idea. 
The right subtree is  $S(n-1)$ 
The left subtree is  $S(n-1)-S(n-2)+S(n-3)$
BTW some values for S(n) are:
$S(3) = 7$$S(4) = 12$$S(5) = 21$$S(6) = 37$$S(7) = 65$$S(8) = 114$
A: Hint: One way is to look at $3$ sequences:


*

*$a_n$: number of valid sequences of length $n$ 

*$b_n$: number of valid sequences of length $n$ ending with $0$

*$c_n$: number of valid sequences of length $n$ ending with $01$


This should help you write a recurrence relation for $a_n$...
A: Using notation above 
Any sequence $a_{n+1}$ can be obtained by appending $0$ or $1$ to any valid sequence of size $n$ ending in $11$ there are $(a_{n}-b_{n}-c_{n})$ such sequences. Similarly we can append $0$ or $1$ to any sequence ending in $0$ but we can only append $1$ to any sequence ending in $01$. 
Hence $$a_{n+1}=2(a_{n}-c_{n}-b_{n})+2b_{n}+c_{n}=2a_{n}-c_{n}.$$ 
Now consider $c_{n}$ we can obtain $c_{n}$ be appending $01$ onto the end of any valid sequence in $a_{n-2}$ provided it does not end in $01$, there are $a_{n-2}-c_{n-2}$ such sequences. Hence $c_{n}=a_{n-2}-c_{n-2}$ and so $c_{n}=a_{n-2}-a_{n-4}+a_{n-6}-a_{n-8}...$
