I have an assignment which I am quite stuck on. The question is the following: function f: N to N is defined recursivly:
f(k+1)=(k+1)*f(k) for each k in N. f(0)=1.
That is the factorial function.
Now I have to prove by induction:
1* f (1) + 2 * f (2) + 3* f (3) +....+n * f (n) = f (n +1) -1
I have made two steps: 1. proved that the equation is true for n=1. 2. I assume that the equation is true for n.
Now I have to prove the equation for n+1.
Now the equation is:
1* f (1) + 2 * f (2) + 3* f (3) +....+n * f (n) + (n+1)*f(n+1) = f (n +2) -1
I have used the induction assumption (number 2 in my steps) to place:
f (n +1)-1
insted of:
1* f (1) + 2 * f (2) + 3* f (3) +....+n * f (n)
So now I got:
f(n+1)-1 + (n+1)*f(n+1)=f(n+2)-1
With a common factor of f(n+1) I got:
f(n+1)(n+2)=f(n+2)
Now this is the last step I made.
My question: Can I, from the first definition, say the this final equation is true?
I mean, this is the factorial definition.
I can't PROVE my final step. Please help.
I can't understand why to use $\;f\;$ if we already have a nice, well-known notation for the factorial.
So you have to prove
$$\sum_{k=1}^n kk!=(n+1)!-1$$
So the inductive step is
$$\sum_{k=1}^{n+1}kk!=\sum_{k=1}^nkk!+(n+1)(n+1)!\stackrel{\text{ind. hypothesis}}=(n+1)!-1+(n+1)(n+1)!=$$
$$(n+1)!\left[1+n+1\right]-1=(n+1)!(n+2)-1=(n+2)!-1$$
and we're done.