2
$\begingroup$

The problem asks to find the functional equations for the generating functions whose coefficients satisfy $$ a_n = \sum_{i=0}^{n-1} a_i a_{n-1-i}\,\, (n\geq1), a_0 = 1 $$

There's an example that's similar to it in the text, prior to the exercises, but all I'm doing is mimicking. I don't understand how to solve this and what the double coefficient in the summand mean (an intuitive explanation would be very much appreciated).

$\endgroup$
  • 2
    $\begingroup$ The "double coefficient" is nothing more than multiplication: $xy$ means $x$ times $y$. $\endgroup$ – anon Apr 9 '13 at 7:35
  • 1
    $\begingroup$ @AlanH: You've changed spacing and changed it back. Are you trying to bump the question on the main list? What is it that you don't understand? $\endgroup$ – robjohn Apr 9 '13 at 21:59
  • $\begingroup$ @robjohn I was curious what rollback was. I'll change it back; I didn't edits bumped questions up. Sorry. I'm still going through your response. $\endgroup$ – AlanH Apr 9 '13 at 22:01
5
$\begingroup$

Consider the generating function of $a_k$ $$ f(x)=\sum_{k=0}^\infty a_kx^k\tag{1} $$ Apply the recursion above: $$ \begin{align} f(x) &=\sum_{k=0}^\infty a_kx^k\\ &=1+\sum_{k=1}^\infty\sum_{j=0}^{k-1}a_ja_{k-j-1}x^k\\ &=1+x\sum_{k=1}^\infty\sum_{j=0}^{k-1}a_ja_{k-j-1}x^jx^{k-j-1}\\ &=1+x\sum_{k=0}^\infty\sum_{j=0}^\infty a_jx^j\,a_kx^k\\ &=1+xf(x)^2\tag{2} \end{align} $$ The steps in $(2)$ are related to the Cauchy Product Formula.

Solving $(2)$ for $f(x)$ with the quadratic formula and applying the binomial theorem to $(1-4x)^{1/2}$ yields $$ \begin{align} f(x) &=\frac{1-\sqrt{1-4x}}{2x}\\ &=\sum_{k=0}^\infty\frac1{k+1}\binom{2k}{k}x^k\tag{3} \end{align} $$ Comparing $(1)$ and $(3)$, we get $$ a_k=\frac1{k+1}\binom{2k}{k}\tag{4} $$ Note that these are the Catalan Numbers. You can see the recursion above here.


Binomial Expansion of $\boldsymbol{(1-4x)^{1/2}}$

$$ \begin{align} (1-4x)^{1/2} &=1+\frac{\frac12}{1}(-4x)+\frac{\frac12(-\frac12)}{1\cdot2}(-4x)^2 +\frac{\frac12(-\frac12)(-\frac32)}{1\cdot2\cdot3}(-4x)^3+\dots\\ &=1-\sum_{k=1}^\infty\frac{(2k-3)!!}{2^kk!}4^kx^k\\ &=1-\sum_{k=1}^\infty\frac{(2k-2)!}{2^{k-1}(k-1)!k!}2^kx^k\\ &=1-\sum_{k=1}^\infty\frac2k\binom{2k-2}{k-1}x^k\tag{5} \end{align} $$ Thus, $$ \begin{align} \frac{1-\sqrt{1-4x}}{2x} &=\sum_{k=1}^\infty\frac1k\binom{2k-2}{k-1}x^{k-1}\\ &=\sum_{k=0}^\infty\frac1{k+1}\binom{2k}{k}x^k\tag{6} \end{align} $$

$\endgroup$
  • $\begingroup$ okay so you used the generalized binomial theorem, then how do you get the coefficient of $x^k$ in (3)? $\endgroup$ – AlanH Apr 9 '13 at 22:36
  • $\begingroup$ @AlanH: added a section to the answer. $\endgroup$ – robjohn Apr 9 '13 at 23:35
  • $\begingroup$ oh wow...Thanks for that. $\endgroup$ – AlanH Apr 9 '13 at 23:40
2
$\begingroup$

Hint:

If $$f(x) = a_0 + a_1 x + a_2 x^2 + \dots$$

then what is $(f(x))^2$? (when we attempt to express as power series).

For sake of completion, the coefficient of $x^{k}$ in $(f(x))^2$ is

$$ a_0 a_k + a_1 a_{k-1} + a_{2} a_{k-2} + \dots + a_{k-1}a_{1} + a_{k}a_{0} = \sum_{i=0}^{k} a_i a_{k-1}$$

Since we have that $$a_n = \sum_{i=0}^{n-1} a_i a_{n-1-i}$$

The coefficient of $x^{n-1}$ in $(f(x))^2$ is same as the coefficient of $x^n$ in $f(x)$ and since $a_0 = 1$, we get the functional equation

$$f(x) = 1 + x (f(x))^2$$

$\endgroup$
0
$\begingroup$

Write your recurrence as: $$ a_{n + 1} = \sum_{0 \le k \le n} a_k a_{n - k} $$ Define $A(z) = \sum_{n \ge 0} a_n z^n$. Multiply by $z^n$, sum over $n \ge 0$. The LHS is just: $$ \frac{A(z) - a_0}{z} $$ the RHS is: $$ A(z) \cdot A(z) $$ thus: $$ A(z) = a_0 + z A^2 (z) $$ This gives: $$ A(z) = \frac{1 \pm \sqrt{1 - 4 a_0 z}}{2 z} $$ The positive sign is spurious, $A(0) = a_0$ is finite. Expand the square root by the generalized binomial theorem: $$ A(z) = \frac{1}{2 z} \, \left( 1 - \left( 1 + \sum_{n \ge 1} \frac{(-1)^{n - 1}}{n 2^{2 n - 1}} \, \binom{2 n - 2}{n - 1} \, (-4 a_ 0 z)^n \right) \right) = \sum_{n \ge 0} \frac{1}{n + 1} \binom{2 n}{n} a_0^{n + 1} z^n $$ and thus: $$ a_n = \frac{1}{n + 1} \binom{2 n}{n} a_0^{n + 1} $$ This is intimetaly related to the famous Catalan numbers. A dead giveaway for them is their generating function's functional equation $C(z) = 1 + z C^2(z)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.