Question

What makes a mathematical induction true? I know how to solve both steps in the proof, but how do you reach this conclusion?

Answer 1

You show that it is true for n=1.

Then you show that if it is true for n=k, then it must also be true for n=k+1.

That means that the assertion is true for all values of n, starting with n=1, and thus for n=2,3,4,...

For instance, a common proof is that the sum of the first n odd numbers is n^2.

1 = 1= 1^2
1+3 = 4 = 2^2
1+3+5 = 9 = 3^2
But we want to show that it is true no matter how many odd numbers we add up.

So, assume it is true for the first k odd numbers:

1+3+5+...+(2k-1) = k^2

Now, assuming that's true, what if we add the next odd number to both sides?

1+3+5+...+(2k-1)+(2k+1) = k^2+2k+1
But notice that the right side is just (k+1)^2

So, what we have shown is that </b>if</b> the sum of the first k odd numbers is k^2, then the sum of the first (k+1) odd numbers is (k+1)^2.

Since it was shown to be true for k=1, it must be true for all values of k.