0

I am to use mathematical induction to prove:

$\sum_{i=1}^n$ $(i \times i!) = (n+1)! - 1$

my base case is n = 1

$RHS: (1 \times1!) = 1$

$LHS: (1+1)! - 1 = 1$

If I am not mistaken the next step is to assume n=k so

$=(k+1)! -1$

then I need to show k+1

$((k+1)+1)-1$ or $(k+2)!-1$

now I'm a bit confused on where to go from here. I THINK my next step is:

$(k+1)!-1 + (k+1 \times k+1!)$

Is this the correct next step? if it is how do I algebraically show that it is equal to $(k+2)!-1$

Any help is appreciated guys! Thanks!

Martin Sleziak
  • 53,687
user126959
  • 21

3 Answers3

0

The next is indeed $$(k+1)!-1+(k+1)(k+1)!=(k+1+1)(k+1)!-1=(k+2)!-1.$$

This remarkable identity can be used to define a factorial basis of the integers.

Tom-Tom
  • 6,867
  • I think I'm just a bit confused on how that works out algebraically . Some of these steps seem like magic to me! Specifically, how did you get (k+1+1)(k+1)! - 1 ? Is it some fundamental rule that I'm lost on? – user126959 Feb 28 '14 at 09:49
  • The LHS is what you obtain adding the next term $i.i!$ with $i=k+1$ to the result assumed by induction ($(k+1)!-1$). Then I use $X+(k+1)X=(k+1+1)X$ with $X=(k+1)!$. – Tom-Tom Feb 28 '14 at 09:52
  • So you replaced $(k+1)!$ with $X$ but how did you go from $X + (k+1)X$ to $(k+1+1)X$? – user126959 Feb 28 '14 at 10:02
  • Because of distributivity : $ab+ac=a(b+c)$. – Tom-Tom Feb 28 '14 at 10:06
  • That makes perfect sense! so from there what happens to that last $(k+1)!$. How does $(h+1+1)X-1$ become $(k+2)!-1$? – user126959 Feb 28 '14 at 10:14
  • Check the definition of the factorial: $n!=1\times2\times\cdots\times n$, so $(k+2)\times(k+1)!=(k+2)!$. – Tom-Tom Feb 28 '14 at 10:34
  • Thanks so much! I think I wouldn't be as lost if I had a stronger foundation. – user126959 Feb 28 '14 at 10:40
0

So let's assume that $$ \sum_{i=1}^k (i\cdot i!)=(k+1)!-1. $$ Then for the $k+1$ case, we have $$ \sum_{i=1}^{k+1}(i\cdot i!)=(k+1)\cdot (k+1)!+\sum_{i=1}^k(i\cdot i!)=(k+1)\cdot (k+1)!+(k+1)!-1. $$ Factoring out $(k+1)!$ from the last term, we have $$ \sum_{i=1}^{k+1}(i\cdot i!)=(k+1)![1+k+1]-1=(k+2)!-1 $$ just like you want.

Ian Coley
  • 6,000
0

You already verified the base case.

If it holds for $n$, let us demonstrate it for $n+1$. We know that: $$ \sum_{i=1}^nii!=(n+1)!-1, $$ and $$ \sum_{i=1}^{n+1}ii!=\sum_{i=1}^nii!+(n+1)(n+1)!. $$ The first term, $\sum_{i=1}^nii!=(n+1)!-1,$ is, for induction assumption, equal to $(n+1)!-1$, thus: $$ \sum_{i=1}^nii!+(n+1)(n+1)!=(n+1)!-1+(n+1)(n+1)!=(n+1)!(1+n+1)-1= $$ $$ =(n+2)!-1, $$ Hence: $$ \sum_{i=1}^{n+1}ii!=(n+2)!-1, $$ q.e.d.

7raiden7
  • 1,794