# Closed form for a strong recurrence relation

Let $\alpha_n$ be a sequence of complex numbers and consider the sequence $b_n$ defined by the (strong) recurrence relation : $$b_{n+1} = \sum_{k=0}^n \alpha_{n-k} b_k$$ with the initial condition $b_0=1$.

Is there a closed form for $b_n$ ?

• I have noticed that the right hand side is a Cauchy product ; introducing generating functionss $A$ and $B$ for the $\alpha_n$ and the $b_n$ I obtain $B(z)=\sum_{n \geq 0} z^n A(z)^n$. Now the remaining combinatorial question is : what is the coefficient of the term of order $n-k$ of $A(z)^k$ ? – Hal May 9 '14 at 22:22

## 2 Answers

OK I got it. Like I said in the comments, consider the generating functions $A$ and $B$ for the $a_n$ and $b_n$. Noticing the right hand side of the recurrence relation is a Cauchy product, we get $\frac{B(z)-B(0)}{z}=A(z) B(z)$ wich gives $$B(z)=b_0 \sum_{n \geq 0} z^n A(z)^n$$

Thus $b_n = \sum_{k=1}^n$ coefficient of the term of order $n-k$ of $A(z)^k$.

This finally gives : $$b_n = \sum_{k=1}^n \sum_{p_1 + \ldots p_k=n-k} a_{p_1} \ldots a_{p_k}$$ which I verified to be correct for the first few terms. Phew!

• Careful; your recurrence only holds for $n \geq 1$, so you can only sum the recurrence for $n \geq 1$. – André 3000 May 9 '14 at 23:20
• do you mean there is a mistake in indices ? where ? – Hal May 9 '14 at 23:53
• I get the same answer as you, so I guess it works out, but as I said, you can really only sum the recurrence over $n \geq 1$ after multiplying by $x^n$. So your LHS should be $b_2 x^2 + b_3 x^3 + \cdots = \frac{B(x) - b_0 - b_1 x}{x}$ and your RHS should be $A(x) B(x) - a_0 b_0$. – André 3000 May 10 '14 at 13:48

Given that $b_{0} =1$ and \begin{align} b_{n+1} = \sum_{k=0}^{n} a_{n-k} b_{k} \end{align} then the first few $b_{n}$ are \begin{align} b_{1} &= a_{0} \\ b_{2} &= a_{1} + a_{0}^{2} \\ b_{3} &= a_{2} + 2 a_{0} a_{1} + a_{0}^{3} \\ b_{4} &= a_{3} + 2 a_{0} a_{2} + 2 a_{1} a_{0}^{2} + a_{1}^{2} + a_{0}^{4}. \end{align} These $b_{n}$ are not able to be put into closed form without knowing what the values of $a_{n}$ are.

• I don't think you understood my question. I asked for a closed form obviously depending on the $a_k$. For example, something like say $b_n = \sum_{k=0}^n a_k \sum_{i+j=k} a_i a_j$ (it's not that, just a random example) – Hal May 9 '14 at 21:17