I found it easiest to convert it to a problem in counting paths on the integer lattice in the plane: it can be solved using the reflection method, one of the standard ways to show that $C_n=\frac1{n+1}\binom{2n}n$, where $C_n$ is the $n$-th Catalan number.
Suppose that $\langle a_1,\ldots,a_5\rangle$ is such a sequence. We can interpret it as directions for a walk on the integer lattice in the plane, starting at the origin: we first take $a_1$ steps north to $\langle 0,a_1\rangle$, then one step east to $\langle 1,a_1\rangle$, then $a_2-a_1$ steps north to $\langle 1,a_2\rangle$ and one step east to $\langle 2,a_2\rangle$, and so on, finishing by taking $20-a_5$ steps north from $\langle 5,a_5\rangle$ to $\langle 5,20\rangle$; the requirement that each $a_k\ge k$ is then the requirement that this path never drop below the diagonal $y=x$. Moreover, each NE path (i.e., a path using only steps to the north and to the east) from $\langle 0,0\rangle$ to $\langle 5,20\rangle$ that never drops below the diagonal corresponds to a unique sequence $\langle a_1,\ldots,a_5\rangle$ satisfying the conditions of the problem, so our problem reduces to counting such paths.
Suppose that a path first drops below the diagonal at $\langle k,k-1\rangle$; after that point it must take $5-k$ steps to the east and $21-k$ to the north. If we reflect it in the diagonal, we get a path starting at $\langle k,k-1\rangle$ and taking $21-k$ steps to the east and $5-k$ steps north and thus ends at $\langle 21,4\rangle$. Conversely, any NE path from $\langle 0,0\rangle$ to $\langle 21,4\rangle$ must stay on or above the diagonal until it hits a point of the form $\langle k,k-1\rangle$, and reflecting the remainder of the path in the diagonal gives us a path from $\langle 0,0\rangle$ to $\langle 5,20\rangle$ that first drops below the diagonal at $\langle k,k-1\rangle$.
There are clearly $\binom{25}5$ NE paths from $\langle 0,0\rangle$ to $\langle 5,20\rangle$. There is a bijection between those that drop below the diagonal and NE paths from $\langle 0,0\rangle$ to $\langle 21,4\rangle$, and there are $\binom{25}4$ of those, so there are $$\binom{25}5-\binom{25}4=53130-12650=40480$$ NE paths from $\langle 0,0\rangle$ to $\langle 5,20\rangle$ that do not drop below the diagonal.
More generally, the number of non-decreasing sequences $a_1,\ldots,a_n$ such that $a_1\ge 1$, $a_k\ge k$ for $k=1\ldots,n$, and $a_n\le m$ is
$$\binom{n+m}n-\binom{n+m}{n-1}=\binom{n+m}n-\frac{n}{m+1}\binom{n+m}n=\frac{m+1-n}{m+1}\binom{n+m}n\;.$$
When $m=n$ this reduces to $C_n=\frac1{n+1}\binom{2n}n$.
Best Answer
Hint: By taking the log (with respect to any base) of both sides, we can rewrite the recurrence as $$ \log(a_n) = \frac 12[\log(a_{n-1}) + \log(a_{n-2})] $$ So, the sequence $b_n := \log(a_n)$ satisfies a linear recurrence.