Let $t_n$ be the number of sequences $a_1, a_2, . . . , a_n$ of $n$ integers such that $a_1 \leq a_2 \leq \cdots \leq a_n$ and $1 \leq a_i \leq i$ for each $i$. For $n = 3$, the sequences are $(1, 1, 1), (1, 1, 2), (1, 2, 2), (1, 1, 3)$, and $(1, 2, 3)$. Show that $t_0 = t_1 = 1$ and that $t_n$ satisfies the recurrence relation $$t_n = t_0 t_{n−1} + t_1 t_{n−2} + t_2 t_{n−3} + \cdots + t_{n−1} t_0.$$
I'm trying to find a proof similar to that of the Catalan numbers but I'm not sure where to start.
Call a sequence $s= (a_1, \cdots, a_n)$ good if $1\le a_i \le i$ for all $1\le i \le n$ and $a_1 \le a_2 \le \cdots \le a_n$. Let $t_n$ denote the number of good sequences of length $n$. Note that any good sequence has $a_1 = 1$, and hence we may associate to the sequence an index $j = j(s) := \max\{ i \, : \, a_i = i\}$.
Given a good sequence $s$, we have $a_k \le k-1$ for $k>j$, and hence the sequence $$(a_{j+1} - (j-1), a_{j+2} - (j-1), \cdots, a_n - (j-1))$$ is a good sequence of length $n-j$. Moreover, the sequence $(a_1, \cdots, a_{j-1})$ is itself a good sequence of length $j-1$. Conversely, given any good sequence $s_1$ of length $j-1$ and any good sequence $s_2$ of length $n-j$, the concatenation $(s_1, j, s_2 + j-1)$ is a good sequence of length $n$.
We conclude that the number of good sequences $s$ with $j(s) = j$ is precisely $t_{j-1} t_{n-j}$ and hence $$t_n = \sum_{j=1}^{n} t_{j-1} t_{n-j}$$ as desired.