# Proving an expression with induction

• Nov 23rd 2013, 12:07 AM
nerazzurri10
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

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 :-)

Thank you.
• Nov 23rd 2013, 01:07 AM
romsek
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

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)
• Nov 23rd 2013, 01:14 AM
nerazzurri10
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!
• Nov 23rd 2013, 02:01 AM
romsek
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
• Nov 23rd 2013, 02:05 AM
nerazzurri10
Re: Proving an expression with induction