How to Use Mathematical Induction to Prove Equations?

In summary: Equation! We have an equation, so we can add something on both sides. But this is not always true. We could do it as well on the left only, if there is an "add" on the right. We could not do it for "multiplies on both sides" because there is no "multiplies" on the right, so we cannot apply that rule, and in general we could never do it on the right side, because there are things we don't know yet. So this rule can only be applied in very special cases and we should not try to use it in general, because it is too specific.2) The rule is only valid if we do exactly the same on both sides. If we have
  • #1
FritoTaco
132
23

Homework Statement



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

Homework Equations

The Attempt at a Solution



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

Proof:

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

Basis step:

We want to show [itex]P(1)[/itex] 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

[itex]n\cdot n![/itex]

[itex]= 1\cdot1![/itex]

[itex]= 1\cdot1[/itex]

[itex]= 1[/itex]

RHS

[itex](n+1)!-1[/itex]

[itex]= (1+1)! - 1[/itex]

[itex]= 2! - 1[/itex]

[itex]= 1[/itex]

Both sides are equal.

Induction step:

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

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

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

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

Simplify right side of equation:

[itex]= (k+2)!-1+(k+1)(k+1)![/itex]

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

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

[itex]=[(k+1)!-1]+(k+1)(k+1)![/itex]
we already have [itex]-1[/itex] in the equation so I feel like we just need to manipulate the rest.
I don't know how to condense [itex](k+1)! +(k+1)(k+1)![/itex]
.
.
.
.
[itex]=(k+2)!-1[/itex]
 
Physics news on Phys.org
  • #2
FritoTaco said:
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.
 
  • Like
Likes FritoTaco
  • #3
It's [itex](k+1+1)![/itex] because (just like I did on the left side) I replaced the [itex]k[/itex] in [itex](k+1)![/itex] to be [itex](k+1+ 1)![/itex]. Because of [itex]P(k+1)[/itex] I'm replacing [itex]k[/itex] with [itex]k+1[/itex]. I think that's what you're asking me about?
 
  • #4
FritoTaco said:
It's [itex](k+1+1)![/itex] because (just like I did on the left side) I replaced the [itex]k[/itex] in [itex](k+1)![/itex] to be [itex](k+1+ 1)![/itex]. 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.
 
  • Like
Likes FritoTaco
  • #5
So, what you're telling me is instead of the RHS being [itex]Q(k+1)+p_k[/itex] it should be [itex]Q(k)+p_k[/itex] or how in your original comment left it as [itex](k+1)!-1[/itex]?
 
  • #6
FritoTaco said:
So, what you're telling me is instead of the RHS being [itex]Q(k+1)+p_k[/itex] it should be [itex]Q(k)+p_k[/itex] or how in your original comment left it as [itex](k+1)!-1[/itex]?
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.
FritoTaco said:
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.
 
  • Like
Likes FritoTaco
  • #7
Sorry, I follow what you are writing but I don't understand why I'm not ultimately trying to get [itex][(k+1)!-1]+(k+1)(k+1)![/itex] to equal [itex](k+2)!-1[/itex].

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

Here is my work:

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

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

I simplify RHS of my last equation.

[itex]= (k+2)!-1[/itex]

add [itex](k+1)(k+1)![/itex] to both side of the equation [itex]P(k)[/itex]

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

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

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

Attachments

  • IMG-2088.JPG
    IMG-2088.JPG
    34.7 KB · Views: 252
  • #8
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.
 
  • Like
Likes FritoTaco
  • #9
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?
 
  • #10
FritoTaco said:
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##
 
  • #11
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?
 
  • Like
Likes FritoTaco
  • #12
fresh_42 said:
Separate ##(k+1)!## with the distribution law: ##\ldots = (k+1)! \cdot (\ldots) + \ldots##

does separating give us:

[itex](k+1)!=1+(k+1)[/itex]

I will get back tomorrow if I can.
 
  • #13
FritoTaco said:
does separating give us:

[itex](k+1)!=1+(k+1)[/itex]

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\,.##
 
  • Like
Likes FritoTaco
  • #14
is [itex]a = (k+1)![/itex]

[itex]b = -1[/itex]

[itex]c = (k+1)[/itex]

[itex]d = (k+1)![/itex]
 
  • #15
We have ##P(k+1)= [(k+1)!-1]+(k+1)(k+1)!##, so which factor occurs twice? Take it out and add the rest.
 
  • Like
Likes FritoTaco
  • #16
[itex](k+1)![/itex] factors out

[itex](k+1)![(k+1)+1][/itex]
 
  • #17
FritoTaco said:
[itex](k+1)![/itex] factors out

[itex](k+1)![(k+1)+1][/itex]
Yes! And ##-1## is the leftover.
 
  • Like
Likes FritoTaco
  • #18
So this is the same as [itex](k+2)!-1[/itex]?
 
  • #19
FritoTaco said:
So this is the same as [itex](k+2)!-1[/itex]?
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)! \ ## ?
 
  • Like
Likes FritoTaco
  • #20
SammyS said:
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 [itex](n+1)! = (n+1)·n!.[/itex] but I'm not sure if that's what you do?

https://en.wikipedia.org/wiki/Recursive_definition
 
  • #21
FritoTaco said:
Not exactly. I googled it and it mentioned [itex](n+1)! = (n+1)·n!.[/itex] 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.
 
  • Like
Likes FritoTaco
  • #22
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?
 
  • #23
FritoTaco said:
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.
 
  • Like
Likes FritoTaco
  • #24
Awesome! Thanks for helping me!
 

Related to How to Use Mathematical Induction to Prove Equations?

1. What is mathematical induction?

Mathematical induction is a proof technique used to prove statements about natural numbers or other recursively defined objects. It involves proving a statement for a base case (usually the first natural number) and then showing that if the statement holds for one natural number, it also holds for the next natural number.

2. How does mathematical induction work?

Mathematical induction works by using the principle of mathematical induction, which states that if a statement is true for the first natural number and if it is true for any arbitrary natural number, then it must also be true for the next natural number. This process is repeated until the desired statement is proven to be true for all natural numbers.

3. What is the difference between weak and strong induction?

Weak induction, also known as simple induction, only uses the fact that if a statement is true for one natural number, it is also true for the next natural number. Strong induction, on the other hand, uses the fact that if a statement is true for all natural numbers up to a certain number, it must also be true for the next natural number. Strong induction is a more powerful form of induction and can be used to prove more complex statements.

4. What types of statements can be proven using mathematical induction?

Mathematical induction can be used to prove statements about natural numbers, such as properties of arithmetic operations, divisibility, and sequences. It can also be used to prove statements about recursively defined objects, such as trees or graphs.

5. Are there any limitations to using mathematical induction?

While mathematical induction is a powerful proof technique, it does have some limitations. It can only be used to prove statements about discrete objects, such as natural numbers, and cannot be used for continuous objects, such as real numbers. Additionally, it may not be the most efficient or elegant way to prove certain statements, and other proof techniques may be more suitable.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
539
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
522
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
390
  • Calculus and Beyond Homework Help
Replies
1
Views
298
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
167
  • Calculus and Beyond Homework Help
Replies
8
Views
348
Back
Top