You are invited to Log in or Register a free Frihost Account!

# Math Induction?

gverutes
I am tutoring a student on PreCalc and he is learning about a process called Math Induction. Can someone offer any background on how this works? Practice problems would be helpful!

I have looked at Wikipedia, but the explanation is kind of convoluted.

Thanks,
G
infinisa
Hi gverutes

Mathematical Induction is basically recognising a pattern, saying "and so on", and then proving why.

For instance, if I add the first odd numbers:

1 = 1
1+3 = 4
1+3+5 = 9

I notice a pattern: the sum seems to be a square:

1 = 1^2
1+3 = 2^2
1+3+5 = 3^2
and so on...

The problem is, the "and so on" includes infinitely many cases, so how can I give a Mathematical Proof?

The solution is to use Mathematical Induction

In this case, the general rule I'm trying to prove is:

1 + 3 + ... + (2n-1) = n^2 for n= 1, 2, 3, ...

I've already checked it above for the first few cases (n=1 to 3)

The trick is to show that each line leads to the next:
e.g. to get from
1+3+5 = 3^2
to
1+3+5+7 = 4^2
just add 7 to each side

In the general case, if we've checked up to n=k
i.e. we've shown
1 + 3 + ... + (2n-1) = n^2
for n = 1, 2, ..., k
we need to check for n=k+1, which would be:
1 + 3 + ... + (2(k+1)-1) = (k+1)^2
i.e.
1 + 3 + ... + (2k+1) = (k+1)^2

Well, we have (for n=k):
1 + 3 + ... + (2k-1) = k^2
Add the next odd number, 2k+1 to each side:
1 + 3 + ... + (2k-1)+(2k+1) = k^2 + (2k+1)
so we have
1 + 3 + ... + (2k-1)+(2k+1) = (k+1)^2
[since (k+1)^2 = k^2 + 2k + 1]
and so we have proved the result for n=k+1

So we've shown it's true for for n = 1, 2, ..., k, k+1

Now, by repeating the same argument that each line leads to the next, we've shown it's true for all values of n.

gverutes
Very much so....thank you very much!
infinisa
You're welcome.

If you need more help (examples etc.), I'll see what I can do.
guissmo
In a nutshell, it's basically you take any number, 1 is usually the easiest to get.
Then assuming that it is true for k, you try to prove it for k+1.
After doing so, we consider that k=1 but since it's already proven true, we can say that the case for k+1 (2) is also true. And then we can let k=2, and so on.
sigT
 gverutes wrote: I am tutoring a student on PreCalc and he is learning about a process called Math Induction. Can someone offer any background on how this works? Practice problems would be helpful! I have looked at Wikipedia, but the explanation is kind of convoluted.

I wonder, what was wrong with the explanation of mathematical induction on Wikipedia. I can imagine though that it might appear a bit alien if you have a non-science background. What is PreCalc you are referring to? Is it related to mathematics at all? Does "Calc" stand for "Calculus"?
ninjakannon
 infinisa wrote: Now, by repeating the same argument that each line leads to the next, we've shown it's true for all values of n.

I like your explanation, it brought it all back as I haven't done mathematical proof by induction for a while now. Although, saying "all values of n" could be misconstrued; it's all values of n within the domain of positive integers.

I always write 'so it's true for n >= 1'.