Help with induction proof for recurrent function

Question

I am having issues with the following inductive proof.

Prove by induction on $n$ that $$ a(n) = n!\bigg(\frac{1}{0!} + \frac{1}{1!} + \cdots + \frac{1}{(n-1)!}\bigg)$$ for all $n \geq 1,$ where $$ a(n)= \begin{cases} n\big(a(n-1)+1\big) & \text{if } n \geq 1; \\[0.1in] 0 & \text{if } n=0. \end{cases} $$

Attempt at Solving

1. Firstly, let's prove the base case $n=0$: this is trivial since $a(0)=0.$

2. Now, an inductive assumption. Assume result holds when $n=N-1$. Let's prove that it holds when $n= N$: \begin{align} a(N) & = N\big(a(N-1)+1\big) \\[0.1in] & = N (N-1)! \bigg(\frac{1}{0!} + \cdots + \frac{1}{(n-2)!} \bigg) \\[0.1in] & = N! \bigg(\frac{1}{0!} + \cdots + \frac{1}{(n-2)!} \bigg). \end{align}

Hmm - I'm stuck; now what? - Is what I have done so far, correct?

Any tips or pointers would be great. Thanks in advance.

Answer 1

It holds for $n=1$.

Assume that it holds for $n=k$, i.e. $$a(k)=k!\left(\frac{1}{0!}+\frac{1}{1!}+\cdots+\frac{1}{(k-1)!}\right).$$ Then, we have

$$\begin{align}a(k+1)&=(k+1)(a(k)+1)\\&=(k+1)\left(k!\left(\frac{1}{0!}+\frac{1}{1!}+\cdots+\frac{1}{(k-1)!}\right)+1\right)\\&=(k+1)!\left(\frac{1}{0!}+\frac{1}{1!}+\cdots+\frac{1}{(k-1)!}\right)+k+1\\&=(k+1)!\left(\frac{1}{0!}+\frac{1}{1!}+\cdots+\frac{1}{(k-1)!}\right)+(k+1)!\cdot\frac{1}{k!}\\&=(k+1)!\left(\frac{1}{0!}+\frac{1}{1!}+\cdots+\frac{1}{(k-1)!}+\frac{1}{k!}\right)\end{align}$$

Hence, it holds for $n=k+1$.

Answer 2

You simply dropped a term:

$$ N \bigg((N-1)! \bigg(\frac{1}{0!} + \cdots + \frac{1}{(n-2)!} \bigg)\ \underbrace{{}+1}\bigg)$$