Proving an expression with induction

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

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.

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.

Thank you.

Re: Proving an expression with induction

Quote:

Originally Posted by

**nerazzurri10** 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

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

This is where you've made your mistake. Don't set the left hand side equal to f(n+2)-1. You want to show that it is equal.

so you would say f(n+1)-1 + (n+1)f(n+1) = (n+2)f(n+1) - 1 = f(n+2) - 1, the last bit by the definition of f(n+2)

Re: Proving an expression with induction

So you're saying that I should go on with:

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

And prove that equation?

Thank you!

Re: Proving an expression with induction

Quote:

Originally Posted by

**nerazzurri10** So you're saying that I should go on with:

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

And prove that equation?

Thank you!

yes, just note that (n+2)f(n+1) = f(n+2) by the definition of f

Re: Proving an expression with induction

Thank you. Followed your advice.