# Generating function

$$a_n = \sum\limits_{k=0}^n \frac{1}{k + 1} {{n + k} \choose {n - k}} {{2k} \choose {k}}$$

Does anyone know how to find the generating function of this sequence?

• Mathematica says it is$$\frac{1-x-\sqrt{1-6x+x^2}}{2x}$$ Nov 6, 2017 at 10:50

The Snake Oil Method from Wilf's generatingfunctionology works here. Essentially, we multiply both sides by $x^n$, sum over $n$, then switch the order of summation and shift the (newly) inside index (that's $n$ in this case), noting that $$\sum_{n=0}^{\infty}\sum_{k=0}^{n}=\sum_{(n,k): 0\le k\le n}=\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}.$$
So, letting $C_k=\frac{1}{k+1}\binom{2k}{k}$ and $C(x)=\sum_{k=0}^{\infty}{C_kx^k}=\frac{1-\sqrt{1-4x}}{2x}$, we get $$\begin{split} \sum_{n=0}^{\infty}\sum_{k=0}^{n}{C_k\binom{n+k}{n-k}x^n} &=\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}{C_k\binom{n+k}{n-k}x^n}\\ &=\sum_{k=0}^{\infty}{C_kx^k\left(\sum_{n=k}^{\infty}{\binom{n+k}{n-k}x^{n-k}}\right)}\\ &=\sum_{k=0}^{\infty}{C_kx^k\left(\sum_{n=0}^{\infty}{\binom{n+2k}{n}x^{n}}\right)}\\ &=\sum_{k=0}^{\infty}{C_kx^k\frac{1}{(1-x)^{2k+1}}}\\ &=\frac{1}{1-x}\sum_{k=0}^{\infty}{C_k\left(\frac{x}{(1-x)^2}\right)^k}\\ &=\frac{1}{1-x}C\left(\frac{x}{(1-x)^2}\right). \end{split}$$ The rest is trivial.
Computing the first few terms, $1,2,6,22,90,394,1806$, and searching in the OEIS, leads to the sequence A006318 (large Schroeder numbers) whose entry includes the g.f. (generating function) $(1-x-\sqrt{1-6x+x^2})/(2x)$ as well as some summation formulas. In general, there is no easy way to find g.f.s, sorry. However, there are general methods for special classes of sequences. For example, sequences with linear recurrence relations with constant coefficients have g.f.s which are rational functions and there are methods to find the coefficients of the g.f. we seek to find.
Another special class is sequences whose g.f. is a root of a quadratic polynomial. That is, suppose $\;y:=\sum_{n=0}^\infty a_nx^n\;$ satisfies $\;0=(c_1 x + c_2) y^2 + (c_3 x + c_4) y + (c_5 x + c_6).$ Using the first few terms, $\;y=1+2x+6x^2+22x^3+90x^4+O(x^5),\;$ we can solve for the unknown constants and find $\;0=xy^2+1+(x-1)y+1,\;$ and solving the quadratic for $\;y,\;$ gives the g.f. we seek. Of course, this does not prove that we have the correct g.f., but we can check if they agree to as many terms as we want. An actual rigorous proof would require using some other methods.
• In general, I agree, but this is not the general case. Both $\sum_{k=0}^{n}\binom{2n-k}{k}x^k$ and $\sum_{k\geq 0}\frac{1}{k+1}\binom{2k}{k}x^k$ are well known and the given sequence is associated with the coefficient of $x^n$ in their product. Nov 6, 2017 at 14:33
• @JackD'Aurizio Well this amounts to finding certain Hadamard product then, which is in general not easy. There is a method with residues, though. Btw, you probably mean $\binom{n+k}{2k}$ rather than $\binom{2n-k}k$? Nov 7, 2017 at 4:41
• No, I meant exactly $\binom{2n-k}{k}$, allowing to write your sum as a convolution. Nov 7, 2017 at 13:43