Manipulation of generating functions+quadratic equation with generating functions

Question

Generating functions really give me a hard time. I'm trying to understand this proof. There are two things I don't see. How do you get the quadratic equation with the $P(z)$ (with straightforward manipulations)? Secondly why can one derive $P(z) = z^2 C(z)^2$?

Answer 1

OP did not identify source, hence some guesswork required as to context and objective. I get for plane trees by path length the following functional equation:

$$T(z,u) = z + z T(uz,u) + z T(uz, u)^2 + \cdots = z \frac{1}{1-T(uz, u)}.$$

This is because in the recursive step the subtrees being attached to the new root have their path lengths for every node incremented by one, plus the root, with zero path length. Looking this up in the OEIS we find OEIS A138158 where we discover that there is no simple closed form for $[u^k] [z^n] T(z, u).$

We have

$$\sum_{n\ge 1} E_n z^n = \frac{1}{2} (T(z,1) + T(z,-1)) \quad\text{and}\quad \sum_{n\ge 1} O_n z^n = \frac{1}{2} (T(z,1) - T(z,-1))$$

and hence

$$\sum_{n\ge 1} (E_n-O_n) z^n = T(z, -1).$$

The functional equation tells us that

$$T(z, -1) = z \frac{1}{1-T(-z,-1)} \quad\text{and}\quad T(-z, -1) = - z \frac{1}{1-T(z, -1)}.$$

Substituting the latter into the former we find

$$T(z, -1) = z \frac{1}{1+z/(1-T(z, -1))}$$

which is

$$T(z, -1) (1 + z - T(z, -1)) = z (1 - T(z, -1))$$

or

$$T(z, -1) (1 + 2z - T(z, -1)) = z.$$

Solving the quadratic yields

$$T(z, -1) = z + \frac{1\pm\sqrt{1+4z^2}}{2}.$$

Here we must choose the second branch so as not to have a coefficient on $[z^0]$, which contradicts the functional equation. Note also that with

$$C(z) = \sum_{n\ge 0} C_n z^n = \frac{1-\sqrt{1-4z}}{2z}$$

we have

$$- C(-z) = \sum_{n\ge 0} (-1)^{n+1} C_n z^n = \frac{1-\sqrt{1+4z}}{2z}.$$

which says that

$$T(z, -1) = z - z^2 C(-z^2).$$

Extracting coefficients we get

$$[[n=1]] - [[n\ge 2]] \times [z^{n-2}] C(-z^2) \\ = [[n=1]] - [[n\ge 2,n\;\text{even}]]\times [z^{n/2-1}] C(-z) \\ = [[n=1]] + [[n\ge 2,n\;\text{even}]]\times (-1)^{n/2} C_{n/2-1}.$$

This may be verified using the Lagrange-Burmann formula with

$$z = \frac{T(z, -1)\times (1-T(z,-1))}{1-2T(z,-1)}$$

so that we get

$$[z^n] T(z, -1) = \frac{1}{n} [w^{n-1}] \frac{(1-2w)^n}{(1-w)^n}.$$

This is

$$\frac{1}{n} \sum_{q=0}^{n-1} {n\choose q} (-1)^q 2^q {2n-2-q\choose n-1}.$$

We get for the sum

$$\frac{1}{n} \sum_{q=0}^{n-1} {n\choose q} (-1)^q 2^q [v^{n-1-q}] (1+v)^{2n-2-q} \\ = \frac{1}{n} [v^{n-1}] (1+v)^{2n-2} \sum_{q=0}^{n-1} {n\choose q} (-1)^q 2^q v^q (1+v)^{-q}.$$

Here we get zero contribution to the coefficient extractor when $q\gt n-1$ and hence we may extend the sum to infinity (actually extension to $n$ is sufficient):

$$\frac{1}{n} [v^{n-1}] (1+v)^{2n-2} \left(1-\frac{2v}{1+v}\right)^{n} \\ = \frac{1}{n} [v^{n-1}] (1+v)^{n-2} (1-v)^{n} = \frac{1}{n} [v^{n-1}] (1-v^2)^{n-2} (1-2v+v^2).$$

Extracting coefficients from this we get for $n=1$ the value one, which is correct. For $n\ge 2$ with $n$ odd we obtain

$$\frac{1}{n} (-1)^{(n-1)/2} {n-2\choose (n-1)/2} + \frac{1}{n} (-1)^{(n-3)/2} {n-2\choose (n-3)/2} = 0.$$

For $n$ even we obtain

$$-\frac{2}{n} (-1)^{(n-2)/2} {n-2\choose (n-2)/2} = (-1)^{n/2} \frac{1}{(n-2)/2+1} {n-2\choose (n-2)/2} \\ = (-1)^{n/2} C_{n/2-1}.$$

This is the claim.

The Maple code that was used to verify the above and query the OEIS goes as follows.

with(combinat);

X :=
proc(n)
option remember;
local part, psize, mset, res;

    if n=1 then return 1 fi;

    res := 0;

    part := firstpart(n-1);

    while type(part, `list`) do
        psize := nops(part);
        mset := convert(part, `multiset`);

        res := res + u^(n-1)*
        mul(X(v), v in part)*
        psize!/mul(v[2]!, v in mset);

        part := nextpart(part);
    od;

    expand(res);
end;

EODIFF := n -> subs(u = -1 , X(n));

CAT := n -> 1/(n+1)*binomial(2*n,n);

EODIFFX := n ->
`if`(type(n,odd), `if`(n=1, 1, 0), (-1)^(n/2)*CAT(n/2-1));