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.
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
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
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.
Does this help you to understand the concept?
Very much so....thank you very much!
If you need more help (examples etc.), I'll see what I can do.