# Help with proof by induction, please! I may not be understanding how to work with factorials.

Prove that for all integers $$n \ge 1, 1\cdot1! + 2\cdot2! + 3\cdot3! + \cdots + n\cdot n! = (n+1)! - 1$$.

OK, so I verified base case $$n = 1: 2! - 1 = 1$$

I assumed that for all $$k \ge n, P(k) = (k+1)! - 1$$

I am unsure how to prove true for $$P(k+1)$$, though I understand that the first step is to replace all $$k$$ values with $$k+1$$ which yields $$1\cdot1! + 2\cdot2! + 3\cdot3! + \cdots + k!\cdot k! + (k+1\cdot k+1)! = (k+2)! - 1$$

What next?

• I recommend reading How to write a clear induction proof. – JMoravitz Feb 6 at 19:24
• Welcome to Mathematics Stack Exchange. Note that each term $k\times k!=(k+1)!-k!$ – J. W. Tanner Feb 6 at 19:24
• As for your induction step, begin with just the left side, use a chain of equalities to make it eventually equal your intended right hand side, using your induction hypothesis along the way. $(1\cdot 1!+2\cdot 2!+\dots + k\cdot k!) + (k+1)\cdot (k+1)! = \color{blue}{(k+1)!}-1 + (k+1)\cdot \color{blue}{(k+1)!} = \cdots$ Now, notice that what I colored blue is equal and so may be combined as like terms. – JMoravitz Feb 6 at 19:25

If you are working with proofs by induction, then you have (hopefully) dealt with $$\Sigma$$-notation for making sums more manageable. In my experience, it also makes proofs by induction with sums easier to cobble together and understand (see this answer for one such reason).

Now, at the possible risk of oversimplifying some things, you've got the base case down. You get to assume or make the inductive hypothesis (for $$k\geq1$$) that

$$1\cdot1!+2\cdot2!+\cdots+k\cdot k!=\color{blue}{\sum_{i=1}^k i\cdot i!}=\color{blue}{(k+1)!-1}.\tag{1}$$

Using the base case and the assumption (i.e., inductive hypothesis) stated in $$(1)$$, your goal is to then show that

$$\color{green}{\sum_{i=1}^{k+1}i\cdot i!} = \color{green}{(k+2)!-1}\tag{2}$$

naturally follows. And we can do this in the following manner:

\begin{align} \color{green}{\sum_{i=1}^{k+1}i\cdot i!} &= \color{blue}{\sum_{i=1}^ki\cdot i!} + \underbrace{(k+1)\cdot(k+1)!}_{\substack{\text{evaluate}\\\text{sum at k=i+1}}}\\[1em] &= \underbrace{[\color{blue}{(k+1)!-1}]}_{\substack{\text{use inductive}\\\text{hypothesis from (1)}}} + (k+1)(k+1)!\\[1em] &= (k+1)!-1+(k+1)(k+1)! & \text{(simplify)}\\[1em] &= (k+1)![1+(k+1)]-1 & \text{(rearrange and factor out (k+1)!)}\\[1em] &= (k+1)!(k+2)-1 & \text{(simplify)}\\[1em] &= \color{green}{(k+2)!-1}. & \text{(by definition of factorial)} \end{align} Since we have shown what we set out to show, namely that $$(2)$$ follows from the base case and the assumption of $$(1)$$, we can call it a day. Hope that helps.

Hint: If $$f(n) = 1*1! + 2*2! + ..... + n*n!$$ then $$f(n+1) = 1*1! + 2*2! + ..... + n*n! + (n+1)(n+1)! = f(n) + (n+1)(n+1)!$$.

Hint 2: $$m!(m+1) = (m+1)!$$ and $$m!*m + m! {=\over{\text{factor}}} m!(m+1) = m!(m+1)= m!$$.

So if we assume $$f(k) = 1*1! + 2*2! + ..... + k*k!= (k+1)! - 1$$.

.

Then $$f(k+1) = f(k) + (k+1)(k+1)! =$$

.

$$(k +1)! -1 + (k+1)(k+1)!=(k+1)! + (k+1)(k+1)! - 1 = (k+1)![1+(k+1)]-1=$$

.

$$(k+1)![k+2]-1 = (k+2)!-1$$

You don't really need induction here (or an obvious use of induction) since you have $$(k+1)!=(k+1)\cdot k!= k\cdot k!+k!\iff k\cdot k!= (k+1)!- k!$$ for all $$k$$, so that you obtain a telescoping sum.

• Well, induction is substituted here by the telescoping (they have the same idea) – richrow Feb 6 at 20:08
• @richrow: Behind telescoping, there is indeed induction, but it is so well-known that usually, one doesn't even mention it. – Bernard Feb 6 at 20:35
• Yes, I understand that. Just wanted to say that this another form (maybe clearer) of induction. – richrow Feb 6 at 20:37

Assume $$P(n-1)$$: $$\sum_{k=1}^{n-1}k\cdot k!=n!-1$$ Add $$n\cdot n!$$ to both sides: \begin{align} \sum_{k=1}^nk\cdot k! &=n\cdot n!+n!-1\\ &=(n+1)n!-1\\[9pt] &=(n+1)!-1 \end{align} and we have $$P(n)$$.

After first step which you mentioned,We have

=>1.1!+2.2!+3.3!+.......+n.n!+(n+1)(n+1)!

As a second step,put the value of expression 1.1!+2.2!+3.3!+..........n.n! which is equal to (n+1)!-1 from original equation to step 1. The expression will then become

= (n+1)!-1+(n+1)(n+1)!

=(n+1)!(1+n+1)-1

=(n+1)!(n+2)-1

=(n+2)!-1

=((n+1)+1)!-1

OK, so we're trying to show here that

$$\displaystyle \sum_1^n j\cdot j! = (n + 1)! - 1, \tag 1$$

and we want to use induction to do it. Our OP algebrahman correctly verified the case $$n = 1$$, so we can accept that as a starting point without further ado.

Now if we assume the existence of some $$k$$ such that

$$\displaystyle \sum_1^k j\cdot j! = (k + 1)! - 1, \tag 2$$

we merely need add $$(k + 1) (k + 1)!$$ to each side to obtain

$$\displaystyle \sum_1^{k + 1} j\cdot j! = \sum_1^k j\cdot j! + (k + 1)(k + 1)!$$ $$= (k + 1)! + (k + 1) (k + 1)! - 1 = ((k + 1) + 1) (k + 1)! - 1$$ $$= (k + 2) (k + 1)! - 1 = (k + 2)! - 1, \tag 3$$

and we are done!!!

Note Added in Edit, Thursday 6 February 2020 12:22 PM PST: A few thoughts about our OP's proof attempt: one can't simply replace $$k$$ by $$k + 1$$ and expect the resulting formula to bind; that is in fact what we are trying to prove; rather, one needs to use the ordinary rules of arithmetic and algebra to perform the addition of $$(k + 1)(k + 1)$$ to each side of (2), as was done here. End of Note.

Indeed, if $$n=1$$, this amount consists of a single sum, which is $$1\cdot 1!=1$$ and which coincides with $$(1+1)!-1$$.

If $$n$$ is such a natural number that $$n\geq 1$$ and the induction hypothesis is assumed to be true for $$n$$, that is to say, if $$\sum_{k=1}^n k\cdot k!=(n+1)!-1,$$ then that hypothesis is also true for $$n+1$$, that is to say, $$\sum_{k=1}^{n+1}k\cdot k!=(n+2)!-1,$$ so $$\sum_{k=1}^{n+1}k\cdot k!=\sum_{k=1}^n k\cdot k!+(n+1)\cdot (n+1)!\underbrace{=}_{\text{induction hypothesis}}(n+1)!-1+(n+1)\cdot (n+1)!=(1+n+1)\cdot (n+1)!-1=(n+2)!-1$$ and the test is, by the principle of induction, concluded.