# Explicit formula for a generating function

In an enumeration problem the sequence of number of Dyck paths semilength n having no UUDD's starting at level 0 with generating function $$\frac{2}{(1+2z^2+\sqrt{1-4z})}$$ showed up, see also https://oeis.org/A114487. It is not really important but I wonder whether a nice explicit formula exists for this sequence.

Im not really experienced with such problems but I saw that sometimes very nice formulas exit for such non-rational generating functions. For example for the Motzkin numbers $M_n$ with generating function $\frac{ 1 - x - (\sqrt{1-2x-3x^2} )}{ 2x^2}$ the explicit formula $M_n=\sum\limits_{k=0}^{[\frac{n}{2}]}{\binom{n}{2k}C_k}$ exists when $C_k$ are the Catalan numbers, see https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5310552/.

• You can make a summation by applying the binomial theorem to the numerator of the rationalized version $$\frac{1+2z^2-\sqrt{1-4z}}{2z(1+z+z^3)}$$. – Brendan McKay Jun 16 '18 at 11:37
• @BrendanMcKay... But even for $1/(1+z+z^3)$, where the coefficients satisfy a third-order recurrence, is there a nice-looking closed form? – Gerald Edgar Jun 16 '18 at 11:41
• @GeraldEdgar That is at least one summation for even powers and one for odd powers. But, I guess "nice" is a bit strong a word. – Brendan McKay Jun 16 '18 at 11:46
• More precisely, it is $-(1-z-z^3)$, not $1+z+z^3$; the $n$th coefficient of $\frac1{1-z-z^3}$ is ${\displaystyle\sum_{k=0}^{\left[\frac n3\right]}}\binom{n-2k}k$. – მამუკა ჯიბლაძე Jun 16 '18 at 12:42

The coefficient of $z^n$ is $$\sum_{0\le k\le n/2} (-1)^k \frac{k+1}{2n-3k+1}\binom{2n-3k+1}{n-2k}.$$

To see this, let $C(z)$ be the Catalan number generating function, $$C(z) = \frac{1-\sqrt{1-4z}}{2z}=\frac{2}{1+\sqrt{1-4z}}.$$ Then $$\frac{2}{1+2z^2+\sqrt{1-4z}} = \frac{C(z)}{1+z^2 C(z)}.$$ It is well known that $$C(z)^j = \sum_{m=0}^\infty \frac{j}{2m+j}\binom{2m+j}{m} z^m.$$ Thus \begin{aligned} \frac{2}{1+2z^2+\sqrt{1-4z}}&=\sum_{k=0}^\infty (-1)^k z^{2k}C(z)^{k+1}\\ &=\sum_{k=0}^\infty (-1)^k z^{2k} \sum_m \frac{k+1}{2m+k+1}\binom{2m+k+1}{m} z^m\\ &=\sum_n z^n \sum_{0\le k\le n/2} (-1)^k \frac{k+1}{2n-3k+1}\binom{2n-3k+1}{n-2k}. \end{aligned}

I have added this formula to the OEIS entry.

• It is very nice anyway, but would not $\sum(-1)^k\frac{k+1}{n-k+1}\binom{2n-3k}{n-k}$ or $\sum(-1)^k\frac{k+1}{n-k+1}\binom{2n-3k}{n-2k}$ look slightly tidier? – მამუკა ჯიბლაძე Jun 16 '18 at 15:11
• Yes, either of these would look slightly tidier. – Ira Gessel Aug 25 '18 at 20:41

This can be done with help of Maple, realizing the Brendan McKay's suggestion, in such a way:

a := convert(expand(convert(-sqrt(1-4*z), FPS, z, j)+1+2*z^2), FPS, z);


$$\sum _{j=0}^{\infty }{\frac { \left( 2\,j \right) !\,{z}^{j}}{ \left( j! \right) ^{2} \left( -1+2\,j \right) }}+1+2\,{z}^{2}$$

b := b := allvalues(convert(1/(2*z*(-z^3-z+1)), FPS, z));


$$1/2\,{z}^{-1}+\sum _{k=0}^{\infty } \left( {\frac {4\, \left( 1/6\, \sqrt [3]{108+12\,\sqrt {93}}-2\,{\frac {1}{\sqrt [3]{108+12\,\sqrt { 93}}}} \right) ^{2}+\sqrt [3]{108+12\,\sqrt {93}}-12\,{\frac {1}{ \sqrt [3]{108+12\,\sqrt {93}}}}+13}{62\, \left( 1/6\,\sqrt [3]{108+12 \,\sqrt {93}}-2\,{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}} \right) ^{ k+1}}}+{\frac {4\, \left( -1/12\,\sqrt [3]{108+12\,\sqrt {93}}+{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}}+i/2\sqrt {3} \left( 1/6\,\sqrt [3] {108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}} \right) \right) ^{2}-1/2\,\sqrt [3]{108+12\,\sqrt {93}}+6\,{\frac {1 }{\sqrt [3]{108+12\,\sqrt {93}}}}+3\,i\sqrt {3} \left( 1/6\,\sqrt [3]{ 108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}} \right) +13}{62\, \left( -1/12\,\sqrt [3]{108+12\,\sqrt {93}}+{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}}+i/2\sqrt {3} \left( 1/6\,\sqrt [3] {108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}} \right) \right) ^{k+1}}}+{\frac {4\, \left( -1/12\,\sqrt [3]{108+12 \,\sqrt {93}}+{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}}-i/2\sqrt {3} \left( 1/6\,\sqrt [3]{108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108 +12\,\sqrt {93}}}} \right) \right) ^{2}-1/2\,\sqrt [3]{108+12\,\sqrt {93}}+6\,{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}}-3\,i\sqrt {3} \left( 1/6\,\sqrt [3]{108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108 +12\,\sqrt {93}}}} \right) +13}{62\, \left( -1/12\,\sqrt [3]{108+12\, \sqrt {93}}+{\frac {1}{\sqrt [3]{108+12\,\sqrt {93}}}}-i/2\sqrt {3} \left( 1/6\,\sqrt [3]{108+12\,\sqrt {93}}+2\,{\frac {1}{\sqrt [3]{108 +12\,\sqrt {93}}}} \right) \right) ^{k+1}}} \right) {z}^{k}$$

It remains to multiply these series.

• I think there is a wrong exponent in the denominator of b. As GeraldEdgar says, the coefficients have a third order linear recursion, and they are linear combinations of powers of roots of $1+z+z^{\bf 3}.$ – Pietro Majer Jun 16 '18 at 12:55
• @Pietro Majer: Thank you for your valuable comment. In this case Maple performs the expansion too, but the formulas are somewhat longer. – user64494 Jun 16 '18 at 13:02
• Thanks, but Im not sure whether this qualifies as a nice formula. – Mare Jun 16 '18 at 13:09
• @Mare: An explicit closed-form expression is asked in the title of your question. – user64494 Jun 16 '18 at 13:12
• Yes so it is good to see it here, but there might be a much nicer closed form (see the example with the Motzkin numbers, where such a direct approach probably also would end up uglier than the formula given). – Mare Jun 16 '18 at 13:15