I don't get INDUCTION!! (1 Viewer)

[live.fast]

Hey i posted this because i seriously don't understand how induction works logically. I mean the first step is alright, prove n = 1 works, that's all well and good.

But then the second step seems a bit...weird to me.

Induction is meant to be proving an equation thingy works for all integers, right?

But the second step is to assume that an integer, K, works.

I mean, doesn't that kind of go against the whole point of induction? Because you're trying to prove something works? But if you're instantly assuming one integer works (K), then doesn't this undermine the whole process? I mean then, by that logic, you should be able to assume that integer L, M, N, O, P etc all work too. Therefore the equation works. By assumption. That's just...weird.... Not to mention the fact that you're proof becomes based on assumption, if you follow the rest of the steps. The 3rd step would only work if K actually works, isn't it? But my main problem I think is understanding how you're allowed to assume something works.

lol of course i'm probably just entirely wrong, but it just doesn't make sense to my sloooowww brain. So yep, newaiz, pleeaaase someone explain to me wat's goin on? Why the assumption there is actually allowed. ??

 

[pLuvia]

You proved that one number works, so then you assume numbers, k, being any integer that suits the condition works also. And then you prove that any number (according to the condition) is valid (by letting n=k+1, or n=k+2)

 

[Riviet]

Example: Prove by induction that 1+2+3+...+n = n(n+1)/2 for all positive integers, n.

If n=1,
LHS=1
RHS=1(1+1)/2
=2/2
=1
.'. the statement is true for n=1

Now we assume that the statement is true for n=k, where k is some random positive integer. In other words, we asssume that
1+2+3+...+k = k(k+1)/2

We want to show that the statement is true for n=k+1 because k+1 is the next integer after k. In the same way 3 is the integer right after 2 and 12 is the integer right after 11, but we use k+1 and k as a general case when proving the statement.

So we want to prove the statement is true for n=k+1, so we substitute n=k+1 into the original statement. For the left side of the statement, we originally had
1+2+3+...+n, which is the sum of all the integers from 1 to n. We want to find the sum of the integers from 1 to k+1 so we write
1+2+3+...+ k + (k+1), which is an expression for the sum of all the integers from 1 to k+1.
On the right side of the equation, we originally had n(n+1)/2, which was what the sum of the integers from 1 to n was equal to. But we want the RHS to be an expression for the sum of all the integers from 1 to k+1, so instead of using n, we substitute k+1:
(k+1)([k+1] + 1)/2 = (k+1)(k+2)/2

Putting it together, we are required to prove that for n=k+1:
1+2+3+...+ k + (k+1) = (k+1)(k+2)/2

So we start with LHS:

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

We stop here momentarily, observing that the highlighted bit in red is identical to what we had assumed previously (above). Since we assumed that the statement is true for n=k, we can use this in our proof for n=k+1 by substituting the assumption:

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

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

We stop here again. Looking at our assumption (highlighted in blue and red above), and observing that the blue bit is equal to the red bit, so in the last line we simply replace the red bit with the blue bit which is allowed since we assumed them to be equal at the start.

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

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

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

= [k(k+1) + 2(k+1)]/2, by adding the fractions with a common denominator

= [k² + k + 2k + 2]/2

= [k² + 3k + 2]/2

= (k+1)(k+2)/2 => notice we have arrived at what we wanted to prove (highlighted in green in this line and further up)

= RHS

.'. The statement is true for n=k+1.

At the start, we proved that the statement was true for n=1. We assumed it was true for n=k and successfully used this assumption to prove that it was true for n=k+1.

Remembering that k can be ANY positive integer, it could be 1, it could be 2, 3, etc. we can say that:
If the statement is true for n=k, then it is true for n=k+1 (we have just proved this).

Since the statement is true for n=1 (we proved this at the very start), then it must also be true for n=1+1=2 (because of the orange bit).

So we have just deduced that the statement must be true for n=2, so since it is true for n=2, then the statement is also true for n=2+1=3 (because of the orange bit).

So we have just deduced that the statement must be true for n=3, so since it is true for n=3, then the statement is also true for n=3+1=4 (because of the orange bit).

So we have just deduced that the statement must be true for n=4, so since it is true for n=4, then the statement is also true for n=4+1=5 (because of the orange bit).

As you can see, this will continue on and on and on until we get to:
......... so we have just deduced that the statement must be true for n=k-2, so since it is true for n=k-2, then the statement is also true for n=k-2+1=k-1 (because of the orange bit).

So we have just deduced that the statement must be true for n=k-1, so since it is true for n=k-1, then the statement is also true for n=k-1+1=k (because of the orange bit).

We must realise that this will continue on for n=k+2, k+3, k+4, k+5, etc. and since we started from n=1, we are able to deduce that the statement is true for all positive integers n from n=1 onwards, by the principal of mathematical induction.

I hope that helps your understanding of induction.

 

[SoulSearcher]

To quote wikipedia:

The simplest and most common form of mathematical induction proves that a statement holds for all natural numbers n and consists of two steps:

1. The basis: showing that the statement holds when n = 1.
2. The inductive step: showing that if the statement holds for n = m, then the same statement also holds for n = m + 1.

The proposition following the word "if" in the inductive step is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis (that the statement is true for n = m) and then uses this assumption to prove the statement for n = m + 1.

This method works by first proving the statement is true for a starting value, and then proving that the process used to go from one value to the next is valid. If these are both proven, then any value can be obtained by performing the process repeatedly. It may be helpful to think of the domino effect; if you have a long row of dominoes standing on end and you can be sure that:

1. The first domino will fall.
2. Whenever a domino falls, its next neighbor will also fall.
then you can conclude that all dominoes will fall, and this fact is inevitable.

Another analogy can be to consider an infinite set of identical lily pads, all equally spaced on a pond. If a frog wishes to traverse the pond. He must:

1. Determine if the first lily pad will hold his weight.
2. Prove that he can jump from the one lily pad to another
then you can conclude that he can jump to all the lily pads.

 

[live.fast]

See, I just want to know if anyone else has the same problem accepting the reasoning behind the inductive process. I'll use the domino theory soulsearcher highlighted for me.

1. The first domino will fall.
2. Whenever a domino falls, its next neighbor will also fall.
then you can conclude that all dominoes will fall, and this fact is inevitable.


But with the inductive process, you're assuming a domino (K) will fall, before you're proving its neighbour will fall, right?

So if you're allowed to assume a domino (K) will fall...

Then what's stopping you from assuming that every other single domino is just like another K, and that every other single domino will also fall too?

The assumption step in the inductive process undermines the whole process of PROVING something. Doesn't it?

 

[Anonymou5]

Statement is true for n = 1.

Let k = 1 so that k + 1 = 2.
Let k = 2 so that k + 1 = 3.
Let k = 3 so that k + 1 = 4 and so on.

You've shown that the statement is true for some integer in this case, the integer one. So what's wrong with the assumption that the statement is true for n = k? What would you be assuming if k = 1?

 

[Riviet]

Then what's stopping you from assuming that every other single domino is just like another K, and that every other single domino will also fall too?

Because you don't know if it's true for n=9481138 and n=999938282828 and n=456 [until you test each out and this would take what, forever]. But by the domino effect and using the logic of induction, you are able to convincingly prove it's true for all positive integers.

 

[SoulSearcher]

http://www2.edc.org/makingmath/mathtools/induction/induction.asp

 

[live.fast]

Statement is true for n = 1.

Let k = 1 so that k + 1 = 2.
Let k = 2 so that k + 1 = 3.
Let k = 3 so that k + 1 = 4 and so on.

By this process, you can let k = ANY integer --> please note this before i continue the argument of my inability to understand induction logic.

Because you don't know if it's true for n=9481138 and n=999938282828 and n=456 [until you test each out and this would take what, forever]. But by the domino effect and using the logic of induction, you are able to convincingly prove it's true for all positive integers.

I know you don't know its true. But the second step allows for assumptions to be made. Do YOU know that n = k? No, you're assuming it. It's like assuming that n=9481138 and n=999938282828 and n=456 (k is an integer, remember?)

So if you're ASSUMING n = k, then that in itself is deviation from the process of proof isnt it. You're basis for proof for induction logic is actually, what soulsearcher described as 'an induction hypothesis' - if you do science, does the word hypothesis give any clues? SO then how does it prove itself to be true convincingly for all positive integers, when the basis of that truth is itself an assumption?

From the first quote

Statement is true for n = 1.

Let k = 1 so that k + 1 = 2.
Let k = 2 so that k + 1 = 3.
Let k = 3 so that k + 1 = 4 and so on.

The need for k +1 = 2 and k +1 = 3 etc becomes dismissed by the fact that k itself can be any integer. If k = 1, 2, 3 etc, then k can be all integers. Thus by the logic of the second step repeated iteratively for all integers, it can be concluded (by the induction hypothesis) that the equation works for all integers. And why not? What prevents this from being so, by the reasoning of induction?

And if you say, "Well duh, you can't just assume it's all true, that's stupid" then I ask, how come the 2nd step of induction lets you assume it so?

 

[Shady01]

Remember use the n=k substition for n=k+1, that is one struggling mathay to another

 

[live.fast]

That wasn't what I meant by I don't get it. The method I know. The reasoning behind the method is just...not right though. You shouldn't be able to have a proof that has the inclusion of an assumption in it. That screws up the proof.

 

[Anonymou5]

Sorry but I really don't understand what you're attempting to say in the last two bolded paragraphs could you please be less ambiguous? Are you saying that induction doesn't work? If so, why doesn't it work?

The inequality (9)^n < 10n^2 is certainly not true for all natural numbers but it is true for n >= 2. This is why you need to show that the statement is true for a specific case before you can go on to make the assumption. I still don't get the reasoning behind your belief that the assumption step is invalid. You're confusing yourself by trying to make comparisons between induction and science experiments. You would be better off to consider induction from a logical point of view rather than getting caught up in the semantics of language. In particular, don't take the word hypothesis literally - it's maths, not english.

Edit: You're worried about the integer k being able to be any integer? Lets just say that you've shown that the statement is true for n = 1. Now you 'assume'(it's just a word to convey meaning, it doesn't need to be taken literally) that the statement is true for some integer k. You might be thinking, but if k = 1000 what happens to the numbers in between 1 and 1000? That wouldn't be a problem because since you've shown that the statement is true for n = k and n = k + 1 then you can plug in any integer for k. If the equation isn't true then the algebra will not work out for the n = k + 1 step. Try 'proving' that 9^n < 10n^2 for all natural numbers.

 

[SoulSearcher]

http://www.purplemath.com/modules/inductn.htm
http://www.purplemath.com/modules/inductn2.htm
http://www.purplemath.com/modules/inductn3.htm

Read the second one in particular.

 

[who_loves_maths]

Hey i posted this because i seriously don't understand how induction works logically. I mean the first step is alright, prove n = 1 works, that's all well and good.

But then the second step seems a bit...weird to me.

Induction is meant to be proving an equation thingy works for all integers, right?

But the second step is to assume that an integer, K, works.

I mean, doesn't that kind of go against the whole point of induction? Because you're trying to prove something works? But if you're instantly assuming one integer works (K), then doesn't this undermine the whole process? I mean then, by that logic, you should be able to assume that integer L, M, N, O, P etc all work too. Therefore the equation works. By assumption. That's just...weird.... Not to mention the fact that you're proof becomes based on assumption, if you follow the rest of the steps. The 3rd step would only work if K actually works, isn't it? But my main problem I think is understanding how you're allowed to assume something works.

I'm not sure if any of the subsequent posts actually answered your question, but I think I understand where you're coming from as I had the same conceptual difficulties with induction as well in year 11.

Please tell me if I am wrong, but I think the crux of what you're asking lies in the essence of the bolded line in the quote box above ^ ?
i.e. it's the use of assumptions here that is the problem for you, not the specific methods of induction.

Initially, you might be inclined to think it's all based on the artifice of assumptions and building assumptions upon assumptions. But let's just take the example you personally gave in the bold line for a discussion:

Now, say that initially we assume "integers L, M, N, O, P, etc, all work" for a specific statement S(n).

BUT, then, we go on to prove that our assumption is in fact correct by testing all, each and every one, of the integers L, M, N, ... by say, substituting all of them in the statement S(n) and show that they satisfy it, then you would agree that we now have proved our assumptions to be correct right?

So let's agree that in order for assumptions to be accepted as "true", we need to perform the following logical steps: Assumption ---> Proof, by subsitution into S.
Let this be our standard logical model in dealing with assumptions.

Now, having agreed on that, let's examine what is at issue here with mathematical induction in the language of assumptions:

First, notice that the only assumption used in the philosophy behind induction is simply that: "suppose n= k be true".
It gets a bit conceptually abstract here but I simply can't stress enough how important it is to realise that this is the one and only assumption in all of induction!

It's necessary to try and distinguish this single part from everything else involved in induction because this is why I think you're getting a bit confused with it all - do not mix up this assumption with the separate step of showing that "n = k+1 be true" which is not an assumption, it is a technique.

So then we apply our logical model "Assumption ---> Proof by substitution into S" to this, and we arrive at the necessary obstacle that we need to prove "suppose n= k be true" by somehow testing 'k' against the statement S(n).

How do we do that? What is 'k'?

Well, at this stage there is nothing wrong with saying 'k' can be any/all of L, M, N, ... and then go on to show all these integers satisfy S(n) - but this is too tedious a procedure. So instead we say "k is arbitrary" because 'k' is a pronumeral representing any one number.

Thus we proceed to fix 'k' and assign it an actual value - say, 1. We then go on to show n = k = 1 is in fact true - i.e. S(1) true. And this, as you know, is done in the first step of any induction proof.
Hence, we have proven the only assumption using the our model "Assumption ---> Proof by substitution into S" in the first step of any induction proof.

Now what remains: "n = k+1 be true" is, as I said, not an assumption - it is a technique that frees us from testing all of L, M, N, ... since we really only need to test one of these integers.


Finally, you will have noticed, hopefully, that this above argument uses a very general set of logic to validate the principle of induction - it doesn't actually involve the specifics of the methods used in induction proofs (which I know isn't what you're interested in anyways ).
This set of logic behind validating assumptions in mathematics is actually very fundamental, albeit subtle at times:
For example, have you realised that the method of trial-and-error uses the identical set of logic as mathematical induction?

e.g. Find the root of the equation: x - 1 = 0

Suppose we haven't yet established the rules of algebra and so don't know how to systematically solve the above equation. We proceed with trial-and-error.

Logically, in any trial-and-error method we make an initial assumption:
let's assume x = 1 gives us the root.

How do we prove this assumption? By substitution:
We find that 1 -1 = 0 ---> LHS = RHS indeed gives us the root.
Hence, problem solved.


The real issue here I think is getting yourself to be able to conceptually distinguish the assumptions in induction proofs as separate entities from the rest of the proof and analysing only that part - if you can do that successfully without mixing up other steps in induction then you shouldn't have difficulties with it anymore.

Remember: there is only one assumption in induction proofs, and that single assumption is always proven in the very first step of the induction process when you prove the statement S(n) is true for some fixed value of arbitrary 'k', usually k = 1.
[this is why the first step, although easiest to perform, is crucial in an overall inductive proof.]


Hope that might have cleared a few things up ... though, it's extremely hard to explain logic clearly over the net like this.

 

[Slidey]

See, I just want to know if anyone else has the same problem accepting the reasoning behind the inductive process. I'll use the domino theory soulsearcher highlighted for me.

1. The first domino will fall.
2. Whenever a domino falls, its next neighbor will also fall.
then you can conclude that all dominoes will fall, and this fact is inevitable.


But with the inductive process, you're assuming a domino (K) will fall, before you're proving its neighbour will fall, right?

So if you're allowed to assume a domino (K) will fall...

Then what's stopping you from assuming that every other single domino is just like another K, and that every other single domino will also fall too?

The assumption step in the inductive process undermines the whole process of PROVING something. Doesn't it?

I won't help with the explanation, but I'll add some comforting words:

A LOT of students have problems with it (a few teachers I've asked have said so, and it doesn't surprise me). It feels like "cheating". All I can gaurentee is that it isn't cheating, and does work. Oh, and I myself had big problems with it at first. It's something which just snaps into understanding.

 

[who_loves_maths]

A LOT of students have problems with it (a few teachers I've asked have said so, and it doesn't surprise me). It feels like "cheating". All I can gaurentee is that it isn't cheating, and does work. Oh, and I myself had big problems with it at first. It's something which just snaps into understanding.

^ Cheating ?

Well, at least we don't need to use up space on the 'cheat sheets' to write up induction proof-formulae , so it's good for something right?

 

[live.fast]

lol yeaaa you see that's da kinda explanation i was looking for! lol but i still got questions. sorta.

so you're saying that for this sorta proof, it's about assuming something works, and then proving it doesnt, and if you can't prove it doesnt, then it does...which makes sense.

Well, at this stage there is nothing wrong with saying 'k' can be any/all of L, M, N, ... and then go on to show all these integers satisfy S(n) - but this is too tedious a procedure. So instead we say "k is arbitrary" because 'k' is a pronumeral representing any one number.

Thus we proceed to fix 'k' and assign it an actual value - say, 1. We then go on to show n = k = 1 is in fact true - i.e. S(1) true. And this, as you know, is done in the first step of any induction proof.

But you know how k is arbitrary, right? So if k is assigned its value, say 1, which is the only actual number number I see proven in the induction method....
So the 1st step, where n = 1 is proven, and then n = k = 1, like you said,
then what about the rest of the numbers? If k is say one, then k +1 = 2. But the 1st step of induction only proves that n = 1 works. the rest of the numbers aren't all ' 1's '. Just because it works for n=1, and just because k CAN be n =1, it doesnt mean that suddenly all the other values that k can be, can work. They still all have to be proven, right?

Hence, we have proven the only assumption using the our model "Assumption ---> Proof by substitution into S" in the first step of any induction proof.

The assumption that n = k works in the equation hasn't been proven if k can have any integer value. You'd have to prove it for all of k's integer values. K can be 1, and it's been proven it works for one. But K could also be 100, 1000, 100000...and you haven't yet proven it for these values. The fact that K is an arbitrary number, doesnt that mean you have to prove n =k works for all of K's possible values? Number by Number? Before you assume n = k ?


e.g. Find the root of the equation: x - 1 = 0

Suppose we haven't yet established the rules of algebra and so don't know how to systematically solve the above equation. We proceed with trial-and-error.

Logically, in any trial-and-error method we make an initial assumption:
let's assume x = 1 gives us the root.

How do we prove this assumption? By substitution:
We find that 1 -1 = 0 ---> LHS = RHS indeed gives us the root.
Hence, problem solved.

Wouldn't that be like saying here, that just because the number 1 works to solve this equation, and that k can be 1 (k=1), that the k works to solve all equations?

The assumption can't have yet been proven by that. No assumption for an arbitrary k (where k can be ANY integer) can be proven by one solution alone. The only way your assumption for 'n=k works' can be proven is by proving its works for every single value that k could possibly be. Not just one value that k could possibly be

Remember: there is only one assumption in induction proofs, and that single assumption is always proven in the very first step of the induction process when you prove the statement S(n) is true for some fixed value of arbitrary 'k', usually k = 1.
[this is why the first step, although easiest to perform, is crucial in an overall inductive proof.]

Thus the assumption remains an assumption. However, you'll probably question me on the fact that k's arbitrary value is also a FIXED value. Which I only understand as this, that k = 1, right? But then k, can change? Or does k remain k=1? Because for the rest of induction to 'work' then k has to change. But if k remains 1, then the other problem is that not every number is a 1. If k+1 is proven to work, then the only assumption proven is that 1 and 2 work. But not every number is 1 and 2.

I guess the best way to show me how induction works, is to show me a simple maths equation where induction proved the equation didn't work. Where n = 1 worked, where n = k = 1 worked, but where n = k+1 didn't work. If someone can show me an equation like this, that can be 'un-proven' by induction to work on the rest of the integers, then I think it'd make me understand better, exactly how induction reasoning works.

 

[SoulSearcher]

http://www.purplemath.com/modules/inductn2.htm

 

[live.fast]

Okay, by induction, how would you un-prove this one

(n^3) <= 2(n^2)

because it works for n = 1
1<2

pretend n = k
so it works for one instance of k

and it works for one instance of k+1 (i.e. 2)

8 = 8

But fuks up after.

I guess now its about the methodology, how do you un-prove this by induction?
(i know how to solve it algebraically *duh* but how by induction)

 

[gamecw]

See, I just want to know if anyone else has the same problem accepting the reasoning behind the inductive process. I'll use the domino theory soulsearcher highlighted for me.

1. The first domino will fall.
2. Whenever a domino falls, its next neighbor will also fall.
then you can conclude that all dominoes will fall, and this fact is inevitable.


But with the inductive process, you're assuming a domino (K) will fall, before you're proving its neighbour will fall, right?

So if you're allowed to assume a domino (K) will fall...

Then what's stopping you from assuming that every other single domino is just like another K, and that every other single domino will also fall too?

The assumption step in the inductive process undermines the whole process of PROVING something. Doesn't it?

letin n=k is an essential step of indution, because what we really have to prove in induction is whether n=k+1 is true or not.

but why let n=k, and then prove n=k+1 is true? why dont we just prove n=n+1 is true? well simply because n=n+1 itself is not a true statement. (eg. (1)=(1)+1=2)

so basically, for the second step, we're just substituting another letter with the existing one, ofcouse the statement still holds.