Mathematical Induction - Help for a Beginner?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 2:13 pm UTC

In an attempt to keep my mind active, I'm trying to re-learn many of the concepts that I have forgotten or never truly grasped in the first instance. I'm working my way through a discrete mathematics book and I'm having trouble with the concept of mathematical induction. All of the examples are difficult for me. Here's one:

Prove that P(n): 1 + 2 + 3 + . . . n = n(n+1)/2

The steps for solving this are illustrated in the book, but I just can't follow them. Can anyone help?

Nicias
Posts: 168
Joined: Tue Aug 13, 2013 4:22 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Nicias » Fri Jan 02, 2015 3:26 pm UTC

It might help to think about how you would check this by hand, if you had to make a chart.

One would probably check 1+2+3+4=10=4(4+1)/2 by looking at it.

Likewise 1+2+3+4+5=15=5(5+1)/2 might be doable by looking.

Most people would have to get clever if they wanted to do 1+2+3+4+5+6=21=6(6+1)/2 in their head.

If you were now going to find 1+2+3+4+5+6+7, would you start from scratch? Or would you use the result of the previous step?

So, 1+2+3+4+5+6+7=(1+2+3+4+5+6)+7=21+7=28=7(7+1)/2.

At that last step you used the fact that the formula worked for 6 to show that it works for 7.

Now, do the same abstractly. Replace 6 with "k". Then you can show that if the formula works for n=k, it works for n=k+1.

This is the hard part for most people.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 3:38 pm UTC

Nicias wrote:
At that last step you used the fact that the formula worked for 6 to show that it works for 7.

Now, do the same abstractly. Replace 6 with "k". Then you can show that if the formula works for n=k, it works for n=k+1.

This is the hard part for most people.


That is the trouble I'm having - when I try to abstract it away, I don't know what I'm doing and get lost. Also, the whole process seems circular.

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Nyktos » Fri Jan 02, 2015 3:47 pm UTC

The basic idea of induction is: if it's true for some number n, does that mean it's true for n + 1?

If you know (for some unspecified particular n) that 1 + ... + n = n(n + 1)/2, what can you say about 1 + ... + (n + 1)?

If you can prove that, and you can prove the case for n = 0 directly, you've proven it holds for all natural numbers.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 3:48 pm UTC

Nyktos wrote:The basic idea of induction is: if it's true for some number n, does that mean it's true for n + 1?

If you know (for some unspecified particular n) that 1 + ... + n = n(n + 1)/2, what can you say about 1 + ... + (n + 1)?

If you can prove that, and you can prove the case for n = 0 directly, you've proven it holds for all natural numbers.


That is clear. Thank you.

How can I get better at the inductive part? That is, how do I figure out how to do the abstraction?



I should also point out that I don't understand how to manipulate the symbols to arrive at the solution. The text I'm working from has the following solution:

1 + 2 + 3 + . . . + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2

Can anyone help me figure out what happened above?

User avatar
mosgi
Posts: 46
Joined: Thu Jul 17, 2014 8:19 pm UTC
Location: Somewhere in your past light cone

Re: Mathematical Induction - Help for a Beginner?

Postby mosgi » Fri Jan 02, 2015 4:56 pm UTC

MathDoofus wrote:I should also point out that I don't understand how to manipulate the symbols to arrive at the solution. The text I'm working from has the following solution:

1 + 2 + 3 + . . . + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2

Can anyone help me figure out what happened above?

Does it help to have a few more steps/words?

We're inducting, so we want to show that if 1 + 2 + 3 + ... + k = k(k+1)/2, then 1 + 2 + 3 + ... + (k+1) = (k+1)(k+2)/2.
Another way to think of it is this: Imagine we've been given some specific value of k, and we've been told that we're allowed to assume that, for that value of k, 1 + 2 + 3 + ... + k = k(k+1)/2. Based on that, we want to prove that 1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2.

So, how can we make use of what we know? Well, first, we can regroup: 1 + 2 + 3 + ... + k + (k+1) = (1 + 2 + 3 + ... + k) + (k+1).
Then look at the first bracket on the right-hand side. We've been told that (the stuff in that bracket) equals (some other stuff). So let's substitute it.
That gives us 1 + 2 + 3 + ... + k + (k+1) = (k(k+1)/2) + (k+1).
The last few steps are "just" algebraic manipulations - that's just to make sure that what we have actually equals (k+1)(k+2)/2, like we wanted it to.
(they pronouns please)

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 5:00 pm UTC

mosgi wrote:Does it help to have a few more steps/words?

We're inducting, so we want to show that if 1 + 2 + 3 + ... + k = k(k+1)/2, then 1 + 2 + 3 + ... + (k+1) = (k+1)(k+2)/2.
Another way to think of it is this: Imagine we've been given some specific value of k, and we've been told that we're allowed to assume that, for that value of k, 1 + 2 + 3 + ... + k = k(k+1)/2. Based on that, we want to prove that 1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2.

So, how can we make use of what we know? Well, first, we can regroup: 1 + 2 + 3 + ... + k + (k+1) = (1 + 2 + 3 + ... + k) + (k+1).
Then look at the first bracket on the right-hand side. We've been told that (the stuff in that bracket) equals (some other stuff). So let's substitute it.
That gives us 1 + 2 + 3 + ... + k + (k+1) = (k(k+1)/2) + (k+1).
The last few steps are "just" algebraic manipulations - that's just to make sure that what we have actually equals (k+1)(k+2)/2, like we wanted it to.


Thanks for your response. Unfortunately, I'm even more confused. I don't understand the substitution or the regrouping. And how does the stuff on the left-hand side of the equals sign get turned it into the stuff on the right-hand side?

User avatar
Flumble
Yes Man
Posts: 2248
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Flumble » Fri Jan 02, 2015 6:22 pm UTC

MathDoofus wrote:How can I get better at the inductive part? That is, how do I figure out how to do the abstraction?

That's a tough one. IMHO, it's a matter of time —give it some thought over the months and eventually you'll simply "get it".
In this case, it's quite simple: every term adds one new number, so you can take the assumed formula for k and add the difference and equate it to the assumed formula for k+1.
It's even easier (and slightly cyclic) to prove fn(0)=n by induction, with f(x)=x+1.
Do you have more examples of proofs by induction?

MathDoofus wrote:1 + 2 + 3 + . . . + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2

Can anyone help me figure out what happened above?

What happened over there is that the author is trying to prove the next term, let's call it m=k+1, which has the equation 1+2+3+...+k+m = m(m+1)/2 by grouping 1+2+3+...+k together. You can group 1+2+3+...+k together, because we know that 1+2+3+...+k = k(k+1)/2.
So the left side becomes k(k+1)/2+m, which is k(k+1)/2+(k+1) if you replace m again, and with some manipulation (k+1)*k/2+(k+1) = (k+1)*(k/2+1) = (k+1)*(k+2)/2 = m(m+1)/2.
Last edited by Flumble on Fri Jan 02, 2015 6:23 pm UTC, edited 1 time in total.

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 6:22 pm UTC

MathDoofus wrote:
mosgi wrote:Does it help to have a few more steps/words?

We're inducting, so we want to show that if 1 + 2 + 3 + ... + k = k(k+1)/2, then 1 + 2 + 3 + ... + (k+1) = (k+1)(k+2)/2.
Another way to think of it is this: Imagine we've been given some specific value of k, and we've been told that we're allowed to assume that, for that value of k, 1 + 2 + 3 + ... + k = k(k+1)/2. Based on that, we want to prove that 1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2.

So, how can we make use of what we know? Well, first, we can regroup: 1 + 2 + 3 + ... + k + (k+1) = (1 + 2 + 3 + ... + k) + (k+1).
Then look at the first bracket on the right-hand side. We've been told that (the stuff in that bracket) equals (some other stuff). So let's substitute it.
That gives us 1 + 2 + 3 + ... + k + (k+1) = (k(k+1)/2) + (k+1).
The last few steps are "just" algebraic manipulations - that's just to make sure that what we have actually equals (k+1)(k+2)/2, like we wanted it to.


Thanks for your response. Unfortunately, I'm even more confused. I don't understand the substitution or the regrouping. And how does the stuff on the left-hand side of the equals sign get turned it into the stuff on the right-hand side?


I'll just rewrite mosgi's argument with less words so you can maybe stare at the equations more easily so you can think about them more.
Make sure to pay careful attention to when we have k on the left hand side and when we ALSO have k+1 on the left hand side.

What we want to show:
1 + 2 + 3 + ... + (k+1) = ((k+1)(k+2))/2

What we get to start with:
1 + 2 + 3 + ... + k = k(k+1)/2

Step 1: write down
1 + 2 + 3 + ... + k + (k+1)

Step 2: add in some parenthesis (regroup):
1 + 2 + 3 + ... + k + (k+1) = (1 + 2 + 3 + ... + k) + (k+1)

Step 3: Remember what we got to start with and plug that into Step 2
k(k+1)/2 + (k+1)

Step 4: algebra:
k(k+1)/2 + (k+1) = (k+1)(k/2+1) = (k+1)(k+2)(1/2) = ((k+1)(k+2))/2

(first equality if factoring out (k+1) from both terms.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 6:30 pm UTC

Twistar wrote:
I'll just rewrite mosgi's argument with less words so you can maybe stare at the equations more easily so you can think about them more.
Make sure to pay careful attention to when we have k on the left hand side and when we ALSO have k+1 on the left hand side.

What we want to show:
1 + 2 + 3 + ... + (k+1) = ((k+1)(k+2))/2

What we get to start with:
1 + 2 + 3 + ... + k = k(k+1)/2

Step 1: write down
1 + 2 + 3 + ... + k + (k+1)

Step 2: add in some parenthesis (regroup):
1 + 2 + 3 + ... + k + (k+1) = (1 + 2 + 3 + ... + k) + (k+1)

Step 3: Remember what we got to start with and plug that into Step 2
k(k+1)/2 + (k+1)

Step 4: algebra:
k(k+1)/2 + (k+1) = (k+1)(k/2+1) = (k+1)(k+2)(1/2) = ((k+1)(k+2))/2

(first equality if factoring out (k+1) from both terms.


Here are the parts that I don't understand.

First, why are we allowed to use our assumption as part of the proof? In other words, why are we replacing (1 + 2 + 3 + . . . k) with [(k + 1)(k + 2)]/2?

Second, when [(k + 1)(k +2)]/2 is plugged into the left-hand side, how does it interact with the existing (k + 1) on that side? I don't know much algebra.

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 6:55 pm UTC

MathDoofus wrote:
Twistar wrote:
I'll just rewrite mosgi's argument with less words so you can maybe stare at the equations more easily so you can think about them more.
Make sure to pay careful attention to when we have k on the left hand side and when we ALSO have k+1 on the left hand side.

What we want to show:
1 + 2 + 3 + ... + (k+1) = ((k+1)(k+2))/2

What we get to start with:
1 + 2 + 3 + ... + k = k(k+1)/2

Step 1: write down
1 + 2 + 3 + ... + k + (k+1)

Step 2: add in some parenthesis (regroup):
1 + 2 + 3 + ... + k + (k+1) = (1 + 2 + 3 + ... + k) + (k+1)

Step 3: Remember what we got to start with and plug that into Step 2
k(k+1)/2 + (k+1)

Step 4: algebra:
k(k+1)/2 + (k+1) = (k+1)(k/2+1) = (k+1)(k+2)(1/2) = ((k+1)(k+2))/2

(first equality if factoring out (k+1) from both terms.


Here are the parts that I don't understand.

First, why are we allowed to use our assumption as part of the proof? In other words, why are we replacing (1 + 2 + 3 + . . . k) with [(k + 1)(k + 2)]/2?

Second, when [(k + 1)(k +2)]/2 is plugged into the left-hand side, how does it interact with the existing (k + 1) on that side? I don't know much algebra.


I'll address your second question first since it's quicker. We are doing a simple substitution. Say we have this formula:
x + 6 = y
But then I tell you that x = 7. Now we can plug x = 7 into the first equation and get:
7 + 6 = y
My teachers always called this "plug and chug"
In this case, we are doing a more complicated substitution. We are substituting (1 + 2 + 3 + ... + k) with k(k+1)/2. So to answer your question of how the k(k+1)/2 interacts with the existing (k+1) here is what happens. Since the (1 + 2 + 3 + ... + k) was simply ADDED to the existing (k+1), when we replace it with k(k+1)/2 then the k(k+1)/2 is also simply ADDED to the existing (k+1). You can see this as I've written it in Step 3.

As for your first question of why we are allowed to use the assumption as part of the proof, that gets to the heart of how induction works. Here is the analogy I always heard. Induction is like climbing a ladder. Imagine we have a ladder and we want to know if we can climb it. There are two things we need to know
1) Can we get on the ladder at all? This is equation to checking the base case of the n=1 case.

2) If we are on the ladder on any given rung, are we able to get from whatever rung we are on to the next rung. Can we go from n to n+1?

the second part is the induction step. We are just checking that if we are on rung n can we get to rung n+1. If this is true for any possible value of n, then that means that (as long as we can get on the ladder) we can climb as high as we want because we just go from n to n+1, then n+1 to n+2, etc.

Does this help make a little more sense? It is very abstract at first and does feel very circular but it actually isn't circular and it is very clever. However, if you forget to check the base case then the argument IS circular and is invalid so you need to make sure you check that.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 7:11 pm UTC

Twistar wrote:
MathDoofus wrote:
Twistar wrote:
I'll just rewrite mosgi's argument with less words so you can maybe stare at the equations more easily so you can think about them more.
Make sure to pay careful attention to when we have k on the left hand side and when we ALSO have k+1 on the left hand side.

What we want to show:
1 + 2 + 3 + ... + (k+1) = ((k+1)(k+2))/2

What we get to start with:
1 + 2 + 3 + ... + k = k(k+1)/2

Step 1: write down
1 + 2 + 3 + ... + k + (k+1)

Step 2: add in some parenthesis (regroup):
1 + 2 + 3 + ... + k + (k+1) = (1 + 2 + 3 + ... + k) + (k+1)

Step 3: Remember what we got to start with and plug that into Step 2
k(k+1)/2 + (k+1)

Step 4: algebra:
k(k+1)/2 + (k+1) = (k+1)(k/2+1) = (k+1)(k+2)(1/2) = ((k+1)(k+2))/2

(first equality if factoring out (k+1) from both terms.


Here are the parts that I don't understand.

First, why are we allowed to use our assumption as part of the proof? In other words, why are we replacing (1 + 2 + 3 + . . . k) with [(k + 1)(k + 2)]/2?

Second, when [(k + 1)(k +2)]/2 is plugged into the left-hand side, how does it interact with the existing (k + 1) on that side? I don't know much algebra.


I'll address your second question first since it's quicker. We are doing a simple substitution. Say we have this formula:
x + 6 = y
But then I tell you that x = 7. Now we can plug x = 7 into the first equation and get:
7 + 6 = y
My teachers always called this "plug and chug"
In this case, we are doing a more complicated substitution. We are substituting (1 + 2 + 3 + ... + k) with k(k+1)/2. So to answer your question of how the k(k+1)/2 interacts with the existing (k+1) here is what happens. Since the (1 + 2 + 3 + ... + k) was simply ADDED to the existing (k+1), when we replace it with k(k+1)/2 then the k(k+1)/2 is also simply ADDED to the existing (k+1). You can see this as I've written it in Step 3.

As for your first question of why we are allowed to use the assumption as part of the proof, that gets to the heart of how induction works. Here is the analogy I always heard. Induction is like climbing a ladder. Imagine we have a ladder and we want to know if we can climb it. There are two things we need to know
1) Can we get on the ladder at all? This is equation to checking the base case of the n=1 case.

2) If we are on the ladder on any given rung, are we able to get from whatever rung we are on to the next rung. Can we go from n to n+1?

the second part is the induction step. We are just checking that if we are on rung n can we get to rung n+1. If this is true for any possible value of n, then that means that (as long as we can get on the ladder) we can climb as high as we want because we just go from n to n+1, then n+1 to n+2, etc.

Does this help make a little more sense? It is very abstract at first and does feel very circular but it actually isn't circular and it is very clever. However, if you forget to check the base case then the argument IS circular and is invalid so you need to make sure you check that.


Thank you for your patience. Much appreciated. And I'm glad that you made explicit something that seems to be implicit in many introductions to mathematical induction - namely, the fact that the substitution occurs on the left-hand side as a result of the assumption we made earlier in the process! You'd be surprised by how many tutorials I've read online that omit this vital piece of information. This omission is frustrating to beginners/morons like me.

Further questions:

1. I've got this so far:

Assume that: 1 + 2 + 3 + . . . + k = [k(k+1)]/2

So, I test it by plugging in the next increment:

1 + 2 + 3 + . . . + k + (k + 1) = [(k + 1)((k + 1) + 1)]/2

That can be simplified as follows:

1 + 2 + 3 + . . . + k + (k + 1) = [(k + 1)(k + 2)]/2

Then, I have to substitute the assumption in place of 1 + 2 + 3 + . . . k, which leaves me with:

[(k(k+1))/2] + (k + 1) = [(k + 1)(k + 2)]/2

But that's where I get stuck - where do I go from there?

My thinking is that I'd chug on both sides, which would eventually leave this:

k^2 + 3(k) + 2 = k^2 + 3(k) + 2

Is this correct? If so, have I proved it?

2. Is mathematical induction useful only for integers? All of the examples I've seen deal with integers, and I'm not sure how it would apply to real numbers. I'm obviously too stupid to actually follow a proof involving real numbers (if one exists), but I was just curious about the limits of this area.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Mathematical Induction - Help for a Beginner?

Postby jaap » Fri Jan 02, 2015 7:31 pm UTC

[This took a while to write, so it has been slightly overtaken by previous posts]

So we have this formula that may or may not be true:
1+2+3+...+k = k*(k+1)/2

Suppose someone with a lot of patience has actually evaluated this for k equal to one million, i.e. he added up all the numbers from 1 to 1000000, and found that this equalled 1000000*1000001/2. So he has verified that the formula is true for the value k=1000000.

Now what about k=1000001? Would it still be true? Now you could go and sum up all the numbers from 1 to 1000001, but that is a lot of work. It would be much easier to build on what that patient guy has done - he already summed the first million numbers, and got 1000000*1000001/2, so for you to calculate 1+2+..+1000001, all you have to do is add that last term.
So you calculate 1000000*1000001/2 + 1000001. However, that formula we are testing says that (for the value of k=1000001) this should be equal to 1000001*1000002/2. You can check that this is true:
1000000*1000001/2 + 1000001 = 1000001*(1000000/2 + 1) = 1000001*1000002/2
So the formula works for k=1000001 as well.

Now someone comes along and says - so the formula works for k=1000001, well what about 1000002 then? Does the formula still hold?
So you use the same trick. You know what the sum of 1+2+...+1000001 is, add 1000002, and see if that matches what the formula says. It is exactly the same as the above, just with the large numbers incremented by one.
So what about k=1000003? You do the same trick again, with the numbers incremented once more.

So what about k=2000000? Well you'll just have to do the trick a million times...
Or rather, you have to show that the trick will really work every time, by writing a generic version that does not use a specific value of k=1000000 or k=1000001 but that you can apply exactly every time without needing to change it.
So you have to write a mini-proof of this statement:
"If the formula holds for a particular value of k, then it also holds for the next higher value of k."

Once you have that mini-proof, then you can be sure that this process described above really does work. It shows that the trick really can be applied a million more times to show the formula holds for k=2000000. In fact it shows that the formula holds for any larger value of k that you care to name.

Induction is merely the formal name of the above process. For induction to prove something you need to:
1) Provide a proof of: "If something holds for a particular value of k, then it also holds for the next higher value of k."
2) Show something is true for one particular value of k.
Then induction allows you to deduce that this something is true for all larger values of k.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 7:48 pm UTC

jaap wrote:
Induction is merely the formal name of the above process. For induction to prove something you need to:
1) Provide a proof of: "If something holds for a particular value of k, then it also holds for the next higher value of k."
2) Show something is true for one particular value of k.
Then induction allows you to deduce that this something is true for all larger values of k.


Thank you for your explanation and for taking the time to write it. Based on your explanation, my understanding is that mathematical induction doesn't actually prove that something is true, but rather proves that something is true if the conditional is true. Is that correct?

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 7:55 pm UTC

MathDoofus wrote:Thank you for your patience. Much appreciated. And I'm glad that you made explicit something that seems to be implicit in many introductions to mathematical induction - namely, the fact that the substitution occurs on the left-hand side as a result of the assumption we made earlier in the process! You'd be surprised by how many tutorials I've read online that omit this vital piece of information. This omission is frustrating to beginners/morons like me.


You're not a moron! You're getting it! Good job for picking up on what a lot of tutorials leave out.

Technically you did prove it. If you start with some statement like A = B (and you don't know if it is true or not) and you do algebraic manipulations and you end up with something like c = c then what this means is that A =B is true. This is because you know c=c is true and you could do the reverse manipulations to get back A = B. However, I would consider this a sort of 'backwards' way of doing the proof.

The reason your proof came out backwards is because you are "testing" the induction conclusion (i.e. the k + 1) case using the k case as an assumption. This is a valid way of doing it, but I prefer to start with the k case and use that to derive the k + 1 case. Look at my colored post above to see what I mean by deriving it starting with the k case.


2. Is mathematical induction useful only for integers? All of the examples I've seen deal with integers, and I'm not sure how it would apply to real numbers. I'm obviously too stupid to actually follow a proof involving real numbers (if one exists), but I was just curious about the limits of this area.


Interesting question! Basic induction certainly works only on the integers. This is because we need to know how far up the ladder we are to go with each step. For the real numbers if we choose some step size z, there will always be a smaller step z=1/2 that we miss so how are we to choose a good step size?

Now, there is such a thing as transfinite induction which can 'in some contexts' be applied to the real numbers but not in the way you're probably thinking. Suffice it to say you're question is very interesting and people have thought about that, but the full answer is too technical to explain here!

edit: More:
MathDoofus wrote:
jaap wrote:
Induction is merely the formal name of the above process. For induction to prove something you need to:
1) Provide a proof of: "If something holds for a particular value of k, then it also holds for the next higher value of k."
2) Show something is true for one particular value of k.
Then induction allows you to deduce that this something is true for all larger values of k.


Thank you for your explanation and for taking the time to write it. Based on your explanation, my understanding is that mathematical induction doesn't actually prove that something is true, but rather proves that something is true if the conditional is true. Is that correct?


No, the FULL process of induction does prove something is true. The "induction step" (i.e. the can you get to the next rung step) only proves something conditional. The induction step proves IF I am on the rung k, THEN I get to rung k + 1. It is the other step, the base case, which tells us that we CAN get onto the ladder. Thus the entire proof proves that we can get to any rung of the ladder, because we know we can step onto rung 1 from the base case, but from the induction step we know we can get from rung 1 to rung 2, and then rung 2 to rung 3 etc.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 8:06 pm UTC

Twistar wrote:
Technically you did prove it. If you start with some statement like A = B (and you don't know if it is true or not) and you do algebraic manipulations and you end up with something like c = c then what this means is that A =B is true. This is because you know c=c is true and you could do the reverse manipulations to get back A = B. However, I would consider this a sort of 'backwards' way of doing the proof.

The reason your proof came out backwards is because you are "testing" the induction conclusion (i.e. the k + 1) case using the k case as an assumption. This is a valid way of doing it, but I prefer to start with the k case and use that to derive the k + 1 case. Look at my colored post above to see what I mean by deriving it starting with the k case.


Thank you for the encouragement! One last question: I have looked at your post and still don't know what you mean by "using the k case as an assumption" and "deriving it starting with the k case."

User avatar
PeteP
What the peck?
Posts: 1451
Joined: Tue Aug 23, 2011 4:51 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby PeteP » Fri Jan 02, 2015 8:10 pm UTC

MathDoofus wrote:
jaap wrote:
Induction is merely the formal name of the above process. For induction to prove something you need to:
1) Provide a proof of: "If something holds for a particular value of k, then it also holds for the next higher value of k."
2) Show something is true for one particular value of k.
Then induction allows you to deduce that this something is true for all larger values of k.


Thank you for your explanation and for taking the time to write it. Based on your explanation, my understanding is that mathematical induction doesn't actually prove that something is true, but rather proves that something is true if the conditional is true. Is that correct?

The inductive step only shows that the formula holds for k+1 if it did hold for k yes. But that is why you also show that it holds for your first number. The two steps together prove that the formula is true for the natural numbers.

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 8:15 pm UTC

Twistar wrote:What we want to show:
1 + 2 + 3 + ... + (k+1) = ((k+1)(k+2))/2

What we get to start with:
1 + 2 + 3 + ... + k = k(k+1)/2

Step 1: write down
1 + 2 + 3 + ... + k + (k+1)

Step 2: add in some parenthesis (regroup):
1 + 2 + 3 + ... + k + (k+1) = (1 + 2 + 3 + ... + k) + (k+1)

Step 3: Remember what we got to start with and plug that into Step 2
k(k+1)/2 + (k+1)

Step 4: algebra:
k(k+1)/2 + (k+1) = (k+1)(k/2+1) = (k+1)(k+2)(1/2) = ((k+1)(k+2))/2

(first equality if factoring out (k+1) from both terms.


So the first line, What we want to show. That's like the title at the top of the page. I haven't proven it yet, it's what I want to prove. I just wrote it down so that when I finish the rest of my proof I will know when I'm done! This can often be something that's actually really hard for beginners to figure it out so I write it at the top!
The next line is when the proof starts, step 1. "what we get to start with". It is the assumption and I start by just writing it down. Then, in steps 2, 3, and 4 I take what I started with, the assumption, and do algebraic manipulations to it. I manipulate and manipulate until I get to the last equation in step 4 which matches what I was looking for in the first place! That's why I colored them both blue. So this means I derived the result I was looking for from the initial assumption. This is called a "direct proof" in mathematics. Maybe your discrete math textbook talks about direct proofs.

edit: typo
Last edited by Twistar on Fri Jan 02, 2015 8:16 pm UTC, edited 1 time in total.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 8:16 pm UTC

PeteP wrote:
MathDoofus wrote:
jaap wrote:
Induction is merely the formal name of the above process. For induction to prove something you need to:
1) Provide a proof of: "If something holds for a particular value of k, then it also holds for the next higher value of k."
2) Show something is true for one particular value of k.
Then induction allows you to deduce that this something is true for all larger values of k.


Thank you for your explanation and for taking the time to write it. Based on your explanation, my understanding is that mathematical induction doesn't actually prove that something is true, but rather proves that something is true if the conditional is true. Is that correct?

The inductive step only shows that the formula holds for k+1 if it did hold for k yes. But that is why you also show that it holds for your first number. The two steps together prove that the formula is true for the natural numbers.


That makes sense - the base case is the "first number" step, right? So if I show that it works for the base case (i.e., an actual number) and I prove that it works for any integer plus one, then I've proved it?

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 8:19 pm UTC

MathDoofus wrote:
PeteP wrote:
MathDoofus wrote:
jaap wrote:
Induction is merely the formal name of the above process. For induction to prove something you need to:
1) Provide a proof of: "If something holds for a particular value of k, then it also holds for the next higher value of k."
2) Show something is true for one particular value of k.
Then induction allows you to deduce that this something is true for all larger values of k.


Thank you for your explanation and for taking the time to write it. Based on your explanation, my understanding is that mathematical induction doesn't actually prove that something is true, but rather proves that something is true if the conditional is true. Is that correct?

The inductive step only shows that the formula holds for k+1 if it did hold for k yes. But that is why you also show that it holds for your first number. The two steps together prove that the formula is true for the natural numbers.


That makes sense - the base case is the "first number" step, right? So if I show that it works for the base case (i.e., an actual number) and I prove that it works for any integer plus one, then I've proved it?


Bingo

Nyktos
Posts: 138
Joined: Mon Mar 02, 2009 4:02 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Nyktos » Fri Jan 02, 2015 8:21 pm UTC

MathDoofus wrote:That makes sense - the base case is the "first number" step, right? So if I show that it works for the base case (i.e., an actual number) and I prove that it works for any integer plus one, then I've proved it?

If you do that, you've proved that it holds for any integer greater than or equal to the base case. The base case is normally 0 or 1, so you're showing that it holds for non-negative or positive integers respectively.

Whether you've proven what you want to prove, well, that depends on what you want to prove. If you want it to hold for all negative numbers as well you'll need to do more work, for instance.
Last edited by Nyktos on Fri Jan 02, 2015 8:21 pm UTC, edited 1 time in total.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 8:21 pm UTC

Twistar wrote:
Twistar wrote:What we want to show:
1 + 2 + 3 + ... + (k+1) = ((k+1)(k+2))/2

What we get to start with:
1 + 2 + 3 + ... + k = k(k+1)/2

Step 1: write down
1 + 2 + 3 + ... + k + (k+1)

Step 2: add in some parenthesis (regroup):
1 + 2 + 3 + ... + k + (k+1) = (1 + 2 + 3 + ... + k) + (k+1)

Step 3: Remember what we got to start with and plug that into Step 2
k(k+1)/2 + (k+1)

Step 4: algebra:
k(k+1)/2 + (k+1) = (k+1)(k/2+1) = (k+1)(k+2)(1/2) = ((k+1)(k+2))/2

(first equality if factoring out (k+1) from both terms.


So the first line, What we want to show. That's like the title at the top of the page. I haven't proven it yet, it's what I want to prove. I just wrote it down so that when I finish the rest of my proof I will know when I'm done! This can often be something that's actually really hard for beginners to figure it out so I write it at the top!
The next line is when the proof starts, step 1. "what we get to start with". It is the assumption and I start by just writing it down. Then, in steps 2, 3, and 4 I take what I started with, the assumption, and do algebraic manipulations to it. I manipulate and manipulate until I get to the last equation in step 4 which matches what I was looking for in the first place! That's why I colored them both blue. So this means I derived the result I was looking for from the initial assumption. This is called a "direct proof" in mathematics. Maybe your discrete math textbook talks about direct proofs.

edit: typo


Thank you. My question is now why we got different results.

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 8:27 pm UTC

We got the same results. The result we both got is as follows:

"For every integer n, the following equality holds:
1 + 2 + 3 + ... + n = n(n+1)/2"

We both proved that statement but in different ways. This is why math teachers are always saying annoyingly "there's more than one way to do things in math". We proved the same thing different ways.

I proved it by this reasoning:
1) prove the base case (actually I didn't write it in my post but 1 = 1(2)/2)
2) assume the k case
3) starting from the k case do algebra to derive the k+1 case

You proved it by this reasoning:
1) prove the base case
2) assume the k+1 case (note, at the point you don't know whether the k+1 case is true or not, you just assumed it)
3) assume the k case
4) do algebra using the k+1 case and the k case to ultimately prove that your assumption of the k+1 case was correct.

You're way is technically correct, but is in my opinion more confusing and 'feels' more circular even though it isn't.

edit: you proved the k+1 case by starting with
1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2 and doing algebra to derive:
-->
k^2 + 3(k) + 2 = k^2 + 3(k) + 2
If you divide both sides by k^2 + 3(k) + 2 you get
-->
1=1

If you start with something like A = B (the first line in my edit:) and you do algebra and arrive at 1=1 that means that the thing you started with is a TRUE equality. If you start with something that is not a true equality you will get something like 1=2 or 1=10 which is clearly false so you know that whatever you started with is NOT TRUE. That is called proof by contradiction.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 8:30 pm UTC

Twistar wrote:
You proved it by this reasoning:
1) prove the base case
2) assume the k+1 case (note, at the point you don't know whether the k+1 case is true or not, you just assumed it)
3) assume the k case
4) do algebra using the k+1 case and the k case to ultimately prove that your assumption of the k+1 case was correct.

You're way is technically correct, but is in my opinion more confusing and 'feels' more circular even though it isn't.


I don't understand steps 2 and 3 - I thought the k case and the (k + 1) case were assumed more or less simultaneously.

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 8:32 pm UTC

MathDoofus wrote:
Twistar wrote:
You proved it by this reasoning:
1) prove the base case
2) assume the k+1 case (note, at the point you don't know whether the k+1 case is true or not, you just assumed it)
3) assume the k case
4) do algebra using the k+1 case and the k case to ultimately prove that your assumption of the k+1 case was correct.

You're way is technically correct, but is in my opinion more confusing and 'feels' more circular even though it isn't.


I don't understand steps 2 and 3 - I thought the k case and the (k + 1) case were assumed more or less simultaneously.


look at my edit. An induction proof has two elements, the base case, and the induction step. The induction step involves PROVING the k+1 case by ASSUMING the k case. you technically did that but in a roundabout way. You basically made an additional assumption but then justified that assumption by showing it leads to 1=1.

edit: i.e. you don't HAVE to assume the k+1 case. For example, in my proof I don't assume the k+1 case, I just prove it. In your proof you happened to assume the k+1 case as well which made it confusing because you kind of made an extra unnecessary assumption

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 8:37 pm UTC

Twistar wrote:
MathDoofus wrote:
Twistar wrote:
You proved it by this reasoning:
1) prove the base case
2) assume the k+1 case (note, at the point you don't know whether the k+1 case is true or not, you just assumed it)
3) assume the k case
4) do algebra using the k+1 case and the k case to ultimately prove that your assumption of the k+1 case was correct.

You're way is technically correct, but is in my opinion more confusing and 'feels' more circular even though it isn't.


I don't understand steps 2 and 3 - I thought the k case and the (k + 1) case were assumed more or less simultaneously.


look at my edit. An induction proof has two elements, the base case, and the induction step. The induction step involves PROVING the k+1 case by ASSUMING the k case. you technically did that but in a roundabout way. You basically made an additional assumption but then justified that assumption by showing it leads to 1=1.

edit: i.e. you don't HAVE to assume the k+1 case. For example, in my proof I don't assume the k+1 case, I just prove it. In your proof you happened to assume the k+1 case as well which made it confusing because you kind of made an extra unnecessary assumption


I'm sorry, but I still don't understand how our paths diverged. In other words, I don't understand the meaning of the statement "I don't assume the k + 1 case, I just prove it." Don't both k and (k + 1) have to be assumed for induction to work?

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 8:41 pm UTC

MathDoofus wrote:I'm sorry, but I still don't understand how our paths diverged. In other words, I don't understand the meaning of the statement "I don't assume the k + 1 case, I just prove it." Don't both k and (k + 1) have to be assumed for induction to work?


No, just the k case has to be assumed. Look at my proof again and try to tell me where I assume the k+1 case.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 8:44 pm UTC

Twistar wrote:
MathDoofus wrote:I'm sorry, but I still don't understand how our paths diverged. In other words, I don't understand the meaning of the statement "I don't assume the k + 1 case, I just prove it." Don't both k and (k + 1) have to be assumed for induction to work?


No, just the k case has to be assumed. Look at my proof again and try to tell me where I assume the k+1 case.


I re-read your proof - I'm still unclear on the differences between our methods. It looks to me like the (k + 1) case is assumed in step 1 of your proof.

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 8:54 pm UTC

Let me re-write your proof.

What we want to prove:
1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2

Now, you assumed the k+1 case first and then assumed the k case. But like you said, you did it basically simultaneously so I'm just going to reverse the order

Induction step: assume the k case
1 + 2 + 3 + ... + k = k(k+1)/2
Now store this fact in your back pocket for a second.. since we are within the induction step part of the proof we are going to assume this is true for this whole step.

Assuming the k+1 case step
Now lets assume the k+1 case and see what happens. We don't yet know if it is true or not so we are going to test and see. Note that this is where you and I diverge. I put the =? since we're not yet sure if this equality holds
1 + 2 + 3 + ... + k + (k+1) =? (k+1)(k+2)/2
A=?B
Now plug in the k case:

k(k+1)/2 + (k+1) = (k+1)(k+2)/2
-->
k^2 + 3(k) + 2 = k^2 + 3(k) + 2
-->
1=1

since we got from
A=?B
to
1=1
this means that we can get rid of the ? and in fact
A=B
which means
1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2
which is what we were trying to prove.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 9:09 pm UTC

Twistar wrote:Let me re-write your proof.

What we want to prove:
1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2

Now, you assumed the k+1 case first and then assumed the k case. But like you said, you did it basically simultaneously so I'm just going to reverse the order



I don't understand what you mean by this statement.

Cradarc
Posts: 455
Joined: Fri Nov 28, 2014 11:30 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Cradarc » Fri Jan 02, 2015 9:09 pm UTC

I'm going to try to visualize this for you.

You want to prove: 1 + 2 + 3 + . . . n = n(n+1)/2, for ALL n >0.
Imagine you have an infinitely long assembly line. Let the first worker be Worker 1, the second be Worker 2, etc.
You tell Worker 1 to prove it true for n=1, Worker 2 to prove true for n=2, etc. If all the workers can prove their portion, then the original statement is proved true.

Fundamental Concept: Once something is proven, it can be used as truth for other proofs.
Think about it like assembling a large machine. Suppose a particular worker needs to make an engine. To do that he will need a piston. However he doesn't need to know how to make the piston, as long as he knows someone before him will make one. He can assume a piston will be passed to him when it comes time for him to build the engine.

The "base case" is to show that Worker 1 can "build" his portion out of scratch. In this case, show that for n=1, the equation is true.
The "induction case" is to show that every worker after Worker 1 can build his part if the worker before him can build theirs.

When you "assume true for k", you are actually assuming "the worker before the (k+1)th worker knows how to build his part". When you "prove true for k+1", you are actually proving "Then the (k+1)th worker can build his part".
k is an arbitrary variable. It generalizes the statement to any worker, as long as one of them (the kth worker) comes immediately before the other (the (k+1)th worker)

Now consider the base and induction case together:
Base case showed that the first person can build his part out of scratch. Induction case showed that if any worker can build his part, the worker that comes after can also build his using the result. You can imagine how the assembly line can function. At each worker, more and more of the total proof is "built up".
This is a block of text that can be added to posts you make. There is a 300 character limit.

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 9:15 pm UTC

MathDoofus wrote:
Twistar wrote:Let me re-write your proof.

What we want to prove:
1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2

Now, you assumed the k+1 case first and then assumed the k case. But like you said, you did it basically simultaneously so I'm just going to reverse the order



I don't understand what you mean by this statement.


Oh the last sentence of mine that you quoted is meant to be a summary of how you did your proof in one of your above posts. I am just trying to recreate your proof but twerk it slightly so that you better understand what you actually did.

My advice for you is to do induction proofs the way I did them, by direct proof. I would call your method "testing" the k+1 case, but it is more confusing in my opinion. If you understand the way I did it then stick with that because I think that is the least confusing way of doing induction proofs.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 9:18 pm UTC

Twistar wrote:
MathDoofus wrote:
Twistar wrote:Let me re-write your proof.

What we want to prove:
1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2

Now, you assumed the k+1 case first and then assumed the k case. But like you said, you did it basically simultaneously so I'm just going to reverse the order



I don't understand what you mean by this statement.


Oh the last sentence of mine that you quoted is meant to be a summary of how you did your proof in one of your above posts. I am just trying to recreate your proof but twerk it slightly so that you better understand what you actually did.

My advice for you is to do induction proofs the way I did them, by direct proof. I would call your method "testing" the k+1 case, but it is more confusing in my opinion. If you understand the way I did it then stick with that because I think that is the least confusing way of doing induction proofs.


I apologize - I don't understand your method or how it differs from what I did. Can you clarify? I understand if you're losing patience at this point. As my user name indicates, I'm an idiot when it comes to math. If math-related concepts don't come to me intuitively, I have a difficult time picking them up.

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 9:21 pm UTC

Why don't you go ahead and try to recreate the proof how I did it, and the proof how you did it side by side and see if you can see differences. Post your results for trying to do the proof my way because I want to see if you're understanding it. Remember, NOWHERE in my proof do I assume the k+1 case. (I do write it down at the beginning of my proof, but that is only so I know what I'm looking for by the time I get to the end of the proof, that first blue line is not technically part of the proof.)

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 9:29 pm UTC

Twistar wrote:Why don't you go ahead and try to recreate the proof how I did it, and the proof how you did it side by side and see if you can see differences. Post your results for trying to do the proof my way because I want to see if you're understanding it. Remember, NOWHERE in my proof do I assume the k+1 case. (I do write it down at the beginning of my proof, but that is only so I know what I'm looking for by the time I get to the end of the proof, that first blue line is not technically part of the proof.)


I apologize again. My problem (I guess) is that I don't understand your method. Broadly speaking, here's how I've figured out how to solve the problem below:

Prove that 1 + 2 + 3 + . . . + n = n(n + 1)/2

- Step 1: Plug in k in place of n.

1 + 2 + 3 + . . . + k = k(k + 1)/2

- Step 2: Plug in (k + 1). [Note: I'm not sure why I'm doing this, but this is what the text advises me to do.]

1 + 2 + 3 + . . . + k + (k + 1) = [(k + 1)((k + 1) + 1)]/2

- Step 3: Plug in the assumption in place of the series.

k(k + 1)/2 + (k + 1) = [(k + 1)((k + 1) + 1)]/2

- Step 4: Chug on both sides of the equals sign.

Is this wrong? If so, why?

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 9:39 pm UTC

No that is correct. I've been telling you that is correct. However, you need to realize that it is not necessary to assume the k+1 case.
In my proof I do not assume the k+1 case. I start with the k case, (step 1 in my proof) then I do some algebraic manipulations (steps 2, 3, and 4) and end up with the following expression:
1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2

This is exactly the statement "1 + 2 + 3 + ... + n = n(n+1)/2" for n = k + 1. So to summarize,

I started with
"1 + 2 + 3 + ... + n = n(n+1)/2" holds for n = k
Then I did algebra, and proved that
"1 + 2 + 3 + ... + n = n(n+1)/2" holds for n = k+1
That means that I have completed the induction step of the proof. There are at least two different ways to do the inductive step. Your text does it one way, I do it another way.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 9:42 pm UTC

Twistar wrote:No that is correct. I've been telling you that is correct. However, you need to realize that it is not necessary to assume the k+1 case.
In my proof I do not assume the k+1 case. I start with the k case, (step 1 in my proof) then I do some algebraic manipulations (steps 2, 3, and 4) and end up with the following expression:
1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2

This is exactly the statement "1 + 2 + 3 + ... + n = n(n+1)/2" for n = k + 1. So to summarize,

I started with
"1 + 2 + 3 + ... + n = n(n+1)/2" holds for n = k
Then I did algebra, and proved that
"1 + 2 + 3 + ... + n = n(n+1)/2" holds for n = k+1
That means that I have completed the induction step of the proof. There are at least two different ways to do the inductive step. Your text does it one way, I do it another way.


I'm still having trouble processing the way you did it. It looks to me like you've assumed the (k + 1) case in one of the steps.

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 9:42 pm UTC

MathDoofus wrote:
Twistar wrote:No that is correct. I've been telling you that is correct. However, you need to realize that it is not necessary to assume the k+1 case.
In my proof I do not assume the k+1 case. I start with the k case, (step 1 in my proof) then I do some algebraic manipulations (steps 2, 3, and 4) and end up with the following expression:
1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2

This is exactly the statement "1 + 2 + 3 + ... + n = n(n+1)/2" for n = k + 1. So to summarize,

I started with
"1 + 2 + 3 + ... + n = n(n+1)/2" holds for n = k
Then I did algebra, and proved that
"1 + 2 + 3 + ... + n = n(n+1)/2" holds for n = k+1
That means that I have completed the induction step of the proof. There are at least two different ways to do the inductive step. Your text does it one way, I do it another way.


I'm still having trouble processing the way you did it. It looks to me like you've assumed the (k + 1) case in one of the steps.


Which step?

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby MathDoofus » Fri Jan 02, 2015 9:44 pm UTC

Twistar wrote:
Which step?


Step 1, where you include the (k + 1) in the series on the left-hand side.

Twistar
Posts: 445
Joined: Sat May 09, 2009 11:39 pm UTC

Re: Mathematical Induction - Help for a Beginner?

Postby Twistar » Fri Jan 02, 2015 9:49 pm UTC

Let me rewrite the proof

We are attempting to prove "1 + 2 + 3 + ... + n = n(n+1)/2" for all integers n

1) Base case n = 1
1 = 1(2)/2 = 1 Check

2) Induction step, assume n = k case and prove n = k + 1 case
a) 1 + 2 + 3 + ... + k = k(k+1)/2 -assumption
b) 1 + 2 + 3 + ... + k + (k+1) = ??? -We don't know what this is equal to. Let's find out
c) 1 + 2 + 3 + ... + k + (k+1) = k(k+1)/2 + (k+1) -plugging in assumption from line a)
d) 1 + 2 + 3 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k^2 + 3k +2)/2 = (k+1)(k+2)/2 - algebra
e) 1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2 -Simple rewriting of the previous line, no math here
f) This is the statement "1 + 2 + 3 + ... + n = n(n+1)/2" for the n = k + 1 case so we have done what we wanted. Proof complete.

edit: Yeah, I see your confusion. I'm not assuming the k + 1 case because I am not assuming that the left hand side equals anything. I am just writing down "1 + 2 + 3 + ... + k + (k+1)" and sort of seeing where it takes me. The reason I wrote it down is because I know that that expression is part of what I'm looking for (the equation in blue).


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 12 guests