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
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 '19 at 23:44
  • $\begingroup$ That's right! And then multiply by $z$. I've put the extra steps into my answer. $\endgroup$ – Martin Hansen Apr 14 '19 at 4:28
  • 1
    $\begingroup$ Thanks, I understood now. $\endgroup$ – novice Apr 14 '19 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 '19 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 '19 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$ – Martin Hansen Apr 11 '19 at 18:37
  • $\begingroup$ @MartinHansen I don't understand, can you provide more details? thanks. $\endgroup$ – novice Apr 13 '19 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$ – Martin Hansen Apr 13 '19 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.