Find a recurrence relation for the number of ways to divide an n-gon into triangles with noncrossing diagonals.
The solution to this question is: $a_n = a_{n-1}a_3 + a_{n-2}a_4 + ... + a_3a_{n-1}$
I understand that $a_4 = 2$ and $a_5 = 5$ and $a_6 = 14$, but I'm confused on how I can continue this pattern to develop the recurrence relationship presented in the solution. In other words, I'm really not sure where the solution comes from...recurrence relations is a major struggle of mine.
I suspect your $n$-gon is regular (or at least convex).
The correct solution is $a_n = a_{n-1} a_2 + a_{n-2} a_3 + \ldots + a_2 a_{n-1}$, where we put $a_2 = 1$.
To get it, consider an $n$-gon $P$ with $n > 3$, and pick any two adjacent vertices $A, B$ in it. Now if $P$ is split into triangles, consider the vertex $C$ such that $ABC$ is one of these triangles. If we remove $ABC$ from $P$, we are left either with two polygons with a common vertex $C$ (thus if one of these polygons contains $k$ vertices, the other contains $n + 1 - k\ $ vertices), or with a single polygon with $n - 1$ vertices. Conversely, if we take for $C$ any of the remaining $n - 2$ vertices, remove $ABC$ from $P$, and split the remaining polygons, we obtain a splitting of $P$. This explains the formula stated above, with the first and the last term corresponding to a single polygon left after removing $ABC$, and each of the remaining terms (if any) to a pair of polygons left.
In closed form, the solution is $a_n=C_{n-2}=\dfrac{1}{n-1}\dbinom{2n-4}{n-2}$.