Proving a Recursion Using Induction

Question

I am trying to prove the following recursion.

$$a(n) = \left\{\begin{matrix} n(a(n-1)+1) & \text{if } n \geq 1\\ 0 & \text{if } n = 0 \end{matrix}\right.$$

is the series definition of $a(n)$. using this, I need to prove that

$$ a(n) = n!\bigg(\frac{1}{0!} + \frac{1}{1!} + \cdots + \frac{1}{(n-1)!}\bigg)$$

for $n \geq 1$ by induction on $n$.

I've found that the $n$ equals, for the first 5 terms, $2,5,16,65,326$. I think now I need to find a formula that describes these terms, and therefore $a(n)$. The problem is, I don't know where to start. Can anyone give me a hand?

Answer 1

Your induction step is: \begin{align} n \cdot a_{n-1} + n & = n(n-1)!\bigg(\frac{1}{0!} + \frac{1}{1!} + \cdots + \frac{1}{(n-1)!}\bigg) + 1 \\ & = n!\bigg(\frac{1}{0!} + \frac{1}{1!} + \cdots + \frac{1}{(n-1)!}\bigg) + n! \cdot \frac{1}{n!} \\ & = n!\bigg(\frac{1}{0!} + \frac{1}{1!} + \cdots + \frac{1}{(n-1)}! + \frac{1}{n!}\bigg) \\ & = a_n \end{align} The base is easy. Then you're done. Read up on how induction works.

Answer 2

For $m\ge1,$

If $a(m)=m!\left(\sum_{r=0^{m-}}\frac1{r!}\right)$

\begin{align} a(m+1) & =(m+1)[a(m)+1] \\[6pt] & =(m+1)[m!\left(\sum_{r=0^{m-}}\frac1{r!}\right)+1] \\[6pt] & =(m+1)!\left(\sum_{r=0^{m-}}\frac1{r!}\right)+m+1 \\[6pt] & =(m+1)!\left(\sum_{r=0^{m-}}\frac1{r!}\right)+\frac{(m+1)!}{m!} \end{align}