I'm trying to solve the following recurrence equation.
$$a_0 = 1,\hspace{5mm} a_n = \frac{1}{6}(n+1)(n+2) – \frac{1}{3} \sum_{\substack{0 \leq i,j < n,\\1 \leq i+j \leq n}} a_i a_j a_{n-i-j}$$
I started by considering the edge case $n=0$ and ended up with:
$$a_n = \frac{1}{6}(n+1)(n+2) – \frac{1}{3} \sum_{\substack{0 \leq i,j < n,\\1 \leq i+j \leq n}} a_i a_j a_{n-i-j} + \frac{2}{3}[n=0].$$
Let $A(x) = \sum_{n \geq 0} a_nx^n$ be the ordinary generating function of $a_n$. I tried to use the approach similar to solving recurrence equation for Catalan numbers and assumed $[A(x)]^3 = \sum_{n \geq 0}\sum_{\substack{0 \leq i,j < n,\\1 \leq i+j \leq n}} a_i a_j a_{n-i-j} \hspace{1mm} x^n$ because it is a triple convolution of $A(x)$. Next, I multiplied the original equation by $x^n$ and summed it over n:
$$A(x) = \sum_{n \geq 0}\frac{1}{6}(n+1)(n+2)x^n-\frac{1}{3}[A(x)]^3+\frac{2}{3}.$$
I know that $\frac{1}{6}(n+1)(n+2) = \frac{1}{3}\binom{n+2}{2}$. Using formula for generating functions for sequences of this kind, I arrived at:
$$A(x) = \frac{1}{3(1-x)^3} – \frac{1}{3}[A(x)]^3 + \frac{2}{3}.$$
However, I cannot solve this final equation and find the expression for $A(x)$. How can I move forward in solving this recurrence equation?
Best Answer
We can use hyperbolic functions to get a reasonably compact form for the generating function, but still it will be a bit messy to implement.
Begin by rearranging the equation algebraically:
$[A(x)]^3+3A(x)=\dfrac{1}{(1-x)^3}+2.$
Then define $A(x)=2\sinh u$ whereupon the left side becomes $2\sinh (3u)$, and then
$A(x)=2\sinh\left[\dfrac13\sinh^{-1}\left(\dfrac{1}{2(1-x)^3}+1\right)\right].$