How did the idea of mathematical induction come about?

Question

and is there any proof of it.

u dont get the question. i mean is there any proof of mathematical induction itself.

Answer 1

Solved the problem of how "to get from here to there." ;-)

There is not a "proof" of induction... it is a *method* used in "proof by induction."

A good analogy is climbing a ladder. If you can show that you can get onto the first rung, and you can show that you can move from one rung to another, then you have demonstrated (proven) that you can climb the whole ladder... by induction.

1575
The first known proof by mathematical induction is included in Francesco Maurolico's Arithmeticorum Libri Duo; he proves that the sum of the first n odd integers is n^2.


Aloha

Answer 2

I believe your question is actually about the validity of induction itself. The proof is really very simple to understand. All you need to consider is the opposite. To illustrate the argument let us consider a property P about natural numbers. In other words, if n is a natural number, then P(n) is either true or false.

If you can prove P by induction, then you must have proved 2 things:

1. P(0) is true. --- this is the base
2. for any n, P(n) implies P(n+1). --- this is the induction step

Suppose now that the induction as a proof method was not correct. This will mean that

a) there is a number m>0 (and m is indeed greater than 0 because we have proved P(0) independently) for which P(m) is false.
b) We have, however proved that for any n, P(n) implies P(n+1).

a) and b) tell us that P must be false for m-1 as well. Now, repeat this argument for m-1 and you will get that P is false for m-2. Run this enough number of times and you will reach the base of the induction, i.e. P(0) must be also false, which is a contradiction resulting from the incorrect assumption that there was m for which P(m) was false. If there is no such m, then P must be true for all numbers.

To add at the very end, this same argument holds not only about properties of natural numbers, but for all well-partial-ordered sets, or wpos. Have a look at http://en.wikipedia.org/wiki/Well_partial_order if you want to know more about wposes.

Answer 3

First think about this question: does every subset of *positive integers* have a smallest element? The intuitive, i.e. obvious, answer is Yes! Induction is another way of interpretting this statement.

Think about what you do when you do an induction proof. You want to show that some property holds for all integers. You start by showing that the property holds for a base case (or two, or three) and then you assume that it holds for some integer. From that assumption, you show that it holds for the next integer. So you show: The property holds for n=1 (and n=2 and n=3 maybe); if a property holds for integers n=1, 2, ..., k, then it holds for n=k+1. In this way you see that the property has to hold for every integer, since you show that it holds for n=1 and this implies it holds for n=2, and this implies that it holds for n=3, and this implies...

Now let's try a different proof strategy. Instead of proving by induction, consider the set of positive integers for which the property does *not* hold. This set has a smallest element, call it k. Here too we'll need to show that the property holds for at least the integer 1. Now try to use the fact that the property fails for k to show that it also fails for some positive integer m
The second strategy is a proof by contradiction. But it gets you to the same place as the induction proof. The idea of the second strategy is clear, it is based on the "obvious" fact that every set of positive integers has a smallest element. But many people don't like contradiction proofs. So if you remove all the negativity in this strategy (think "contrapositive"), you get exactly a proof by induction! In this way, the induction proof is very natural and really just "comes from" the intuitive statement that sets of positive integers have smallest elements.

Answer 4

Yes, mathematical induction is based on propositions. If P(n) is a proposition, then it can be true or false. Now suppose that you have a problem in which you need to show that all propositions P(k) starting with k=1,2,3... are true. You could try each of the propositions from the beginning, i.e. P(1), P(2), P(3), etc but this could take you 'forever' to accomplish. So what you do is assume that it is true for some k, i.e. P(k) is true. Now, if you can show that P(k) implies that P(k+1) is true, then you can say with certainty that all the propositions will be true. Mathematical induction is used in sequential-type problems. It is based on the fact that each proposition supports the following proposition. Here's an example:

Is 0.999... < 1 ?

Well, 0.9 < 1. Is 0.999.....k(times) < 1? Yes. Does 0.999...k(times) < 1 imply that 0.999...k+1(times) < 1? Yes. Therefore 0.999... < 1.

Get the idea?

I strongly suggest you be aware of incorrect advice from firat_c. Mathematical induction does not require showing P(infinity). In fact P(infinity) is not a logical statement. There is no such thing as P(infinity) because infinity is not a number. The whole idea behind mathematical induction is to show that every proposition is true. Does P(infinity) make any sense to you? Does such a proposition even exist? Firat_c needs to be careful about posting nonsense as he has.

The truth of an infinite sequence of propositions P(i) for i=1,2,3... is established if (1) P(1) is true, and (2) P(k) implies P(k+1) for all k.
This principle is known as the method of induction.

firat_c writes:
"The catch is you will have to do this for each n separately, whereas induction allows you to do it simultaneously for all n. I know this may sound rather silly but well this is how it is."

To which I respond: It is silly because it's absolute nonsense. Do not talk about transfinite induction because you don't know what it is and in any case, it does not apply in my example.

Answer 5

the proof is diveded into
1. Scientific proof which is called induction
2. Mathematical or logical proof which is called deduction
3. Statistical proof which deals with the relations which are perfectly related to each other

the induction is to generalizer a certain piece of fact, for example if you heat a piece of metal then it expands, if you heat another then it expands also
if you did heat a piece of metal so many times then you will reach to the fact that the matals expand by heat
mathematically this is not true, because if you did this experiment a million times then it may not expand at the following experiment.
the scientists believe that the fact is true if it is possible to estimste the result of the experiment according to this rule in advance.

the mathematics accepts the induction if it satisfies to condtions:
1. It the statement you need to prove is true at the first treatment to this experiment
2. If there is a certain rule that enables us to prove that: when the statement is true in a certain case it is true for the next case

Under these condition mathematics and logic accepts the truth of this fact.
the quetion now is why math accepts thin induction

the answer is very easy

Suppose you did the experiment a lot of times
let the statement P(n) means that the experiment is true at the nth trial:

According to the mathematical induction the experiment is true when
1. P(1)
2. P(n) leads to P(n+1)

Now let us examine the two conditions together

by putting n = 1 in the second condition
you see that:

P(1) leads to P(2) which means that the experiment in true at n = 2
Now P(2) is true

So by the second condition we get
P(2) leads to P(3) which means that the experiment in true at n = 3

Similarly
P(3) leads to P(4)
P(4) leads to P(5)
and so on
that means that the second condition will automatically lead us to the next experiment up to infinite number of times

Answer 6

Be aware of the bad mathematical advice going on in this forum. There is a very big mistake in the supposed proof by induction above by Tom. Ordinary induction (as opposed to the transfinite induction) proves a property P(n) for each n by showing that if P(0) holds and if P(n) holds so does P(n+1). So at once you establish that P(1), P(2),...,P(n),... However it does not show that P(infinity) holds. Here is another example for the consequences of the misuse of induction by Tom:
Set A0=0 and An=1+1+...+1 (n times) =n
Let P(n) be the property which says An is a finite number. Then we have P(0) to be true as A0=0 is a finite number and we also have that if P(n) holds An is a finite number, any finite number plus one is a finite number, and therefore A(n+1) is a finite number and therefore P(n+1) holds. This shows that for any n An is a finite number, however P(infinity) which states that
1+1+1+....(infinitely many times)
is a finite number is not true, obviously.
If you are interested in transfinite induction, you may want to read an elementary set theory book where ordinal numbers are discussed.
As for the origin of the method I vaguely remember reading something like the infinite descent method being used by ancient greeks, possibly by Archimedes. Infinite descent is a rough version of mathematical induction which relies on the same principle. However I am not quite sure about this and I would not bet on it. Just something for you to check out.

Edit: As for the proof of mathematical induction, there exists one and there does not exist one at the same time. Here is the thing, there is a proof of the mathematical induction in set theory. However as mathematical logic freely uses mathematical induction in foundations of set theory this is really not exactly a proof. In a sense induction is one of the axioms of metamathematics. On the other hand it is not that much of a thing which requires a proof. If you can prove that P(n) holds for all n by induction, then given any n you can also give a proof that P(n) holds without using any induction. The catch is you will have to do this for each n separately, whereas induction allows you to do it simultaneously for all n. I know this may sound rather silly but well this is how it is.

TOM: I will give you the benefit of doubt and will try to explain why you are wrong with your induction proof once again. I am not optimistic that you will have the humility to read and understand what I am going to say but there is enough ignorance going on around that it would be a great disservice to society to just watch you spread more of it.

Your proof of 0.9999...<1 is wrong, why? You take the property P(n) which says
0.9999 (n) times < 1
and you correctly use induction to prove P(n) holds for each n. BUT at the end you state that by induction you have proved
0.999999......(infinitely many times) <1.
That is COMPLETELY WRONG. What you state at the end to have proved is P(infinity), which ordinary induction can not prove. What you showed is for ANY n
0.9999 (n times) <1 holds, nothing more. IF you are under the misconception that showing
0.9<1, 0.99<1, 0.999<1,...
is the same thing as showing
0.9999...<1,
That is also very WRONG. See then I can prove that
1+1+1+1...
is finite as 1 is finite and 1+1 is finite and .... or prove that each line segment is of infinite length:
Take [0,1], divide it into 2, and 4, and 8.... at each step the line segments are of positive length. SO at the end we end with infinitely many pieces of a line segment with positive length. But then the whole [0,1] has length infinity. Or we can prove that Pi is a rational number as so are 3, 3.1, 3.14, 3.141,.....
I can make tons of examples like this, but the problem is can you shut your ego and listen for a minute?

And by the way P(any ordinal) makes perfect sense in set theory. Please stop confusing people around, they are having trouble understanding math already. They don't need you teach them misconceptions.

Answer 7

There very definitely IS a proof FOR mathematical induction! It is a method of proof itself, of course, but the method too is supported by proof. The proof for M.I. is commonly something pure maths undergraduates would encounter early in their degree studies.
As for FiratC's transfinite induction, I suggest you ignore this since you've already established that the process works indefinitely far, and the idea of an 'infinite number', which itself requires a deep breath and a lot of axioms to establish what you mean by such a thing, leads into more abstruse and esoteric areas of pure mathematics.

Answer 8

It just seemed like a pretty kewl way to prove something was true for all possible values of an index variable.

The 'proof' of induction is buried in Peano's Postulates. But you can get there with a bit of set theoretic logic and some horse-sense.


Doug

Answer 9

while trying to offer rigid mathematical proofs to seemingly obvious formulas mathematical induction was resorted to

Answer 10

I have seen examples of induction in the work of Pascal and Euler. It seems to have emerged in number theory--where patterns are codified into formulas, and then algebra on the formulas proves things.