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

Question

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?

Answer 1

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$

Answer 2

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)$.

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

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.