Thread: Induction

I feel like I really need a lesson on mathematical induction. I tried it once and failed miserably. I understand the idea but I can't do it right. I've seen it in the case of proving that and things like that. However I'm clueless when it comes to proving things where you have, say the objects and have to use it on to prove that something works for objects. I have to use induction for the proof I'm currently working on, but I want to be able to do it myself so I'm not posting that problem here. Any help would be appreciated.

The basic idea is to determine if a proposition about something which depends on integers holds for all integers (n). The approach has two basic steps:
1) Show that the proposition holds for n=1.
2) Assume that the proposition is true for n=k. Show that the proposition then holds for n=k+1.

The idea behind it is that once you have carried out step one, you know that the proposition holds for n=1. Step 2 then implies that it therefore holds for n=2, and therefore it holds for n=3, and therefore it holds for n=4, etc.

Originally Posted by Chemboy

I feel like I really need a lesson on mathematical induction. I tried it once and failed miserably. I understand the idea but I can't do it right. I've seen it in the case of proving that and things like that. However I'm clueless when it comes to proving things where you have, say the objects and have to use it on to prove that something works for objects. I have to use induction for the proof I'm currently working on, but I want to be able to do it myself so I'm not posting that problem here. Any help would be appreciated.

It is not clear from you post just what the problem is. Here is a link to a proof by induction of a formula for the first n cubes in another thread. Take a look at that proof and see if it helps you understand the basic process.

http://www.thescienceforum.com/viewt...r=asc&start=45

I understand it there where you have s in a formula. What I don't understand is how you work with it when the is in a subscript or something.

Originally Posted by Chemboy

I understand it there where you have s in a formula. What I don't understand is how you work with it when the is in a subscript or something.

I think you need to show us an example of such a proof that is giving you trouble.

...Bearing in mind that I, as an interested outsider, am still of the opinion that Induction cannot work with regard to any series except one consisting of whole numbers. Or is this a false notion?

Originally Posted by sunshinewarrior

...Bearing in mind that I, as an interested outsider, am still of the opinion that Induction cannot work with regard to any series except one consisting of whole numbers. Or is this a false notion?

The terms in the sequence are not necessarily integers. However each term is dependent on an integer and succeeding terms depend on succeeding integers.

induction is used on orderd sequences, that is, sequences with numbered terms, where those numbers must be integers, or, more commonly, natural numbers

Originally Posted by sunshinewarrior

...Bearing in mind that I, as an interested outsider, am still of the opinion that Induction cannot work with regard to any series except one consisting of whole numbers. Or is this a false notion?

Induction is a means of proof for statements involving the natural numbers, independent of how the natural numbers are involved. The principle is very simple -- if a set of natural numbers contains a natural number K, and if whenever it contains a natural number n it also containse its successor (n+1), then that set contains all natural numbers greater than or equal to K.

Most commonly you have a statement A(n) which makes an assertion regarding the natural number n. You wish to prove that A(n) is true for all n. So first you show that A(1) is true. Then you show that if A(n) is true that it logically follows that A(n+1) is true. You then conclude that A(n) is true for all natural numbers n.

Originally Posted by DrRocket

Originally Posted by sunshinewarrior

...Bearing in mind that I, as an interested outsider, am still of the opinion that Induction cannot work with regard to any series except one consisting of whole numbers. Or is this a false notion?

Induction is a means of proof for statements involving the natural numbers, independent of how the natural numbers are involved. The principle is very simple -- if a set of natural numbers contains a natural number K, and if whenever it contains a natural number n it also containse its successor (n+1), then that set contains all natural numbers greater than or equal to K.

Most commonly you have a statement A(n) which makes an assertion regarding the natural number n. You wish to prove that A(n) is true for all n. So first you show that A(1) is true. Then you show that if A(n) is true that it logically follows that A(n+1) is true. You then conclude that A(n) is true for all natural numbers n.

That's what I thought - but couldn't put into words as well as you guys.

Thanks.

Originally Posted by Chemboy

I feel like I really need a lesson on mathematical induction. I tried it once and failed miserably. I understand the idea but I can't do it right. I've seen it in the case of proving that and things like that. However I'm clueless when it comes to proving things where you have, say the objects and have to use it on to prove that something works for objects. I have to use induction for the proof I'm currently working on, but I want to be able to do it myself so I'm not posting that problem here. Any help would be appreciated.

From these various postings it seems to me that it can only work on your set of objects if there is a rule regarding them such that a relationship can be mathematically formulated between and .

Is this the case in the problem on which you're working?

No, I don't think it is. Unfortunately the only example I have is the problem I'm trying to do, which I want to do myself.

you can only do it if you can establish a mathematical relation between all of the members of your sequence. i.e. there must be some rule that the nth term follows.

Ummm,

Every uncountable set has at least one countable proper subset. So we know that is uncountable, then is countable, say. . But "countable" means a bijection from the natural numbers to , say ,

Then since there is a natural ordering on this induces an ordering on such that, for any there will always be some . (This is true, of course, for any subset of )

Induction would fail should this not be true.

Originally Posted by Chemboy

No, I don't think it is. Unfortunately the only example I have is the problem I'm trying to do, which I want to do myself.

If there is no relationship that you can clearly formulate relating to then you may dealing with a proof that is not amenable to the technique of induction.

Do you have some reason to believe that induction is the right tool for your problem ?

The author says it is. haha. I'll look at it more closely though when I'm able.

Originally Posted by Chemboy

No, I don't think it is. Unfortunately the only example I have is the problem I'm trying to do, which I want to do myself.

Say what, post your problem, and I will do my best to ensure that nobody does it for you, at least not for your eyes. No guarantees (because of time zones)

To all: Should Chemboy decide to post his problem, I hope we all here will respect his wish, namely that he wants to solve it himself.

Originally Posted by Guitarist

To all: Should Chemboy decide to post his problem, I hope we all here will respect his wish, namely that he wants to solve it himself.

Agreed

Thank you very much Guitarist and DrRocket, I appreciate it.

Let be positive real numbers. Prove that if , then , where equality occurs iff .

The case for 1 I think is trivial, and I can show it for 2 (that was problem #6, this is #7).

The hint in the book says "Use induction and Problem 6."

Originally Posted by Chemboy

Thank you very much Guitarist and DrRocket, I appreciate it.

Let be positive real numbers. Prove that if , then , where equality occurs iff .

The case for 1 I think is trivial, and I can show it for 2 (that was problem #6, this is #7).

The hint in the book says "Use induction and Problem 6."

It is possible to prove that theorem by induction.

If you will give me your permission, I will give you a one-line hint (with no mathematical symbols) that might help you just a little, merely pointing out the potential usefulness of some things that I know that you already know.

Sure, go ahead. I just don't want the whole thing given away, or enough information to make it obvious.

Originally Posted by Chemboy

Sure, go ahead. I just don't want the whole thing given away, or enough information to make it obvious.

OK use the associative property of multiplication and the results for the case n=2 from your exercise 6.

May I ask a question for explication? I don't believe it has anything to do with the solution (the Proof using Induction), but it will help me grasp the problem better.

Would that be ok?

Examples of induction using the well-ordering of the natural numbers:

Theorem: Every dog has his day.

proof: Suppose that some dog did not have his day. Call that dog D. Without loss of generality, we may assume that D is the first dog who did not have his day. But then today is the day for that unique dog. Contradiction.

Theorem: Every positive integer is special.

proof: Suppose not. Let N be the least positive integer which is not special. That sounds like a pretty special quality to me. Contradiction.

I would have never thought to use induction that way... very nice use of the concept on rather abstract ideas

Originally Posted by sunshinewarrior

May I ask a question for explication? I don't believe it has anything to do with the solution (the Proof using Induction), but it will help me grasp the problem better.

Would that be ok?

You can ask anything that you want to ask. It is, after all, your problem that we are addressing. You get to make the rules here.


Edit: Oops -- I lost track of the source of the question. I was addressing Chemboy, but sunshinewarrior asked the question.

Originally Posted by sunshinewarrior

May I ask a question for explication? I don't believe it has anything to do with the solution (the Proof using Induction), but it will help me grasp the problem better.

Would that be ok?

Yep, go for it. Maybe if the answer would be too revealing the reply could be via PM?

Thanks.

The question was this:

Are we allowed to assume that the value of is the same for every value of ?

Or are we even to take that the value of will differ depending upon the value of ? (Or in other terms, the sets defined by values of are not necessarily proper subsets of those defined by the higher values of .)

Does this question make sense?

looking at his problem, it looks as if each member of the sequence is equivalent to every other member, and is equal to 1. so it doesn't matter what n is: for all n

No. It just says that that's the only way is true.

can you post your proof for the case n=2?

Originally Posted by Chemboy

No. It just says that that's the only way is true.

That's what I assumed - but do you have an idea how my question should be tackled? Unique s or varying?

That response was just to Arcane... I would think the s can vary. No reason to think they can't, really.

Originally Posted by sunshinewarrior

Originally Posted by Chemboy

No. It just says that that's the only way is true.

That's what I assumed - but do you have an idea how my question should be tackled? Unique s or varying?

The s are permitted but not required to vary. If they do not vary then the theorem is trivial, since the fact their product is zero would then imply that they would all be 1, since they are positive by hypothesis.

I suspect part of the problem here is in the index notation. Here, refers to the number of factors in the product, and hence to the same number of terms in the sum. It is a positive integer. That is is the "last" factor or term in a string that is precisely factors/terms long.

If we wish to refer to a particular factor or term, it would be better to use . This means that is integer, but does not mean that is integer, and in general will not be

So yes, for any we may have that , but for full generality it would better not to assume so.

Actually, unless I have misunderstood the problem, it is quite straightforward. But, since the reals comprise rationals, irrationals and transcendentals, the only way through is by abstraction; that is, don't attempt to use "actual" reals. As far as I can see it, this part of the object of the exercise.

But then, what do I know?

Originally Posted by DrRocket

OK use the associative property of multiplication...

Aarg, that sounds like something you'd see in a Hungerford textbook.

So. I haven't been able to put an awful lot of time into this, unfortunately. For the case the elements have to be an and a . Can I do the same thing with elements, and call the first elements and the th element ? And then can I do the same thing as when I showed that the case is true? (of course I haven't shown that, but I'm sure you know it)

Originally Posted by Chemboy

So. I haven't been able to put an awful lot of time into this, unfortunately. For the case the elements have to be an and a . Can I do the same thing with elements, and call the first elements and the th element ? And then can I do the same thing as when I showed that the case is true? (of course I haven't shown that, but I'm sure you know it)

I don't quite follow your question, but I think the answer is "no."

The case n=2 actually takes some work. It does not follow, at least as far as I can see, from the case n=1. The case n=1 is trivial. The case n=2 is not so trivial and is the key to the remainder of the proof by induction. That in no way is meant to imply that the inductive step in any way resembles the proof for n=2.

This is not a stupendously difficult proof (Wiles's proof of Fermat's Last Theorem was stupendously difficult) but it is not trivial either. It is not so straightforward as the typical proofs by induction that one sees in school classes that are designed to simply provide a little exposure to inductive proofs. This one takes some thought and some work, and is not just pushing symbols.

Keep plugging away. This is a good exercise.

At chemboy's request here is a proof by induction of the theorem being discussed. I have not polished this presentation so there may well be a more elegant proof. Also beware of typos, there are undoubtedly a few.

Theorem: Let with for all i=1,2,...n for some natural number n. Suppose that
. Then



and equality holds if and only if

Proof

a) If n=1 the theorem is obvious

b) Suppose that n=2

so

Hence



Now let for . Then and if and only if . From this and inspection of it follows immediately that has a minimum at 1 and .

This proves the theorem in the case n=2.

c) Now assume inductively that the theorem is true for all for some

Then we have as our hypothesis for the theorem that

.

Without loss of generality we may assume (re-ording the if necessary) that



By the inductive hypothesis, treating as a single term



which becomes




Consider now the function for and . We claim that with equality if and only if

The claim follows from observing that ,

and the theorem follows as well.

QED

Edit: 1) A simpler proof of the case n=2 follows from the observation that the statement is equivalent to the statement that which is clear for

2) The case n=2 is not really needed in the step c) and one can dispense with it, simply assuming then that

Absolutely never would have gotten that. I was nowhere close.

For I said




which is obviously true.

I guess that's closer to what you had in your edit.

So now I won't waste any more time on trying to do that, and I've learned a new trick for proofs involving or type requirements: use derivatives.

Fair enough, but just for the masochism of being publicly humiliated, I will post what I thought was a "proof".

Base case is . Notice first that for any then can only be true when .

Since , then for any that . Moreover, for any there is nothing to prove, since then by necessity.

So consider that . Again, and

But if obviously , so clearly from the above.

Base case "proved".

Assume that . Here we must assume that,either each is one - to- one paired with its inverse, or that mutual inverses can be found by factoring as appropriate (recalling that is arbitrary). Call this sum as .

Then the case for is trivial - if and , then .

Consider the case of . Since this product must be unity, from the base case we must have that , then

I made it as far as getting the base case of 2 down, couldn't get a handle on the induction part.

Wow.

Followed some of it.

Originally Posted by DrRocket

By the inductive hypothesis, treating as a single term

Couldn't understand how you're allowed to do this. How can the product of those two be used in a sum?

Is this a silly question?

Originally Posted by sunshinewarrior

Wow.

Followed some of it.

Originally Posted by DrRocket

By the inductive hypothesis, treating as a single term

Couldn't understand how you're allowed to do this. How can the product of those two be used in a sum?

Is this a silly question?

It is simply treated as a single term, reducing the number of terms being considered to k which is covered by the inductive hypothesis.

What allows me to do it is the associative property of multiplication.

Originally Posted by DrRocket

Originally Posted by sunshinewarrior

Wow.

Followed some of it.

Originally Posted by DrRocket

By the inductive hypothesis, treating as a single term

Couldn't understand how you're allowed to do this. How can the product of those two be used in a sum?

Is this a silly question?

It is simply treated as a single term, reducing the number of terms being considered to k which is covered by the inductive hypothesis.

What allows me to do it is the associative property of multiplication.

I think I've got it. But it's at the limit of my capacities, alas.

Thanks ever so much for that.