Here are all such sequences of length 1.
[1]
Here are all such sequences of length 2.
[1, 1]
[1, 2]
Here are all such sequences of length 3.
[1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[1, 2, 2]
[1, 2, 3]
Here are all such sequences of length 4.
[1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 1, 2, 2]
[1, 1, 2, 3]
[1, 2, 1, 1]
[1, 2, 1, 2]
[1, 2, 1, 3]
[1, 2, 2, 1]
[1, 2, 2, 2]
[1, 2, 2, 3]
[1, 2, 3, 1]
[1, 2, 3, 2]
[1, 2, 3, 3]
[1, 2, 3, 4]
Please observe how the sequences grow longer and longer with the condition
$$a_{n+1} \leq \max_{1\le i \le n} (a_{i}+1) = 1+\max_{1\le i \le n} a_{i}$$
as well as the recurrence relation
$$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m).$$
$a_{2} = a_{1+1} \leq \max_{1 \leq i \leq 1}(a_{i}+1) $ which mean i can only be 1. Then $a_{2} \leq \max(2)$. and $a_{3}\leq \max(3)$.
Yes, $a_{2} \leq \max(2)=2$. However, $a_{3}\leq \max(a_1+1, a_2+1)$. If $a_2=1$, then $a_3\le \max(1+1, 1+1)=2$. While $a_3\le \max(3)=3$ is true, it might be relaxed too much.
Let us see how we are going to fill the two dimensional array sequence($m$,$l$).
For example, how to use the following relation?
$$\text{sequence}(4,4) = \text{sequence}(3, 3 ) + 4 * \text{sequence}(3,4)\,.$$
We know sequence$(3,3) = 1$ since there is only one sequence of length 3 and maximum number 3, $[1,2,3]$ or sequence$(3,3) = 1 + 3 * 0 = 1$. There is no sequence of length of length 3 and maximum number 4, since the maximum number in any sequence of length 3 is at most 3. So $$\text{sequence}(4,4) = 1 + 4 * 0 = 1\,,$$
which corresponds to the unique sequence of length 4 and maximum number 4, $[1,2,3,4]$.
What is exactly $m$ in $\text{sequence}(l, m)$? Where should we place $a_4$ in the table of $l * m$?
It looks like you need to understand the recurrence relation.
$$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m),$$
where $\text{sequence}(l,m)$, $l\ge2$, $m\ge1$ is the number of sequences whose length is $l$ and whose maximum number is $m$. For example, a sequence $(a_1, a_2,a_3,a_4)$ is a sequence of length 4 and whose maximum number is $\max(a_1, a_2,a_3,a_4)$. If that maximum number is $k$, it contributes 1 to $\text{sequence}(4, k)$ if it satisfies the two conditions. For example, sequence $(1,2,3,2)$ contributes 1 to $\text{sequence}(4, 3)$ while sequence $(1,1,2,2)$ contributes 1 to $\text{sequence}(4, 2)$.
Let $a_1, a_2, \cdots, a_l$ be such a sequence. Let us consider its first $l-1$ items, $a_1, a_2,\cdots, a_{l-1}$.
The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is smaller than $m-1$. Then $$a_{l} = a_{(l-1)+1}\leq \max_{1\le i \le l-1} (a_{i}+1) = 1+\max_{1\le i \le l-1} a_{i}\lt m$$, which contradicts that fact that the maximum number of all of them is $m.
So this situation cannot happen.
The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is $m-1$. Then $a_l$ must be $m$. Otherwise, the maximum number of the whole sequence will be $m-1$ instead of the required $m$.
So for each sequence counted in $\text{sequence}(l-1, m-1 )$, we have a sequence that should be counted in $\text{sequence}(l, m)$. We have a summand $\text{sequence}(l-1, m-1)$
The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is $m$. Then $a_l$ can be anyone of $1, 2, \cdots, m$ $m$. So for each sequence counted in $\text{sequence}(l-1, m)$, we have $m$ sequences that should be counted in $\text{sequence}(l, m)$. That is, we have a summand $ m * \text{sequence}(l-1, m)$.
Combining all three cases above, we obtain that recurrence relation.