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.
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
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:
Now this is the last step I made.
Can I, from the first definition, say the this final equation is true?
I mean, this is the factorial definition.
The assignment is that, so that's what I have to prove even if there's not much sense :-)
I can't PROVE my final step. Please help.