# What is the generating function of $z^3 + 2z^5 + 5z^7 + 14 z^9+\dots$?

What is the generating function of $$z^3 + 2z^5 + 5z^7 + 14 z^9+\dots$$ ?

The generating function can be written as follows: $$A(z)=\sum_{i>2}^{\infty} a_i z^{2i+1},\text{where } a_i \text{ is the Catalan numbers}$$

• $$\sum_{n=0}^\infty C_n x^n=\frac{1-\sqrt{1-4x}}{2x}$$ Apr 11, 2019 at 17:06
• – lhf
Apr 11, 2019 at 18:08

The Catalan numbers go, $$1,1,2,5,14,42,132,429, \dots$$ The generating series you are after is, $$z^3+2z^5+5z^7+14z^9+42z^{11}+\dots$$ As Lord Shark the Unknown points out the generating function for the Catalan numbers is well known, $$\frac{1-\sqrt{1-4z}}{2z}=1+z^1+2z^2+5z^3+14z^4+42z^5+...$$ To insert a single interlacing zero between the terms you need to replace $$z$$ with $$z^2$$, $$\frac{1-\sqrt{1-4(z^2)}}{2(z^2)}=1+(z^2)^1+2(z^2)^2+5(z^2)^3+14(z^2)^4+42(z^2)^5+\dots$$ Now multiply both sides by z, $$\frac{1-\sqrt{1-4z^2}}{2z}=z+z^3+2z^5+5z^7+14z^9+42z^{11}+\dots$$

To remove the unwanted initial z, simply subtract it from both sides and so the generating function you are after is, $$\frac{1-\sqrt{1-4z^2}}{2z}-z=z^3+2z^5+5z^7+14z^9+42z^{11}+...$$ There is a marvellous online tool you can use to quickly check what generating series a generating function expands into. It's the Taylor Series Expansion Calculator at https://www.numberempire.com/taylorseriesexpansion.php

• Thanks. When we replace $z$ with $z^2$, we will get $1(z^2)^0 + 1(z^2)^1+2(z^2)^2+5(z^2)^3 ...$, right? Apr 13, 2019 at 23:44
• That's right! And then multiply by $z$. I've put the extra steps into my answer. Apr 14, 2019 at 4:28
• Thanks, I understood now. Apr 14, 2019 at 7:39
• by the way, there is a minor typo, $z^2$ was supposed to be $4z^2$ in the two euqations you added earlier. (I couldn't edit it, it says at least 6 characters...) Thanks for your solution again. Apr 14, 2019 at 8:02

Let $$C(z)=\sum_{n=0}^\infty C_nz^n$$ be the generating function for the Catalan numbers. Then your series is the generating function of the odd terms minus the first term i.e. given by $$\frac{C(z)-C(-z)}{2}-z$$

• Thanks for your reply. As I tested, this will generate ${x,0,4x^3,0...}$, not exactly same with the question... Apr 11, 2019 at 17:24
• Multiply the generating function associated with $x, 0, 4x^3,0,\dots$ by $x$ then replace all occurrences of $x$ with $\sqrt{x}$ and simplify Apr 11, 2019 at 18:37
• @MartinHansen I don't understand, can you provide more details? thanks. Apr 13, 2019 at 15:42
• Apologies, I was talking rubbish. I've had a proper look at this now and have just posted a most excellent answer - Hope you like it ! Green tick it if so. If you need to prove how to get the generating function for the Catalan Numbers just ask. It's a quotable well known result. I enjoyed puzzling over the question. Apr 13, 2019 at 20:50