Thread: Need straightened out on some mathematical induction thoughts

Need straightened out on some mathematical induction thoughts. OK I'm given an equation or series whose right side is supposed to equal its left side for all the positive numbers from 1 to infinity. Its easy enough to show that it works for x=1. Now the questionable part. I assume it is true for some x = k and write the equation using k for the variable symbol. Then I a let k become 1+k, substitute that new number into the same suspicious equation that works for k=1, perform some algebraic magic and low and behold the final equation "looks" exactly like the original one with all the k's now k+1. Just how is that a proof? The final equation looks as suspicious as the first one. Thanks, confused in Ohio.

Originally Posted by Larry

Need straightened out on some mathematical induction thoughts. OK I'm given an equation or series whose right side is supposed to equal its left side for all the positive numbers from 1 to infinity. Its easy enough to show that it works for x=1. Now the questionable part. I assume it is true for some x = k and write the equation using k for the variable symbol. Then I a let k become 1+k, substitute that new number into the same suspicious equation that works for k=1, perform some algebraic magic and low and behold the final equation "looks" exactly like the original one with all the k's now k+1. Just how is that a proof? The final equation looks as suspicious as the first one. Thanks, confused in Ohio.

The principle of mathematical induction works like a set of dominoes lined up. It's known that any domino will push the next one over, as long as the first one is pushed.

Mathematically speaking, if we can show a statement is true for a base case (pushing the first domino), and also show that the truth of the statement for an arbitrary value IMPLIES the truth of the next value (any domino pushing the next one over), then we prove the statement is true for all cases, because we know that this implication means that the first being true implies the second is true, the second being true implies the third is true, the third being true implies the fourth is true, and so on.

Does that make more sense?

Originally Posted by Larry

Then I a let k become 1+k, substitute that new number into the same suspicious equation that works for k=1, perform some algebraic magic and low and behold the final equation "looks" exactly like the original one with all the k's now k+1. Just how is that a proof? The final equation looks as suspicious as the first one.

Suppose you need to prove f(n) = g(n) for all integers n >= 1. As you said, you first prove the base case f(1) = g(1). Then you proceed with the induction step by fixing an arbitrary k and assuming f(k) = g(k). From your post, it seems that after substituting n = k + 1 and doing some algebra, you get f(k + 1) = g(k + 1). This is strange because this is what you get immediately after substituting n = k + 1, without any algebra. And, yes, this is not the end of the proof. What you need to show is that f(k) = g(k) implies f(k + 1) = g(k + 1), i.e., that f(k + 1) = g(k + 1) holds under the assumption f(k) = g(k). This implication f(k) = g(k) => f(k + 1) = g(k + 1) should work for an arbitrary k. Thus, the induction step comprises an infinite number of implications: f(1) = g(1) => f(2) = g(2), f(2) = g(2) => f(3) = g(3), etc.

This way, you proved f(1) = g(1) and f(1) = g(1) => f(2) = g(2), which means that f(2) = g(2) is also proved. Next, f(2) = g(2) and f(2) = g(2) => f(3) = g(3) gives f(3) = g(3), and so on.

"Then I let k become 1+k, substitute that new number into the same suspicious equation that works for k=1, perform some algebraic magic and low and behold the final equation "looks" exactly like the original one with all the k's now k+1."
I have no clue what this means. You do have to show that the equation you are trying to prove (I assume you that's what you mean by "the same suspicious equation that works for k=1") and do whatever algebra is necessary to reduce it to a similar formula (NOT "exactly like the original one with all the k's now k+1". If I understand what you mean by that that's the wrong way) involving k to show that "if the formula is correct for k then it is also true for k+ 1".

For example, to show that , we first show that the statement is true for n=1, just as you say. Typically, that is very easy, as it is here. With n= 1 the left side is just 1 itself. The right side is 1(1+1)/2= 2/2= 1. Yes, those are equal.

Now, we want to show that the formula works for n= k+ 1. I won't just write that formula with k+1 instead of n, because I don't know that it is true. I can say that . Now, from that, I can say that . Now that "algebraic magic" (also known as the "laws of arithmetic") is just adding fractions. Since one fraction has denominator "2" and the other has denominator "1" The common denominator is 2 so getting common denominators, . And now one more step of "algebraic magic"- factor that numerator. That's made easier by the fact that we know what we want to get so we just need to check that it is true: which is just " " with n= k+1.


This shows two things: first that the statement is true when n= 1, second that if it is true for n= k, it is also true for n= k+1. Okay, since it is true for n= k= 1, it is also true for n= k+1= 1+ 1= 2. Since it is true for n= k= 2, it is also true for n= k+1= 2+1= 3. Since it is true for n= k= 3, it is also true for n= k+1= 3+ 1= 4, etc.

Thanks so much. My hang-up was that after showing it had the same shape, size, etc. as the original equation, but now for k+1, I had just generated a new equation that needed as much proof as the first one. I felt the process was somehow incomplete, that now I needed to prove that the new equation was true and so on, for k+2, etc. Didn't realize that when that 2nd domino fell, it is true that all the others must fall. So all that infinite amount of proving is unnecessary. I've never seen an algebra book chapter on induction state it this way. Probably been reading the wrong books. I remember my HS algebra instructor dismissing the entire section on mathematical induction by saying, we will skip this because you wouldn't understand it anyway. And that was 50 years ago. I've been trying to understand it off and on for years! Think I'm finally catching on. Now I'm almost ready for a shorter proof of Fermat's Last!


=1 equation

Oh, My God! What have we done?

Actually the best, easy to understand answer I got was yesterday from a Yahoo Answer It page:

.........The "basic step" establishes that the equation is valid when x=1 (or some other number, depending on the specific case, but x=1 is the most common example).

Now the "induction step": We establish that,
IF the equation is true for some x=k,
THEN it is also true for x=k+1.

Our induction step proves that if it holds for x=1, then it holds for x=1+1=2.
And that if it holds for x=2, then it holds for x=2+1=3.
And that if holds for x=3, then it holds for x=3+1=4.
And so on, until we get to x=any positive integer we want.

To follow this line of reasoning out to x=3,517,645,032, we would have to apply the result of the induction step 3,517,645,031 times. We wouldn't live that long. However, we don't have any problem seeing that we COULD, if we lived long enough, do just that--and the result would be valid. In fact, we can see that the result would be valid for ANY positive integer x, and if we can see that, we don't actually need to carry out the separate applications at all, because the purpose of the proof is to demonstrate that the equation is valid. That's what makes mathematical induction so cool: knowing what it allows you to do saves you from having to do it. We get an infinite set of specific examples all together, and we only have to unwrap and apply the ones we want.

The underlined statement made it all clear to me. Odd that it took so many years to realize that showing that something is possible is as good as actually doing it. Too many years as a "do it" engineer, rather than a theoretician has poisenned my mind.

Well, that's essentially what I and emakarov said and what Prove It meant with his reference to "dominoes".

Originally Posted by Larry

we don't actually need to carry out the separate applications at all, because the purpose of the proof is to demonstrate that the equation is valid. That's what makes mathematical induction so cool: knowing what it allows you to do saves you from having to do it. We get an infinite set of specific examples all together, and we only have to unwrap and apply the ones we want

Using the proof-as-programs correspondence, which is an interesting topic in mathematical logic, proving an equation by induction is like writing a program that takes n as input and uses a loop to construct evidence for the nth instance of the equation. As soon as there is a program, we consider all instances if the equations proved. If we wanted, we could feed this program a specific n, wait for the loop to unwrap itself, and eventually get an induction-free evidence for the nth instance of the equation.

I realize that finding my...."knowing what it allows you to do it saves you from having to do it"......was given implicitly in all your explanations. But seeing those exact words turned on the light and enabled me to appreciate fully all your responses. Again, I thank everyone for taking the time to help. Gees where was this nice group when I needed it back in the 1960's! Today's learners are indeed fortunate to have you folks.