1
$\begingroup$

We define a sequence by $a_0=0$ and $$a_n=1+\sum_{k=0}^n a_k a_{n-k}\quad n\ge1$$ Find a non-recursive formula for $a_n$.

Not homework, this is a question from my friend. I tried to use summation by parts $$ \sum_{k=m}^na_kb_k =A_nb_n-A_{m-1}b_m-\sum_{k=m}^{n-1}A_k(b_{k+1}-b_k) $$ But it doesn't make this problem easier. I am wondering if this problem is a special one ($a_0=0$) and then it has a non-recursive formula. Any hints would be highly appreciated!

$\endgroup$
3
  • $\begingroup$ @ClaudeLeibovici Yes, it's $n$. $\endgroup$
    – Chiquita
    Apr 10, 2020 at 10:24
  • $\begingroup$ It doesn't make much difference, since the terms involving $a_n$ are $a_0a_n$ and $a_na_0$, which both are $0$. If you know about generating functions, they will be very useful for this problem $\endgroup$
    – Wojowu
    Apr 10, 2020 at 10:28
  • $\begingroup$ @Wojowu Could you please explain more about it? I know a little about generating functions but I didn't figure out how to use it. Thanks! $\endgroup$
    – Chiquita
    Apr 10, 2020 at 10:33

2 Answers 2

4
$\begingroup$

Here is a sketch of a solution using generating functions. Let $F(x)=\sum_{n=0}^\infty a_nx^n$. We then have $$F(x)^2=\sum_{n=1}^\infty\left(\sum_{k=0}^n a_ka_{n-k}\right)x^n=\sum_{n=1}^\infty(a_n-1)x^n=F(x)-\frac{x}{1-x}.$$ Using the quadratic formula you can now solve for $F(x)$. To get the formula for the coefficients, you may want to use the binomial series.

$\endgroup$
0
3
$\begingroup$

Note we can drop the $k=n$ term because then $a_{n-k}=0$. Your sequence is the binomial transform of the Catalan numbers. It can be described with many formulae, including yours, credited to Cloitre 2004. The closed form is $F(\tfrac12,\,-n;\,2;\;-4)$ in terms of the ordinary hypergeometric function.

$\endgroup$
1
  • 1
    $\begingroup$ Impressive, we have posted out answers on exactly the same second! $\endgroup$
    – Wojowu
    Apr 10, 2020 at 10:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .