# Generating function of $\binom{3n}{n}$ [duplicate]

Wolfram alpha tells me the ordinary generating function of the sequence $\{\binom{3n}{n}\}$ is given by $$\sum_{n} \binom{3n}{n} x^n = \frac{2\cos[\frac{1}{3}\sin^{-1}(\frac{3\sqrt{3}\sqrt{x}}{2})]}{\sqrt{4-27x}}$$ How do I prove this?

• Note that for $t\approx 0$ we have $\cos(\sin^{-1}(t))=\sqrt{1-t^2}$. This allows you to simplify the right hand side greatly and cast doubts on the WA result. – Hagen von Eitzen Apr 29 '14 at 16:45
• WA's answers actually has $\cos(\mathbf{1/3}\sin^{-1}(...))$ – Grigory M Apr 29 '14 at 17:02
• Thanks Hagen and Grigory. I made a typo. – user17982 Apr 29 '14 at 17:04
• Now more to the point. Using Lagrange inversion formula one can show that if $y^3-y=x$ then $y=-\sum\binom{3n}n\frac{x^{2n+1}}{2n+1}$. Now apply the trigonometric method to the same equation... – Grigory M Apr 29 '14 at 17:11
• @ColinTan: Since the Lagrange Inversion Formula is useful to answer your question, you could add the tags (lagrange-inversion) and (generating-functions). Regards. – Markus Scheuer May 31 '14 at 10:08

As was already mentioned in the comment section the Lagrange Inversion Formula is a proper method to prove this identity. In the following I use the notation from R. Sprugnolis (etal) paper Lagrange Inversion: when and how.

Let us suppose that a formal power series $w=w(t)$ is implicitely defined by a relation $w=t\Phi(w)$, where $\Phi(t)$ is a formal power series such that $\Phi(0)\ne0$. The Lagrange Inversion Formula (LIF) states that:

$$[t^n]w(t)^k=\frac{k}{n}[t^{n-k}]\Phi(t)^n$$

There are several variations of the LIF stated in the paper. We use in the following $G6$:

Let $F(t)$ be any formal power series and $w=t\Phi(w)$ as before, then the following is valid:

\begin{align*} [t^n]F(t)\Phi(t)^n=\left[\left.\frac{F(w)}{1-t\Phi'(w)}\right|w=t\Phi(w)\right]\tag{1} \end{align*}

Note: The notation $[\left.f(w)\right|w=g(t)]$ is a linearization of $\left.f(w)\right|_{w=g(t)}$ and denotes the substitution of $g(t)$ to every occurrence of $w$ in $f(w)$ (that is, $f(g(t))$). In particular, $w=t\Phi(w)$ is to be solved in $w=w(t)$ and $w$ has to be substituted in the expression on the left of the $|$ sign.

We prove the following identity

\begin{align*} \sum_{n\ge0}\binom{3n}{n}t^n=\frac{2\cos\left[\frac{1}{3}\sin^{-1}\left(\frac{3\sqrt{3}\sqrt{t}}{2}\right)\right]}{\sqrt{4-27t}}\tag{2} \end{align*}



Let $F(t)=1$ and $\Phi(t)=(1+t)^3$.

Since $$t\Phi'(w)=3t(1+w)^2=\frac{3t\Phi(w)}{1+w}=\frac{3w}{1+w}$$ we obtain \begin{align*} \binom{3n}{n}&=[t^n]F(t)\Phi(t)^n=[t^n](1+t)^{3n}\\ &=[t^n]\left[\left.\frac{1}{1-t\Phi'(w)}\right|w=t\Phi(w)\right]=[t^n]\left[\left.\frac{1+w}{1-2w}\right|w=t\Phi(w)\right]\\ \end{align*} Let \begin{align*} A(t):=\sum_{n\ge0}\binom{3n}{n}t^n=\left.\frac{1+w}{1-2w}\right|_{w=t\Phi(w)} \end{align*} Expressing $A(t)=\frac{1+w}{1-2w}$ in terms of $w$, we get $$w=\frac{A(t)-1}{2A(t)+1}$$ Since $w=t\Phi(w)=t(1+w)^3$, we get \begin{align*} \frac{A(t)-1}{2A(t)+1}=t\left(1+\frac{A(t)-1}{2A(t)+1}\right)^3 \end{align*}

which simplifies to:

\begin{align*} (4-27t)A(t)^3-3A(t)-1=0\tag{3} \end{align*}

In order to get the RHS of $(2)$ we first analyse the structure of $(3)$ which is

$$f(t)A(t)^3-3A(t)=1$$

with $f(t)$ linear and observe a similarity of this structure with the identity

$$4\cos^3{t}-3\cos{t}=\cos{3t}$$

We use the Ansatz:

$$A(t) := \frac{2\cos\left(g(t)\right)}{\sqrt{4-27t}}$$

and conclude the identity $(2)$ is valid.
Too long for a comment: By investigating series of the form $S_a(x)=\displaystyle\sum_{n=0}^\infty{an\choose n}~x^n$, we notice that — in general — we get a $($ generalized $)$ hypergeometric function of argument $\dfrac{a^a}{(a-1)^{a-1}}~x$, which then naturally leads us to suspect that we should rather be inspecting the values of the same expression for $x(t)=\dfrac{(a-1)^{a-1}}{a^a}~t$. Taking into consideration the fact that $\displaystyle\lim_{u\to0}u^u=1$, we have
\begin{align} S_{-1}\Big(x(t)\Big)~&=~\frac1{\sqrt{1-t}} \\\\ S_{-1/2}\Big(x(t)\Big)~&=~\frac{\cos\bigg(\dfrac{\arcsin t}3\bigg)+\dfrac1{\sqrt3}~\sin\bigg(\dfrac{\arcsin t}3\bigg)}{\sqrt{1-t^2}} \\\\ S_0\Big(x(t)\Big)~&=~0 \\\\ S_{1/2}\Big(x(t)\Big)~&=~1-i~\frac{t}{\sqrt{1-t^2}} \\\\ S_1\Big(x(t)\Big)~&=~\frac1{1-t} \\\\ S_{3/2}\Big(x(t)\Big)~&=~\frac{\cos\bigg(\dfrac{\arcsin t}3\bigg)+\sqrt3~\sin\bigg(\dfrac{\arcsin t}3\bigg)}{\sqrt{1-t^2}} \\\\ S_2\Big(x(t)\Big)~&=~\frac1{\sqrt{1-t}} \\\\ S_3\Big(x(t)\Big)~&=~\frac{\cos\bigg(\dfrac{\arcsin\sqrt t}3\bigg)}{\sqrt{1-t}} \end{align}