2
$\begingroup$

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} $$

$\endgroup$
2

2 Answers 2

3
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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? $\endgroup$
    – novice
    Apr 13, 2019 at 23:44
  • $\begingroup$ That's right! And then multiply by $z$. I've put the extra steps into my answer. $\endgroup$ Apr 14, 2019 at 4:28
  • 1
    $\begingroup$ Thanks, I understood now. $\endgroup$
    – novice
    Apr 14, 2019 at 7:39
  • 1
    $\begingroup$ 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. $\endgroup$
    – novice
    Apr 14, 2019 at 8:02
0
$\begingroup$

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 $$

$\endgroup$
4
  • $\begingroup$ Thanks for your reply. As I tested, this will generate ${x,0,4x^3,0...}$, not exactly same with the question... $\endgroup$
    – novice
    Apr 11, 2019 at 17:24
  • $\begingroup$ 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 $\endgroup$ Apr 11, 2019 at 18:37
  • $\begingroup$ @MartinHansen I don't understand, can you provide more details? thanks. $\endgroup$
    – novice
    Apr 13, 2019 at 15:42
  • $\begingroup$ 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. $\endgroup$ Apr 13, 2019 at 20:50

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.