induction

[richardt]

According to every reference I have read, the principle of mathematical induction refers specifically to the natural numbers. Is there any reason why I cannot use induction to prove a statement true for all negative integers?...or for all integers for that matter? For instance, if S_n denotes a statement about some integer, n, such that S_-1 is true, and S_k-1 is true whenever S_k is true, k < or = -1, does it not necessarily follow that S_n is true for all negative integers, n?

Thank you.
Rich B.

 

[stapel]

According to every reference I have read, the principle of mathematical induction refers specifically to the natural numbers. Is there any reason why I cannot use induction to prove a statement true for all negative integers?...or for all integers for that matter?

For all negative integers, do the proof for all positive integers, but use a "minus" sign. That is, instead of making a statement about "n, for n a natural number", make the statement about "-n, for n a natural number".

How do you propose to use induction for "all integers", considering that the heart of induction is that one starts at some beginning and then goes on in one direction "to infinity"?

 

[richardt]

Greetings stapel: Your response makes great sense. Regarding the proof of S_n for all integers, I intend to approach via three cases as follows, namely, S_o true, S_j true for all j > 0, and S_k true for all k < 0, where the latter two cases shall entail separate inductive "sub-proofs". Moreover, as I now know, in the final case I will actually demonstrate S_-k true for all integers, k > 0.

From this, it will follow that S_n true for all integers, n. How's that?

Thanks again.
Rich

 

[HallsofIvy]

Do you know the word "countable"? A set, A, is said to be "countable" if there exist an invertible (one-to-one and onto) function, f, from the positive integers to the set: for every positive integer, n, there is a unique x in A such that f(n)= x and for every x in A there exist a unique positive integer such that f(n)= x. We can apply "proof by induction" to any statement about members of a countable set by creating such a function and apply induction to the positive integers such that f(n)= x and f(n+1)= y.

We can show that the set of "all integers" is countable by f(0)= 0, f(2n)= n, f(2n+ 1)= -n. That is, if n is 0, f(n)= 0; if n is even, n= 2k, then f(n)= k, a positive integer, and if n is odd, n= 2k+ 1, f(n)= -k, a negative integer. We can prove any statement on all integers by using induction on the corresponding positive integer.

In fact, the set of all rational numbers is countable although there is no simple way to write the function "f":
http://www.homeschoolmath.net/teaching/rational-numbers-countable.php

We can, in that sense, apply "proof by induction" to statements about rational numbers.

 

[richardt]

Thank you kindly, HallsofIvy. Yes, I am indeed familiar with Cantor's work and I do believe I will utilize your suggestion. It seems to promise a much more succinct, elegant proof than three separate cases, two of which are inductive. Okay, enjoy the day.

Rich