Multiple choice question about generating function of a sequence

Question

Suppose $\left\{a_n\right\}_{n=0}^{\infty}$ is sequence . and we have below recursion relation$$\begin{cases}a_n=\sum_{k=0}^{n-1}a_ka_{n-k-1}\\\\a_0=1\end{cases}$$

If $f(x)=\sum_{n=0}^{\infty}a_nx^n$ is generating function of $a_n$ which one is correct .

$$1)\space f^2(x)+xf(x)-1=0\\ 2)\space f^2(x)-xf(x)+1=0 \\ 3)\space xf^2(x)+f(x)-1=0 \\ 4)\space xf^2(x)-f(x)+1=0 $$ I am sorry to ask this question , But as honestly as possible it was my student's question. I forgot this type of question . Can you help me or give me a clue . Thanks in advanced.

Answer 1

Multiply the recurrence formula by $x^n$ and rewrite it like this \begin{eqnarray*} a_n x^n = x \sum_{k=0}^{n-1} a_k x^k \; \; a_{n-k-1} x^{n-k-1} \end{eqnarray*} Now sum on $n$ (starting from $1$) \begin{eqnarray*} \sum_{n=1}^{\infty} a_n x^n = x \sum_{n=1}^{\infty} \sum_{k=0}^{n-1} a_k x^k \; \;a_{n-k-1} x^{n-k-1}. \end{eqnarray*} Invert the sums (Draw your student a grid of the points ... to convince them that the sums interchange as follows) \begin{eqnarray*} \sum_{n=1}^{\infty} a_n x^n = x \sum_{k=0}^{\infty} \sum_{n=k+1}^{\infty} a_k x^k \; \; a_{n-k-1} x^{n-k-1}. \end{eqnarray*} Make the change of variable $m=n-k-1$ & we have \begin{eqnarray*} \sum_{n=1}^{\infty} a_n x^n = x \sum_{k=0}^{\infty} a_k x^k \sum_{m=0}^{\infty} a_{m} x^{m}. \end{eqnarray*} & finally add $1$ to both sides ... none of the above ?

Answer 2

Hint: Note that $a_0 = f(0) =1$ and $a_1 = f'(0) =1$.

Now can you find the right answer between choices !?

Answer 3

Given $$a_0=1,a_1=1,a_2=2,a_3=5,a_4=14,a_5=42,a_6=132,...$$ these are Catalan numbers satisfying $$xf(x)^{2}-f(x)+1=0$$

Answer 4

To approach this kind of problems, multiply by $x^n$ both sides and sum over $n\ge 1$ (the range in which the equation is defined). Define $$f(x) = \sum_{n \ge 0} a_n x^n $$

If you apply the procedure I described, you get $$ (**) \ \ f(x) - a_0 = \sum_{n \ge 1} a_nx^n = \sum_{n \ge 1 } x^n \left ( \sum_{k=0}^{n-1} a_k a_{n-k-1} \right ) $$ Generally, if $C(x) = \sum_{n} c_n x^n, \ \ D(x) = \sum_n d_n x^n$, then $ C(x) D(x) = \sum_n x^n \left ( \sum_{k=0}^{n} c_k d_{n-k} \right ) $.

Thus $f^2(x) = \sum_n x^n b_n = \sum_n \left ( \sum_{k=0}^n a_k a_{n-k} \right )$. You can see that the equation $(**)$ rewrites as (beware indexes!): $$ f(x)-1= \sum_{n \ge 1} x^n c_{n-1} = x\sum_{n \ge 0} x^n c_n = x f^2(x) $$ So that, on balance: $$xf^2(x) -f(x)+1=0$$

If you just wanted to know which one of the multiple choice was right, with a little bit of practitìceyou could have guessed (3): infact the $\sum a_k a_{n-1 -k}$ which is the $n-1$ term of something quadratic in $f$ (you have "$a*a$") makes you think of a shift in a quadratic term, so that the $x$ will probably be next to $f^2$.