proof of a recursive relation

Question

I am currently reading a paper where they refer to the following recursive relation: For $i \geq 1$, $a_i = \sum_{j=0}^{i-1} \frac{(-1)^j}{j!}$. Then we get $a_1 = 1, a_2 = 0$ and $a_j = \frac{1}{j-1} \sum_{i=1}^{j-2} a_i$ for $j \geq 2$. According to the paper it should be easy to verify. I tried to prove the general result directly and by induction, but in both cases could not prove it. Can someone suggest a method for showing this recursion?

Answer 1

From original recurrence, we prove first that:

$a_{j+1}=\frac{j-1}{j}a_j+\frac{1}{j}a_{j-1}$

Then, we apply this relation as a first step before induction hypothesis:

$a_{j+1}=\frac{j-1}{j}a_j+\frac{1}{j}a_{j-1}=\frac{1}{j}\sum_{i=1}^{j-2}a_i+\frac{1}{j}a_{j-1}=\frac{1}{j}\sum_{i=1}^{j-1}a_i$

which was to be proved.

EDIT: Proof of $a_{j+1}=\frac{j-1}{j}a_j+\frac{1}{j}a_{j-1}$

From the original definition of $a_i$ we have:

$a_{j+1}=a_j+\frac{(-1)^j}{j!}$

$a_{j}=a_{j-1}+\frac{(-1)^{j-1}}{(j-1)!}$

Multiply the first equation with $j$ and write $(-1)^j=-(-1)^{j-1}$. Leave the second equation alone:

$ja_{j+1}=ja_j-\frac{(-1)^{j-1}}{(j-1)!}$

$a_{j}=a_{j-1}+\frac{(-1)^{j-1}}{(j-1)!}$

Now add the two equations.

$ja_{j+1}=(j-1)a_j+a_{j-1}$

Last, divide by $j$ and you get your result.