How many ways can $n$ spaces be used with blocks of size $\le n$ (or leave empty) How many ways $n$ spaces be 'used' with blocks of size $\le n$ 
and counting empty spaces as a way of using them.
The first thing came to my mind is to calculate compositions of n (like partitions but with order) so there are $2^{n-1}$ possible compositions, for example  
$2^{3-1}=4$ 
   1) 3 = 3    
   2) 3 = 2 + 1     
   3) 3 = 1 + 2     
   4) 3 = 1 + 1 + 1 

But!, this doesn't count any zero values! 
So I think in summing up the previous compositions till n, $\sum_{k=0}^n 2^{k-1} = 2^n-1$ so for example adding these combinations
   5) 2 = 2 + 0 
   6) 2 = 1 + 1 + 0

   7) 1 = 1 + 0 + 0

$2^n-1=7$
But this is wrong! because it would not count "left zeros" nor "intermediate zeros" I mean, I need to count also these sums
2 = 0 + 2
2 = 1 + 0 + 1
2 = 0 + 1 + 1
1 = 0 + 1 + 0
1 = 0 + 0 + 1 
0 = 0 + 0 + 0

How can this be calculated?
 A: Let $T_n$ be the number of ways to fill $n$ spaces. 
Case 0: The leftmost space is empty. 
After leaving that space empty, there are $T_{n-1}$ ways to use the remaining $n-1$ spaces. 
Case k (for $1 \le k \le n$): The left most space is occupied by a block of length $k$. 
After laying down the block of length $k$, there are $n-k$ spaces left, and thus, $T_{n-k}$ ways to use these spaces. 
Adding these up yields $T_n = 2T_{n-1} + T_{n-2} + T_{n-3} + \cdots + T_{1} + T_{0}$. 
To simplify the recurrence relation, note that $T_{n+1} = 2T_{n} + T_{n-1} + T_{n-2} + \cdots + T_{1} + T_{0}$. 
Subtraction yields $T_{n+1} - T_n = 2T_n - T_{n-1}$, i.e. $T_{n+1} = 3T_n - T_{n-1}$. 
Clearly, there is $T_0 = 1$ way to use $0$ spaces, and $T_1 = 2$ ways to use $1$ space.
Now, you have a linear recurrence relation and initial conditions. :)
Note: I'm assuming that $0 = 0+0+\cdots+0+0$ counts as a way to use $n$ spaces. If it doesn't, then you should compute $T_n - 1$ instead. 
A: Generate the sequence for $n=0,1,2,\ldots$, which is:
$1,2,5,13,34,89,233,610,1597,4181,\ldots$
and take it to OEIS. We will find these related sequences: A001519, A122367 and A099496
In summary, the recurrence is:
$$
a_n=3\, a_{n-1} - a_{n-2} \hspace{20mm} a_0=1,a_1=2
$$
also $$a_n=\operatorname{Fibonacci}(2\, n+1)$$
and the generating function is:
$$G(x)=\frac{1-x}{1-3\, x+x^2}$$
