Find a formula for summation of a increasing term (formal power series)

Question

I am reading the exercises in the Combinatorics book written by Miklos Bona and trying to solve this exercise of 2.10.

Find an formula for $a_n = \sum_{i=0}^{n-1} (i+1)a_i$ , where $a_0 = 1$

I've already try to assume $A(x)$ (the possible summation of terms $a_n$) to be ordinary or exponential. For both, it will become:

$$A(x) - a_0 = \sum^\infty _{n=1}(\sum^{n-1}_{i=1}(i+1)a_i)x^n$$

The difficult I met is: it's hard to deal with the $(i+1)$, whether for ordinary or exponential power series.

For the ordianry, it may be a product of two series, but I can't find such (maybe I haven't try enough?). For the Exponential, it is also hard to remove $(i+1)$

I also try to compute the right hand side, as a product of two power series.(because it has two summation symbol) But I noticed that the right term doesn't start by $i=0$, even if I change use $j=i-1$ to replace $i$.

I also notice that every $a_n$ maybe the summation of the coefficient of a particular derivatived series, will this help? (such as find the formula of such series?)

If any info is needed to edit, please tell me. (this is my first time ask question on stack exchange)

Answer 1

Hint

Compute the first $a_n$ $(n>0)$ $$\{1,3,12,60,360,2520,20160,181440\}$$ and consider $b_n=\frac {a_n}{n!}$ to produce $$\left\{1,\frac{3}{2},2,\frac{5}{2},3,\frac{7}{2},4,\frac{9}{2},5, \frac{11}{2},6,\frac{13}{2}\right\}$$ which obviously gives $$b_n=\frac {n+1}2 \qquad \implies \qquad a_n=\frac {n+1}2 n!=\frac 12 (n+1)!$$

Answer 2

You can easily produce a recurrence relation by detaching the last term of the sum, as follows : $$ a_n = \sum_{k=0}^{n-1} (k+1)a_k = na_{n-1} + \sum_{k=0}^{n-2} (k+1)a_k = na_{n-1} + a_{n-1} = (n+1)a_{n-1} $$ It is solved by recurrence (no joke), so that $a_n = \frac{(n+1)!}{2}a_1$, where $a_1 = 1$, and you are done.

Remark : $a_1$ plays here the role of the initial condition, instead of $a_0$, because the above recurrence relation is valid for $n > 1$ only, as the sum associated to $a_1$ contains only one term and thus cannot be split. However, since $a_0 = a_1 = 1$, we see that we end up with the same solution Claude Lebovici deduced by inspection.

Answer 3

Thanks to the hint from Claude Lebovici and the initial calculation from Abezhiko, I write an answer here.

First, list several terms of the series. (this is to show the recurrences) By $a_n = \sum^{n-1}_{i=0} (i+1)a_i$, we can write:

$a_0 = 1$

$a_1 = 1a_0$

$a_2 = 1a_0 + 2a_1 = a_1 + 2a_1$

$a_3 = 1a_0 + 2a_1 + 3a_2 = a_2 + 3a_2$

$a_4 = 1a_0 + 2a_1 + 3a_2 + 4a_3 = a_3 + 4a_3$

$\cdots$

$a_n = 1a_0 + 2a_1 + \cdots + na_{n-1} = a_{n-1} + na_{n-1} = (n+1)a_{n-1}$

So, $a_n$ now can be solved using exponential series. (noticed $a_0$ doesn't follow this rule, so we put some restriction)

Start from $n>0$. Assume $A(x) = \sum_{n=1}^{\infty} a_n \frac{x^{n+1}}{(n+1)!}$ Multiply $\frac{x^{n+1}}{(n+1)!}$ to both side, and sum all term till infinity, we got:

$$\sum^{\infty}_{n=1} (a_n * \frac{x^{n+1}}{(n+1)!} )= x * (\sum^{\infty}_{n=1} a_{n-1} * \frac{x^{n}}{(n)!})$$

Apply $A(x)$ to it, we got:

$$A(x) - \frac{x^2}{2!} = x*A(x)$$

Finally, $A(x) = \frac{x^2}{2*(1-x)}$

Now find a formula for $a_n$ in $A(x)$, using some fact of the ordinary power series, we got:

$$a_n * \frac{x^{n+1}}{(n+1)!} = \frac{1}{2} * x^{n+1}$$

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

(Still noticed $n > 0$ here, $a_0 = 1$)