Finding a formula for $1+\sum_{j=1}^n(j!)\cdot j$ using induction

Question

I need help with finding the formula and proving it by induction. Am stuck, but the professor says we should know this by now.

Find the formula for $1 + \sum \limits _{j=1} ^n j! j$, and show work proving the formula is correct using induction.

Answer 1

Hint: Let $f(n) = 1 + \displaystyle\sum_{j = 1}^{n}j \cdot j!$. Then, we have $f(0) = 1$ and:

$f(n+1)-f(n) = \left[1 + \displaystyle\sum_{j = 1}^{n+1}j \cdot j!\right] - \left[1 + \displaystyle\sum_{j = 1}^{n}j \cdot j!\right] = (n+1) \cdot (n+1)!$

$= (n+2) \cdot (n+1)! - 1 \cdot (n+1)! = (n+2)! - (n+1)!$.

Can you think of a function which satisfies $f(n+1)-f(n) = (n+2)!-(n+1)!$ and $f(0) = 1$?

After coming up with the formula, proving it by induction is straightforward.

Answer 2

In terms of strategies to find a formula, if you have no idea your best bet might to start computing. Let's compute the first few sums...

$$1 + 1!1=2$$

$$1+1!1+2!2 = 2+2!2=2(1+2!)=2\cdot 3$$

$$1+1!1+2!2+3!3= 6+3!3=2\cdot 3 \cdot (1+3)=2\cdot 3 \cdot 4$$

$$1+1!1+2!2+3!3+4!4 = 24+4!4=2\cdot 3 \cdot 4 (1+4)= 2\cdot 3 \cdot 4 \cdot 5$$

$$\vdots $$

Do you start to see a pattern?

Answer 3

To find the formula, note that $j! j = j! (j+1 - 1) = (j+1)! - j!$, therefore your sum is

$$1 + \sum \limits _{j=1} ^n \big( (j+1)! - j! \big) = 1 + \sum \limits _{j=1} ^n (j+1)! - 1 - \sum \limits _{j=1} ^n j! = \sum \limits _{j=2} ^{n+1} j! - \sum \limits _{j=1} ^n j! = (n+1)! - 1 .$$

Checking this by induction is a piece of cake, now, but most importantly note that the above is a proof already, making verification through induction redundant.