, 2008

a.
To begin, we form $2^{2007}$ different sequences satisfying the given conditions. For all the sequences let $a_1 = 0$. Let each successive member of the sequence be "by 0 greater" or "by 1 greater" than the preceding one. Thus we obtain $2^{2007}$ different sequences. It's easy to show that $a_k \le k-1$ for each of these sequences. To prove that the number of sequences is greater than $2^{2007}$, one sequence will be enough, which is not in the list of $2^{2007}$ sequences, but satisfies the given conditions. E.g., it can be a sequence: $(0,0,2,2,...,2)$.

b.
Let's name some random non-decreasing sequence of non-negative integers $a_1 \le a_2 \le ... \le a_n$ obeying $a_k \le (k-1)$, $k=1, n$ as fine. Note that a random fine sequence with $(n+1)$ members can be obtained from fine sequence with $n$ members if you add a member $a_{n+1}$ for which $a_n \le a_{n+1} \le n$ is true. Similarly, if we remove the last member of some sequence with $(n+1)$ members, we obtain fine sequence with $n$ members.

Let the number of fine sequences with $n$ members be $x_n$. We can obviously build at least two different fine sequences with $(n+1)$ members if we assign the two allowable possibilities for $a_{n+1}$: they will be $a_n$ or $(a_n + 1)$. Similarly, proceeding analyzing, we find $x_{n+m} \ge 2^m x_n$.
Now you only have to find out the number of sequences for a small value of $n$. $x_1 = 1$ as there is only one such a sequence: $(0)$. Again you'll easily find that $x_2 = 2$ because only sequences $(0,0)$ and $(0,1)$ can be regarded as fine. Thus we have an assessment $x_{2008} \ge 2^{2006} x_2 = 2^{2007}$, but it is not enough. To obtain a sequence with 3 members, we may add one of the numbers $0,1,2$ to the sequence $(0,0)$, and one of the numbers $0,1$ to the sequence $(0,1)$. I.e., $x_3 = 5$ and $x_{2008} \ge 2^{2005} x_3 = 5 \cdot 2^{2005} > 2^{2007}$.
After that we continue calculating the number of fine sequences for small values of $n$: $(0,0,0) \rightarrow 0,1,2,3$, $(0,0,1), (0,1,1) \rightarrow 1,2,3$, $(0,0,2), (0,1,2) \rightarrow 2,3$. I.e. in all we obtain 14 different fine sequences and therefore $x_4 = 14$ and $x_{2008} \ge 2^{2004} x_4 = 14 \cdot 2^{2004} > 5 \cdot 2^{2005}$.
As one of these fine sequences ends in $0$, we can add $0,1,2,3,4$. As three of the sequences end in $1$, we can add $1,2,3,4$. As five of the sequences end in $2$, we can add $2,3,4$: as another five end in $3$, we can add $3,4$. So in all we have $5 \cdot 1 + 3 \cdot 4 + 5 \cdot 3 + 5 \cdot 2 = 42$, which implies the first proven assessment: $x_{2008} \ge 2^{2003} x_5 = 42 \cdot 2^{2003} > 32 \cdot 2^{2003} = 2^{2008}$.