How to Use Mathematical Induction to Prove Equations?

[FritoTaco]

Homework Statement

Prove that 1\cdot1!+2\cdot2!+...+n\cdot n! = (n+1)!-1 whenever n is a positive integer.

Homework Equations

The Attempt at a Solution

I'm having trouble simplifying towards the end of the proof.

Proof:

Let P(n) be the statement 1\cdot1!+2\cdot2!+...+n\cdot n! = (n+1)!-1

Basis step:

We want to show P(1) is true, where n = 1. Show both sides of the equation to be true (i.e. Left-hand side and right-hand side equal to each other)

LHS

n\cdot n!

= 1\cdot1!

= 1\cdot1

= 1

RHS

(n+1)!-1

= (1+1)! - 1

= 2! - 1

= 1

Both sides are equal.

Induction step:

For the inductive hypothesis, assume P(k) is true for some k\geq1; then show P(k+1) is true.

assume P(k): 1\cdot1!+2\cdot2!+...+k\cdot k! = (k+1)!-1 (we replaced n with k from original equation)

show P(k+1): (1\cdot1!+2\cdot2!+...+k\cdot k!) + (k+1)(k+1)! = (k+1+1)!-1 + (k+1)(k+1)!

on the left side on the equation, we kept k\cdot k! but also added and replaced the k in k\cdot k! with k+1
on the right side of the equation we added (k+1)(k+1)! that was also on the left side (so we essentially added (k+1)(k+1)! on both sides of the equation.

Simplify right side of equation:

= (k+2)!-1+(k+1)(k+1)!

We want the right-hand side of P(k) which is (k+1)!-1 to look like (k+2)!-1.

Okay, so this is where I'm having trouble getting the equation (which is P(k): (k+1)! -1) to look like my P(k+1) which is (k+2)!-1.

=[(k+1)!-1]+(k+1)(k+1)!
we already have -1 in the equation so I feel like we just need to manipulate the rest.
I don't know how to condense (k+1)! +(k+1)(k+1)!
.
.
.
.
=(k+2)!-1

 

[fresh_42]

show $P(k+1):(1⋅1!+2⋅2!+...+k⋅k!)+(k+1)(k+1)!=(k+1+1)!−1+(k+1)(k+1)!$

I don't get this. We have $$\underbrace{\underbrace{(1⋅1!+2⋅2!+...+k⋅k!)}_{P(k)} +(k+1)(k+1)!}_{P(k+1)} = \underbrace{(k+1)! - 1}_{hyp.}+ (k+1)(k+1)!$$
which is not what you wrote.

 

[FritoTaco]

It's (k+1+1)! because (just like I did on the left side) I replaced the k in (k+1)! to be (k+1+ 1)!. Because of P(k+1) I'm replacing k with k+1. I think that's what you're asking me about?

 

[fresh_42]

It's (k+1+1)! because (just like I did on the left side) I replaced the k in (k+1)! to be (k+1+ 1)!. I think that's what you're asking me about?

No. That is what you want to get at. However, you wrote something else.

Say the RHS is $Q(n)$ and the new element $p_n$. Then the statement reads $P(n)=Q(n)$. The goal is to get $P(k+1)=P(k)+p_k=Q(k)+p_k=\ldots \ldots = Q(k+1)$.

What you wrote was $P(k)+p_k=Q(k+1)+p_k$ which is neither what has to be shown, nor is it correct at all.

 

[FritoTaco]

So, what you're telling me is instead of the RHS being Q(k+1)+p_k it should be Q(k)+p_k or how in your original comment left it as (k+1)!-1?

 

[fresh_42]

So, what you're telling me is instead of the RHS being Q(k+1)+p_k it should be Q(k)+p_k or how in your original comment left it as (k+1)!-1?

I should have defined my abbreviations, sorry.

$P(k)=1!1+\ldots +k!k \; , \; p_k=k!k\; , \;Q(k)=(k+1)!-1\,$
Then the statement reads $P(k)=Q(k)$ and by definition we have $P(k+1)=P(k)+p_{k+1}\,.$

Your induction basis was correct, although a bit complicated. Shorter would have been: $P(1)=1!1=1$ and $Q(1)=(1+1)!-1=2!-1=2-1=1$.
Now what is the induction hypothesis? You said $P(k)=Q(k)$ which is correct.
The induction step is now to prove $P(k+1)= Q(k+1)$.

Therefore we start with $P(k+1)$ which is by definition equal to $P(k)+p_{k+1}$ and hope we will end up with $Q(k+1)$, the statement for the next step. This means we have $P(k+1)=P(k)+p_{k+1}= 1!1+\ldots +k!k + (k+1)!(k+1)= (\text{ind. hyp.}) = Q(k)+(k+1)!(k+1) = ((k+1)!-1)+(k+1)!(k+1) = \ldots ?$
The question mark will hopefully be $Q(k+1)$ at the end.

You had simply one $"+1"$ too many in your RHS (red version), resp. one summand too many (blue version), depending what you wanted to say.

show P(k+1): (1! 1+2! 2+...+k! k) + (k+1)!(k+1) = (k+1+1)!-1 + (k+1)(k+1)!

But both together is wrong.

 

[FritoTaco]

Sorry, I follow what you are writing but I don't understand why I'm not ultimately trying to get [(k+1)!-1]+(k+1)(k+1)! to equal (k+2)!-1.

I was following my example in my book which you can see in a screenshot i attached.

Here is my work:

P(k): 1\cdot1!+2\cdot2!+..+k\cdot k! = (k+1)!-1

P(k+1): (1\cdot1!+2\cdot2!+..+k\cdot k!)+(k+1)(k+1)! = [(k+1)+1]!-1

I simplify RHS of my last equation.

= (k+2)!-1

add (k+1)(k+1)! to both side of the equation P(k)

(1\cdot1!+2\cdot2!+..+k\cdot k!)+(k+1)(k+1)! = Induct. Hyp. = [(k+1)!-1]+(k+1)(k+1)!

So I wanted my RHS which is [(k+1)!-1]+(k+1)(k+1)! to look like (k+2)!-1

= [(k+1)!-1]+(k+1)(k+1)!
.
.
.
= (k+2)!-1

 

[fresh_42]

So? You have to fill the dots from $[(k+1)!-1]+(k+1)(k+1)! = \stackrel{to}{\ldots} = (k+2)!-1$
________
This "add to both sides" is not a good idea to look at it. It is correct in your last post, but led to the error in the first place. And it does not really reflect what's going on. What happens is:

Given a statement $P(n)=Q(n)$.
Maybe it's wrong, so let's see whether $P(1)=Q(1)$ is correct.
Next we pretend that we have checked $P(2)=Q(2)\; , \;P(3)=Q(3)\; , \;P(4)=Q(4)$ as well. Now this won't get us very far, since we will never know, whether it is correct for all numbers $n$. So the trick out of this misery is the following:

Let us assume we did indeed check all numbers up to $P(k)=Q(k)$. What we want to show is, that given this knowledge, can we prove $P(k+1)=Q(k+1)\,?$ If so, then we are done, because we know the case $n=1$ is true, and now we have proven that the next step is also true, i.e. $P(2)=Q(2)$ - by proof, not by calculation. From here we can go on and on and have it for all numbers, simply because we know how to get to the next one, if the previous were all correct.

So we have to prove: $P(k+1) = Q(k+1)$. Now what we are allowed to use for a proof? Basic algebra of course, and all we checked by hand, e.g. $P(1)=Q(1)$. However, we are also allowed to use $P(k)=Q(k)$ because we assume this to hold. We pretend to have checked it.

In our case this means we have to show $P(k+1) = \ldots = Q(k+1)$ and our $P(k+1)$ is defined as being $P(k+1)=P(k)+(k+1)(k+1)!$ Thus we only add something on the left, and we only do this in this special case, as we have an addition. It could as well be a multiplication or any other rule. We do not really add it on the right. We must show that we end up at $Q(k+1)=(k+2)!-1$ - no extra summand.

This in my opinion more than confusing "add on both sides" is actually many things in one:
1) It is only "add" because we have an addition in this case.
2) To write $P(k)+ (k+1)!(k+1) = (k+1)!-1 + (k+1)!(k+1)$ is two steps in one: the definition of $P(k+1)$ and the substitution given by the induction hypothesis. 3) There is not really a right hand side involved here. It is actually only the left hand side after some algebraic steps. The original right hand side, namely $Q(k+1)=(k+2)!-1$ is still untouched. It is the target of our manipulations, i.e. what we want to get at.

 

[FritoTaco]

Yeah, in my first post I did two steps in one without explaining that part. But, you mention to fill the dots part, that's where I'm stuck. I don't know where to go from there?

 

[fresh_42]

Yeah, in my first post I did two steps in one without explaining that part. But, you mention to fill the dots part, that's where I'm stuck. I don't know where to go from there?

Separate $(k+1)!$ with the distribution law: $\ldots = (k+1)! \cdot (\ldots) + \ldots$

 

[fresh_42]

If you want to have a puzzle about induction, look at: $2^n+7^n+8^n+18^n+19^n+24^n=3^n+4^n+12^n+14^n+22^n+23^n$ for all $n\geq 0$

Is the induction basis true? If so, for more than $n=0$?
Can it be true at all? Why or why not?

 

[FritoTaco]

Separate $(k+1)!$ with the distribution law: $\ldots = (k+1)! \cdot (\ldots) + \ldots$

does separating give us:

(k+1)!=1+(k+1)

I will get back tomorrow if I can.

 

[fresh_42]

does separating give us:

(k+1)!=1+(k+1)

I will get back tomorrow if I can.

No. Write your formula with $c:=k+1$ so you might see it better. We have $a \cdot c + b\cdot c +d$. Just write this as $c\cdot (a+b)+d\,.$

 

[FritoTaco]

is a = (k+1)!

b = -1

c = (k+1)

d = (k+1)!

 

[fresh_42]

We have $P(k+1)= [(k+1)!-1]+(k+1)(k+1)!$, so which factor occurs twice? Take it out and add the rest.

 

[FritoTaco]

(k+1)! factors out

(k+1)![(k+1)+1]

 

[fresh_42]

(k+1)! factors out

(k+1)![(k+1)+1]

Yes! And $-1$ is the leftover.

 

[FritoTaco]

So this is the same as (k+2)!-1?

 

[SammyS]

So this is the same as (k+2)!-1?

What is the "this" you refer to?

Do you understand how it is that $\ (k+1)!\,\left[(k+1)+1 \right] \$ is equal to $\ (k+2)! \$ ?

 

[FritoTaco]

Do you understand how it is that (k+1)![(k+1)+1] (k+1)![(k+1)+1] \ (k+1)!\,\left[(k+1)+1 \right] \ is equal to (k+2)! (k+2)! \ (k+2)! \ ?

Not exactly. I googled it and it mentioned (n+1)! = (n+1)·n!. but I'm not sure if that's what you do?

https://en.wikipedia.org/wiki/Recursive_definition

 

[fresh_42]

Not exactly. I googled it and it mentioned (n+1)! = (n+1)·n!. but I'm not sure if that's what you do?

https://en.wikipedia.org/wiki/Recursive_definition

That is the definition of faculty: $(n+1)!=1\cdot 2\cdot 3\cdot \ldots \cdot (n-1)\cdot n \cdot (n+1) = n! \cdot (n+1)$.
In our case, we have
$$
P(k+1)=\underbrace{[(k+1)!-1]+(k+1)(k+1)!}_{\text{your post #7}} = \underbrace{(k+1)![(k+1)+1] -1}_{\text{your post #16}}= (k+1)![k+(1+1)]-1= \underbrace{(k+1)![k+2]-1= 1\cdot 2\cdot \ldots \cdot k \cdot (k+1) \cdot (k+2)-1}_{\text{your post #20}} = \underbrace{(k+2)!}_{\text{def.}}-1=Q(k+1)
$$
It's all there - only a bit spread over the discussion.

 

[FritoTaco]

I’m at school, so I can’t write latex. But I see, the (k+1) is just a precedent of (k+2)! So you can leave it as that. I think that’s what you’re saying?

 

[fresh_42]

I’m at school, so I can’t write latex. But I see, the (k+1) is just a precedent of (k+2)! So you can leave it as that. I think that’s what you’re saying?

Yes. The induction hypothesis took place in the first equality sign, the rest is only algebra and the definition of $n!$. Together it resulted in $P(k+1)=Q(k+1)$ which was what we wanted to show.

 

[FritoTaco]

Awesome! Thanks for helping me!