How many ways to split a convex polygon to squares?

Question

If $a_0 = 0$ and $a_1 = 1$, and $a_n$ stands for the number of ways to split a convex polygon with $n+1$ angles to squares, is given by

$$a_n = \sum_{k+l+m = n }a_ka_la_m$$

Now, using generating function, I'm supposed to get a functional equation.

1. How can I find it?
2. After I find it, I'm supposed to use Lagrange's inversion theorem in order to find the general solution for $a_n$.

Answer 1

I can help you with finding the functional equation, but not with the Lagrange inversion.

The recurrence is valid only when $n\neq 1$.

Let $A(x) = \sum_{n\ge 1}a_{n}x^n$. Note that $\sum_{k+l+m=n}a_ka_la_m$ is equal to the coefficient of $x^n$ in $A(x)^3$. Therefore, $$ A(x) = a_1x+\sum_{n\ge 2}a_nx^n =x+\sum_{n\ge 2}[\text{coef of $x^n$ in $A(x)^3$}]x^n=x+A(x)^3. $$