A recurrence on how to place brackets invert power series and more...

40 Views Asked by At

Find the explicit form for the recurrence: $$b_{n+1}=\sum_{i = 1}^{n}{a_i b_{n-i+1}}$$ in terms of $a_k ;1 \leq k \leq n,b_0,b_1$

$\textbf{This is a very special recurrence}$............... The case $a_j=b_j$ symbolises the number of ways to put brackets in the expression : $$k_1 \times k_2 \times \cdots \times k_n$$ It also gives the coefficient of the power series defined by : $$F(x)=\sum_{j = 1}^{\infty}{a_j x^j}$$ as, $$\frac{1}{F(x)}=\sum_{j =1}^{\infty}{b_j x^j}$$ It is extreme sophisticated so I am not able to apply any of the methods of characteristic equation etc... Do these kind of recurrence have a special name?

1

There are 1 best solutions below

0
On BEST ANSWER

Hint.

Considering a brute force solution, this can be considered as a linear system. For $n = 4$ we have

$$ \left\{ \begin{array}{rcl} a_1 b_1 & =& b_2 \\ a_2 b_1+a_1 b_2&=&b_3 \\ a_3 b_1+a_2 b_2+a_1 b_3&=&b_4 \\ a_4 b_1+a_3 b_2+a_2 b_3+a_1 b_4&=&b_5 \\ \end{array} \right. $$

giving

$$ \begin{array}{rcl} b_2 & = & a_1 b_1 \\ b_3 & = & \left(a_1^2+a_2\right) b_1 \\ b_4 & = & \left(a_1^3+2 a_2 a_1+a_3\right) b_1 \\ b_5 & = & \left(a_1^4+3 a_2 a_1^2+2 a_3 a_1+a_2^2+a_4\right) b_1 \\ \end{array} $$