Mathematical induction

[Primarygun]

For what reason, the induction only can be used to prove natural numbers n(but not negative numbers?)?

How to guess the formula of a sum of a sequence of number?

[Woxor]

It actually can be used to prove things about negative numbers. The reason that you learn it with only the natural numbers is that the natural numbers are intuitive and easy to work with.

 

Furthermore, any set where induction can be applied can be thought of as "equivalent" in some way to the natural numbers. If you want to think in terms of "how many" numbers are in the set, the natural numbers are considered to be "countably infinite," which is opposed to, for example, the "uncountable" real numbers. Any set where normal mathematical induction applies, so far as I understand it, must be countable.

 

The reason it must be countable is that induction relies on the enumeration of the elements in the set; that is, you have to take them one at a time and still be able to prove that all of them are accounted for somewhere in the sequence. No one has ever discovered a way to do this with real numbers, and in fact it has been proven impossible given our current formulation of mathematics.

 

Now, as for how you can apply it to negative numbers: you do it mostly the same way. Start with, say, n=0 or something, and prove S(0). Then show that S(k) implies S(k-1) (instead of showing that S(k) implies S(k+1), as you do for natural numbers). By this, you can prove S(n) for all n <= 0.

 

I like to think of induction as the process of finding a starting point in the set of numbers you're working with and then showing that you can "move" all the way through the set with your theorem holding true. Using it on negative numbers is just the process of showing that you can "move" backwards in this way.

 

Regarding your second question: it's pretty tough. There's not a perfectly standardized way to find the formula for a given series (which is what we call the sum of a sequence). Others probably know much more about it than I do, but to the best of my knowledge, we rely heavily on intuition. There are a few theorems that apply generally, but almost all of them check for whether the sum converges (i.e. whether it keeps from shooting off to infinity) rather than what it actually converges to.

 

EDIT: I don't want to be overly confusing, but I don't doubt that there is a form of induction applicable to uncountable sets. For example, you could prove something for the positive real numbers by proving S(0) and then showing that x < y implies that S(x) implies S(y). I don't know how useful this method is, though, and it's probably not called "induction." If this edit is confusing, feel free to ignore it.

[matt grime]

Semantically: induction does not prove anything about the natural numbers necessarily. It is used to prove things about any well ordered (countable) set of statements. Usually that list is indexed explicitly and obviously by the natural numbers, but the result doesn't have to say anything about natural numbers.

 

As it is any countably infinite well ordered set that you need to use at this stage is canonically isomporphic, as an ordinal, to the natural numbers, which is why it almost always appears to use the natural numbers. The negatives. with the obvious ordering are isomorphic to N with its ordering via x sent to -x.

 

Infinite sets of greater cardinality may indeed be used to prove statements inductively. This is so called transfinite induction, and is most inelegant, and would require too much of an explanation of uncountable ordinals to be of any use at the level where you're first using induction. Indeed I can't think of any place where you'd need to use it before graduate level mathematics.

[matt grime]

http://www.dpmms.cam.ac.uk/~wtg10/ordinals.html

 

there's a page with some uses of transfinite induction to prove statements you already know (and some you won't). Note, these proofs are pedagigical in nature. The usual proofs are much easier to understand.