Ordered binary sequences of length n with no two consecutive 0's without using recursion Given ordered sequences of 0's and 1's of length n. In how many of them no two 0's stand next to each other? Could you do if n=25. 
I know this can be solved by using recursion.
I am not familiar with solving recurrence equations. Could this be done another way? 
 A: Just to put in a defense of recursive methods:
Let $A_n$ be the number of "good" sequences of length $n$.  It is reasonably clear that any good sequence (of length at least $2$) ends in either $0$ or $01$.  Of course what precedes that ending must be a good sequence of shorter length.  Conversely, any good sequence of length $n-1$ becomes a good sequence of length $n$ if you append a $0$ and any good sequence of length $n-2$ becomes a good sequence of length $n$ if you append $01$. Thus we see that $$A_n=A_{n-1}+A_{n-2}$$  Which we recognize as the Fibonacci recursion.  Since $A_1=2$ and $A_2=3$ it is easy to generate $A_n$ for any modest $n$.  No need to solve the recursion (though of course that is possible).  
A: What follows is definitely more of a comment than an answer, providing
a hint  in case other  approaches prove  too difficult. Many  of these
types of problems can be solved with regular expressions. In your case
we have the regex $$1^* (01^+)^* (0|\epsilon).$$
Now  use $z$  for zeros  and  $w$ for  ones to  get the  generating
function
$$\frac{1}{1-w} \left(\sum_{q\ge 0} z^q \frac{w^q}{(1-w)^q}\right) 
(1+z).$$
This yields
$$\frac{1}{1-w} \frac{1}{1-zw/(1-w)} (1+z)
= \frac{1}{1-w-zw} (1+z).$$
As the requirements of the problem  only specify the count we may drop
the distinction between zeroes and ones at this point to obtain
$$\frac{1+z}{1-z-z^2}.$$
We may now continue as in the answer by @MarkusScheuer.
