0
$\begingroup$

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$ ?

$\endgroup$
  • $\begingroup$ 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$ ? $\endgroup$ – Hal May 9 '14 at 22:22
2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Careful; your recurrence only holds for $n \geq 1$, so you can only sum the recurrence for $n \geq 1$. $\endgroup$ – André 3000 May 9 '14 at 23:20
  • $\begingroup$ do you mean there is a mistake in indices ? where ? $\endgroup$ – Hal May 9 '14 at 23:53
  • $\begingroup$ 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$. $\endgroup$ – André 3000 May 10 '14 at 13:48
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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) $\endgroup$ – Hal May 9 '14 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.