# How can I find the general term of this recursive sequence?

I want to find the general term of the sequence defined by $x_0=1$, $x_1=2$, and $x_n=\binom{2n}{n}-\sum\limits_{i=0}^{n-2}\left(x_i\binom{2n-2-2i}{n-2-i}\right)$. Since I didn't know how to approach this problem I tried by making guesses, and the best one I could find is given by $x_n=\binom{2n}{n}-\frac{2^{n-1}(2^{n-1}-1)}{2}$ which gives the exact same results for $n=1,2,3,4,5$. Although this seems an abstract non-sense, it actually comes from a concrete question on directed graphs. I will add the details of this concrete point of view as soon as I have some time.

• Have you tried entering the first five terms into the online encyclopedia of integer sequences? – Adam Lowrance Dec 27 '17 at 0:03
• Thank you! I wasn't aware of the existence of this encyclopedia! A quick search gave me that $x_n=\frac{\binom{2(n+1)}{n+1}}{n+2}$ which is the $(n+1)$-th Catalan number $C_{n+1}$. The "concrete" problem I was talking about is indeed a variation of the sixth application in combinatorics of the Catalan numbers in the following page en.wikipedia.org/wiki/… – I'm D. Dec 27 '17 at 0:53
• Have you tried mathematical induction? – herb steinberg Dec 27 '17 at 1:11
• I'm trying to prove it by induction, but this means that I have to show the equality $$\frac{\binom{2n+2}{n+1}}{n+2} = \binom{2n}{n}-\sum\limits_{i=0‌​}^{n-2}\left(\binom{‌​2n-2-2i}{n-2-i}\frac{\binom{2i+2}{i+1}}{i+2}\right)$$ It is not clear to me how to deal with this.. – I'm D. Dec 27 '17 at 11:20
• In order to have the last equality It suffices to show that $$\sum\limits_{i=0‌​}^{n-2}\left(\frac{\binom{n}{i+2}\binom{n+1}{i+1}}{\binom{2n}{2i+2}}\right)=\frac{n(n-1)}{n+2}$$ This is a bit simpler, but once again I don't know how to prove it – I'm D. Dec 27 '17 at 14:11

Starting with $x_0=1, x_1=2$ and calculating according to OPs recurrence relation a few more terms, \begin{align*} x_2&=\binom{4}{2}-\binom{2}{0}x_0=6-1=5\\ x_3&=\binom{6}{3}-\binom{4}{1}x_0-\binom{2}{0}x_1=20-4-2=14\\ x_4&=\binom{8}{4}-\binom{6}{2}x_0-\binom{4}{1}x_1-\binom{2}{0}x_2=70-15-8-5=42 \end{align*} we note the sequence $(x_n)_{n\geq 0}=(1,1,2,5,14,42,\ldots)$ starts with Catalan numbers $C_{n+1}$ defined as \begin{align*} C_n=\frac{1}{n+1}\binom{2n}{n}\qquad\qquad n\geq 0 \end{align*}

We stick at this lucky guess and can so considerably simplify the recurrence relation. We now claim that for $n\geq 2$ we have \begin{align*} \color{blue}{C_{n+1}=\binom{2n}{n}-\sum_{i=0}^{n-2}\binom{2n-2-2i}{n-2-i}C_{i+1}}\tag{1} \end{align*}

Before we start proving (1) we do some more simplifications. At first we note that the sum can be written as \begin{align*} \sum_{i=0}^{n-2}\binom{2n-2-2i}{n-2-i}C_{i+1}&=\sum_{i=1}^{n-1}\binom{2n-2i}{n-1-i}C_{i}\\ &=\sum_{i=0}^{n-1}\binom{2n-2i}{n-1-i}C_{i}-\binom{2n}{n-1}\\ \end{align*} Here we shift the index by one to start with $i=1$ and then we add the term with $i=0$ and subtract it as compensation. Putting this into (1) we obtain \begin{align*} C_{n+1}&=\binom{2n}{n}-\sum_{i=0}^{n-1}\binom{2n-2i}{n-1-i}C_{i}+\binom{2n}{n-1}\\ &=\binom{2n+1}{n}-\sum_{i=0}^{n-1}\binom{2n-2i}{n-1-i}C_{i}\tag{2} \end{align*} Noting that $\binom{2n+1}{n}-C_{n+1}=\binom{2n+1}{n}-\frac{1}{n+2}\binom{2n+2}{n+1}=\binom{2n+1}{n-1}$ we are ready to reformulate (2) and claim:

The following is valid for $n\geq 1$ \begin{align*} \color{blue}{\sum_{i=0}^{n-1}\binom{2n-2i}{n-1-i}C_{i}=\binom{2n+1}{n-1}}\tag{3} \end{align*}

We show the binomial identity (3) with the help of generating functions. It is convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a series. This way we can write for instance \begin{align*} [z^k](1+z)^n=\binom{n}{k} \end{align*} We also use the well-known generating function of the Catalan numbers \begin{align*} \sum_{n=0}^\infty C_n z^n&=\frac{1-\sqrt{1-4z}}{2z}\\ &=1+z+2z^2+5z^3+14z^4+42z^5+\cdots \end{align*}

We start with the left-hand side of (3) and obtain \begin{align*} \color{blue}{\sum_{i=0}^{n-1}}&\color{blue}{\binom{2n-2i}{n-1-i}C_i}\\ &=\sum_{i=0}^\infty[z^{n-1-i}](1+z)^{2n-2i}[u^i]\frac{1-\sqrt{1-4u}}{2u}\tag{4}\\ &=[z^{n-1}](1+z)^{2n}\sum_{i=0}^\infty\left(\frac{z}{(1+z)^2}\right)^i[u^i]\frac{1-\sqrt{1-4u}}{2u}\tag{5}\\ &=[z^{n-1}](1+z)^{2n}\frac{1-\sqrt{1-\frac{4z}{(1+z)^2}}}{\frac{2z}{(1+z)^2}}\tag{6}\\ &=[z^{n-1}](1+z)^{2n+1}\tag{7}\\ &\color{blue}{=\binom{2n+1}{n-1}} \end{align*} and the claim follows.

Comment:

• In (4) we apply the coefficient of operator twice. We also set the upper bound of the sum to $\infty$ without changing anything since we are adding zeros only (i.e. $\binom{2n-2i}{n-1-i}=0$ if $i>n-1$).

• In (5) we use the linearity of the coefficient of operator and apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$. We do some rearrangements as preparation for the next step.

• In (6) we apply the substitution rule of the coefficient of operator with $u=\frac{z}{(1+z)^2}$
\begin{align*} A(z)=\sum_{i=0}^\infty a_i z^i=\sum_{i=0}^\infty z^i [u^i]A(u) \end{align*}

• In (7) we do some simplifications.

• In (8) we select the coefficient of $z^{n-1}$.

• @MarkoRiedel: Thanks Marko. :-) – Markus Scheuer Dec 29 '17 at 16:38

Starting from $x_0 = 1$ and $x_1 = 2$ and the recurrence for $n\ge 2$

$$x_n = {2n\choose n} - \sum_{q=0}^{n-2} x_q {2n-2-2q\choose n-2-q}$$

we conjecture that

$$x_n = C_{n+1} = \frac{1}{n+2} {2n+2\choose n+1}.$$

The proof is by induction and the base case holds by inspection. For the induction step we get from the recurrence

$$\sum_{q=0}^{n-2} \frac{1}{q+2} {2q+2\choose q+1} {2n-2-2q\choose n-2-q}.$$

With formal power series we have

$$\sum_{q=0}^{n-2} \frac{1}{q+2} {2q+2\choose q+1} [z^{n-2-q}] (1+z)^{2n-2-2q} \\ = [z^{n-2}] \sum_{q=0}^{n-2} \frac{1}{q+2} {2q+2\choose q+1} z^q (1+z)^{2n-2-2q}.$$

Now we may extend $q$ beyond $n−2$ because there is no contribution from the sum in that case. This yields

$$[z^{n-2}] (1+z)^{2n-2} \sum_{q\ge 0} \frac{1}{q+2} {2q+2\choose q+1} z^q (1+z)^{-2q}.$$

We recall that

$$\sum_{q\ge 0} C_q w^q = \frac{1-\sqrt{1-4w}}{2w}$$

so that

$$\sum_{q\ge 0} C_{q+1} w^q = \frac{1}{w}\left(-1+\frac{1-\sqrt{1-4w}}{2w}\right) = \frac{1-2w-\sqrt{1-4w}}{2w^2}.$$

This yields for our sum

$$[z^{n-2}] (1+z)^{2n-2} \frac{1-2z/(1+z)^2-\sqrt{1-4z/(1+z)^2}}{2z^2/(1+z)^4} \\ = [z^{n-2}] (1+z)^{2n-2} \frac{1+z^2-(1-z)(1+z)}{2z^2/(1+z)^2} = [z^{n-2}] (1+z)^{2n} = {2n\choose n-2}.$$

We have shown that

$$x_n = {2n\choose n} - {2n\choose n+2}.$$

This is

$$x_n = \left(\frac{(n+1)^2}{(2n+2)(2n+1)} - \frac{(n+1)n(n-1)/(n+2)}{(2n+2)(2n+1)}\right) {2n+2\choose n+1} \\ = \frac{1}{2} \left(\frac{n+1}{2n+1} - \frac{n(n-1)/(n+2)}{2n+1}\right) {2n+2\choose n+1} \\ = \frac{1}{2(n+2)} \left(\frac{(n+1)(n+2)}{2n+1} - \frac{n(n-1)}{2n+1}\right) {2n+2\choose n+1} = \frac{1}{n+2} {2n+2\choose n+1}$$

as claimed.

Addendum. We furthermore seek to show that

$$\sum_{q=0}^{n-2} {n\choose q+2} {n+1\choose q+1} {2n\choose 2q+2}^{-1} = \frac{n(n-1)}{n+2}.$$

The LHS is

$$\frac{n! (n+1)!}{(2n)!} \sum_{q=0}^{n-2} \frac{(2q+2)! (2n-2q-2)!}{(q+2)! (q+1)! (n-2-q)! (n-q)!} \\ = \frac{n! (n+1)!}{(2n)!} \sum_{q=0}^{n-2} \frac{1}{q+2} {2q+2\choose q+1} {2n-2q-2\choose n-2-q}.$$

Using the first result (induction step) this simplifies to

$$\frac{n! (n+1)!}{(2n)!} {2n\choose n-2} = \frac{n(n-1)}{n+2}$$

again as claimed.

• I'm sorry but I don't get how you are proving the inductive step. Anyway I think there is a little mistake in the sign of $q$ between the 4th and the 5th equations of your answer, so I don't understand how you managed to find the correct solution starting from that – I'm D. Dec 28 '17 at 9:54
• Can you adapt your proof in order to show me that $$\sum\limits_{i=0‌​}^{n-2}\left(\frac{\binom{n}{i+2}\binom{n+1}{i+1}}{\binom{2n}{2i+2}}\right)=\frac{n(n-1)}{n+2}$$ holds? This is the simplified version of the equality that we want to show, and my problem is still the proof of the inductive step. Maybe if you adapt your proof to this simpler case I will understand it more easily. Thank you for your help! – I'm D. Dec 28 '17 at 9:56
• This uses algebra of binomial coefficients which is added to the above. – Marko Riedel Dec 28 '17 at 22:56
• I think you misunderstood my question.. I wanted to understand the proof of the inductive step regarding the first problem using the proof of the inductive step regarding its simplified version (which is the equation that I wrote in my previous comment). You did the opposite: you explained to me the way to get back from the simpler equation to the more difficult one (which is totally clear to me since I did it on my own), and then you told me to use the inductive step of the difficult problem, which is exactly the one that is not clear to me. – I'm D. Dec 29 '17 at 0:18