I'm new to math. I'm learning about set theory. The book I'm reading (Schaum's Outline of Set Theory) covers mathematical induction. The book uses a common illustration and a common example (I could only find the same illustration and example when I searched on-line) to illustrate how mathematical induction works.
Illustration: "...it is like a row of standing dominoes. First, demonstrate that one standing domino falls after it is pushed. Second, demonstrate that pushing over one standing domino will knock down the second. Essentially, that proves that a row of standing dominoes will fall if the first is pushed." (taken from decodedscience.com)
"(1) 1 + 3 + 5 + ... + (2n - 1) = n^2
(2) If x_1, x_2, ..., x_n > 0 then (x_1 + x_2 + ... + x_n)/n ≥ (x1·x2·...·xn)^1/n etc.
n here is an "arbitrary" integer.
It's convenient to talk about a statement P(n). For (1), P(1) says that 1 = 12 which is incidently true. P(2) says that 1 + 3 = 22, P(3) means that 1 + 3 + 5 = 32. And so on. These particular cases are obtained by substituting specific values 1, 2, 3 for n into P(n)." (Taken from cut-the-knot.org)
What I Understand:
I know that Mathematical Induction and The Other Induction are different. I know that they are both about drawing conclusions about the general by examining the specific.
Intuitively, I can see that in the universe of math, where we have the advantage of a 'bottom-up' understanding of the laws of the universe, we can employ induction reliably
I understand that the above equations tell us that the value of a set of odd integers is equal to the square of the set's cardinal. E.g., 1+3+5 = 9. Cardinal of 3. 3^2=9.
I can see that you could apply this along the whole continuum of odd integers.
What I Don't Understand:
I don't see why those equations were used to illustrate mathematical induction. I know little about proofs, but I believe those equations are examples and not proofs. In that case, would it not have been sufficient, but trivial, to use an example like, 'an integer is always one integer greater than the integer that preceded it' n ≺ n+1
Those equations are used everywhere to illustrate mathematical induction. Nobody uses the example I just provided. So I'm assuming there is something more valuable in those equations than in my example. What is it?
I thought of some scenarios where (my understanding of) mathematical induction would be misleading. For instance, if I said that 'a prime number will be one integer greater than the prime that preceded it.' That works for the first two prime numbers (2,3), So haven't we illustrated that if you push one domino you will cause it to fall which will cause the next domino to fall...? (But in this case, the second domino will not cause the third domino to fall)
As far as I (wrongly) understand: Mathematical induction is saying that, 'you can know the infinitely applicable relationship between an input and an output, so long as you have two sets of input and output from the same continuum.'
What am I misunderstanding? Thank you for your help.
P(1) is true
If P(*n*) is true for any n, then P(n+1)
I think that I see what I missed.
- "P(1) is true," is A
- "P(n) is true, for any n" is B
- "P(n +1) is true," is C
I thought that what you wrote meant: (A&B)->C
In words (I may have mucked up the notation): If P(1) is true; and any P(n) is true, for any n; then P(n +1). In other words: That so long as you have P(1), then for any n for which P(n) is true, you also know that the next n is true (i.e., P(n + 1)). Since the 'next n' (i.e., P(n + 1)) is true, you have another 'any n for which P(n) is true';and you can know that the n following it (i.e., P(n + 2))is also true... and you could continue this forever; thus replicating the 'domino' effect.
However, it seemed to me that it would also be possible where one could find some properties of the natural numbers for which P(1) is true, and then check that property on any other number, and by coincidence, that property may appear to be true. One would then have satisfied "P(1) is true,", and "P(n) is true, for any n"; in which case, mathematical induction would mislead one to believe that P(n) was true for all natural numbers.
I think that I should have understood that it meant: (A&(B->C))<-> 'P(n) is true for all natural numbers'.
- 'If P(1)' is true.
- And if it is also true that P(n + 1) is always true whenever 'P(n) is true, for any n'
- Only then and always then, can we say for certain that P(n) is true for all natural numbers.
I'm still curious, how "P(n + 1) is always true whenever 'P(n) is true, for any n'", without having to rely on 'evidence' (since now amount of evidence forms a proof). Is there something about mathematical induction that allows one to prove that, - or is another technique used to prove that it is true that "P(n + 1) is always true whenever 'P(n) is true, for any n'"?