Mastering Basic Math Induction: Tips, Examples, and Resources for Self-Learning

[accesskb]

help needed urgently: Basic Math Induction

I am trying to teach myself mathematical induction, have never encountered this before and it's giving me trouble. My problem will likely be very easy to you all so please forgive me.

I have put up the scanned image of the example in my book.
http://img89.imageshack.us/my.php?image=induct3zv.jpg

here are my 3 questions:

(1) What I don't understand is that how do I get the values in #2 (red ink) from #1. It seems like it's some basic factoring operation but I'm very confused even looking at this example. I have tried to get the values in #2 from #1 but they don't match up. It seems like the text decided to jump a step or maybe I just don't understand it's simple steps.

(2) How do we know when we've completely solved an inducation problem? for eg: in addition we know we've arrived at the answer when we can't add anymore. :D How do we know when we've solved the problem in induction?

(3) I would appreciate it if you can give me some basic tips regarding and how to do induction problems. This book I have doesn't go into it much besides showing examples. I think I understand most of it after having looked at three examples and stressing myself out the past 2 days trying to learn. The book just gives me the basic principles for inducation (1)Prove that it is true for n=1 (2)Assume it is true for n=k (3) use this to prove that n=k+1 is true. I would also be greatful if you can recommend me any good books regarding basic Algegra & Geometry.

Please help me as I'm taking this self learning course and don't have anyone to ask for help. I have an entrance exam in less than three weeks. Appreciate all kind help :D

 

[arildno]

Let's take (1) first:
All that has been done, is to add 0 in the numerator, in the form 0=k-k.
Can you see that this is what has been done?

 

[accesskb]

^ sorry I don't quite get you. Where did the 0=k-k come from? How do I know I need to add 0 to the numerator?

 

[VietDao29]

Here's how induction work. There are 3 steps:
(1) : Prove the statement true for n = 1.
(2) : Assume the statement true for n = k.
(3) : Use that to prove the statement true for n = k + 1.
This is what you already know. When comlete the three steps, the statement is true $\forall n \geq 1$. Why?
Obviously, the statement is true for n = 1 (1). (2) and (3) means that if the statement is true for n = k, then it's true for n = k + 1.
So the statement is true for n = 1 => So it's true for n = 1 + 1 = 2.
Because the statement is true for n = 2 => So it's true for n = 2 + 1 = 3.
Because the statement is true for n = 3 => So it's true for n = 2 + 1 = 4.
...
So the statement is true for all n >= 1.
That's how induction works.
------------
Back to your question:
You should know:
$- (\pm a \pm b \pm c) = (\mp a) + (\mp b) + (\mp c)$
$+ (\pm a \pm b \pm c) = (\pm a) + (\pm b) + (\pm c)$
$a - b = a + (-b) = (-b) + a$
$(a \pm b) ^ 2 = a ^ 2 \pm 2ab + b ^ 2$
$(a \pm b) ^ 3 = a ^ 3 \pm 3ab ^ 2 + 3 a ^ 2b \pm b ^ 3$
$a(b \pm c) = ab \pm ac$ or $ab \pm ac = a(b \pm c)$
$$\frac{a \pm b}{c} = \frac{a}{c} \pm \frac{b}{c}$$ (*)
----------------
(1) $$(k + 1) ^ 3 - (k + 1) = k ^ 3 + 3k ^ 2 + 3k + 1 - k - 1 = k ^ 3 + 3 k ^ 2 + 3k - k + 1 - 1 = k ^ 3 + 3k ^ 2 + 2k$$
(2)$k ^ 3 + 3k ^ 2 + 2k = k ^ 3 + 3 k ^ 2 + 3k - k = k ^ 3 - k + 3 k ^ 2 + 3k$
(3) From (*), you will have (3).
You use the step 2, assume it's true for n = k, so $$\frac{k ^ 3 - k}{3}$$ must be an integer, $k ^ 2 + k$ is also an integer due to k is an integer. So the statement is true for n = k + 1. (Q.E.D)
After completing 3 steps, it's done.
Viet Dao,

 

[HallsofIvy]

2) How do we know when we've completely solved an inducation problem? for eg: in addition we know we've arrived at the answer when we can't add anymore. :D How do we know when we've solved the problem in induction?

In any proof you're done when you've proved what you wanted to!

In particular, in induction, you are done when you have the formula you want to prove in terms of "n+1".

Here the purpose was to prove "$$\frac{n^3- n}{3}$$ is an integer for any positive integer n".
The idea of induction is you first prove it is true for n= 1 and then prove: "If it is true for any specific integer, k, then it is true for the next integer, k+1". Then we could argue (the part you don't have to write) that since it is true for 1, it must be true for 1+1= 2, since it is true for 2, it must be true for 2+1= 3, etc.

Here: If n= 1, this is (1-1)/3= 0, an integer.

Suppose $$\frac{k^3-k}{3}$$ is an integer and look at $$\frac{(k+1)^3-(k+1)}{3}$$.

Multiplying the (k+1)³ term out, we get $$\frac{k^3+ 3k^2+ 3k+ 1- k- 1}{3}= \frac{k^3+ 3k^2+ 2k}{3}$$.

Now, add and subtract k in the numerator: $$\frac{k^3+ 3k^2- k+ k+ 2k}{3}=\frac{k^3+ 3k^2-k+ 3k}{3}$$.

The purpose of that was to get that "3k". Rearrange to terms to put the 3k² and 3k together: $$\frac{k^3- k+ 3(k^2+ k}{3}= \frac{k^3-k}{3}+ k^2+ k$$.

$$\frac{k^3- k}{3}$$ is an integer by the "induction hypothesis" and k²+ k is clearly an integer so their sum is an integer.

Here's a slightly different example: Prove that, for any positive integer, n, $$\sum_{i=1}^n i= \frac{n(n+1)}{2}$$. That is, that the sum of the first n positive integers is n(n+1)/2.

1) If n= 1, the sum is just the first term, 1. 1(1+1)/2= 2/2= 1. Yes, they are the same.

2) Now assume it is true for some positive integer k and look at k+1:
$$\sum_{i=1}^{k+1} i$$. Of course, that's just the sum up to k with one more term added! $$\sum_{i=1}^{k+1} i= \sum{i=1}^k i + (k+1)$$.

By the "induction hypthesis" (that this is true for n= k), that first sum is k(k+1)/2 so
$$\sum{i=1}^{k+1} i= \frac{k(k+1)}{2}+ k+1$$.

What you want to do is show that that is the same a n(n+1)/2 with n replaced by k+1: (k+1)(k+2)/2. Factor (k+1) out of k(k+1)/2+ (k+1) and we what happens!

 

[accesskb]

Here's how induction work. There are 3 steps:

(2) $k ^ 3 + 3k ^ 2 + 2k = k ^ 3 + 3 k ^ 2 + 3k - k = k ^ 3 - k + 3 k ^ 2 + 3k$

here's where I'm confused. how did $k ^ 3 + 3k ^ 2 + 2k$
end up to $k ^ 3 + 3 k ^ 2 + 3k - k$
aren't we supposed to find the greatest common factor here? what step did you use in here?

 

[accesskb]

Now, add and subtract k in the numerator: $$\frac{k^3+ 3k^2- k+ k+ 2k}{3}=\frac{k^3+ 3k^2-k+ 3k}{3}$$.

The purpose of that was to get that "3k". Rearrange to terms to put the 3k² and 3k together: $$\frac{k^3- k+ 3(k^2+ k}{3}= \frac{k^3-k}{3}+ k^2+ k$$.

this is the step that confuses me. Why do we add and subtrack k in the numerator? ok you say so that we get 3k. Why and how do we know we need to get 3k?


thnx for the thorough explanation

 

[VietDao29]

Do you know $a(b \pm c) = ab \pm ac$.
So 2k = (3 - 1) k = 3k - k. The 6th equation in the lists of equations in my last post.
Viet Dao,

 

[accesskb]

Do you know $a(b \pm c) = ab \pm ac$.
So 2k = (3 - 1) k = 3k - k. The 6th equation in the lists of equations in my last post.
Viet Dao,

thanks I understand that. It seems like we are working backwards. Usually I get an equation in this form (3 - 1) k and I end up with 3k-k = 2k I've never had to take 2k and end up with (3-1)k confuses me here. sorry for all the trouble but why are we making 2k into (3-1)K ? Aren't we supposed to follow factoring rules and get the GFC (greatest common factor) for $k ^ 3 + 3k ^ 2 + 2k$

 

[VietDao29]

Okay, what you have is step 2 (assume the statement is true for n = k), and you use that to prove it's also true for n = k + 1.
So, you have : $$\frac{k ^ 3 - k}{3}$$ is an integer. You will try to arrange $$\frac{k ^ 3 + 3k ^ 2 + 2k}{3}$$ into something like: $$\frac{k ^ 3 - k}{3} + ?$$. Why? You have $$\frac{k ^ 3 - k}{3}$$ is an integer, and all you need is to prove '?' is also an integer.
$$\frac{k ^ 3 + 3k ^ 2 + 2k}{3}$$ You already have $$\frac{k ^ 3}{3}$$, you need another $$\frac{-k}{3}$$, so you will get the -k from 2k. So 2k = 3k - k.
Viet Dao,

 

[accesskb]

^^^ thank you so much my friend. That clears up a lot of questions. Now I'm off to try the questions :rofl:

 

[matt grime]

this is the step that confuses me. Why do we add and subtrack k in the numerator? ok you say so that we get 3k. Why and how do we know we need to get 3k?

experience, mathematical maturity if you will. adding 0 in a clever way, or multiplying by 1 (=a/a) is about the most powerful technique of proof you can learn right now.

 

[bruno C]

Although the question is to help with induction, I thought I'd mention that sometimes induction is used but it is not necessary, in the sense that another proof exists that does not use induction. Why would it matter?

Induction says something about an existing proof for all n. If you can prove something using induction, your proof is in this sense existentional and depending on logic. (see the comment of VietDao29 above) So, if logic is the issue in any debate if something is true, you may want to opt for another proof.

Anyway, it may be preferred to have a direct proof of a theorem, without using induction (most mathematicians don't bother, though).

In this case, it is easy too:

For integers n, (n^3-n)/3 is integer iff 3|n^3-n. In this particular case, we see that n^3-n can be factored

n^3-n = n(n-1)(n+1).

Now it is easy to see why this is divisible by 3, because there are three cases.
i. n=0 mod 3. Then 3 divides the factor n.
ii. n=1 mod 3. Then 3 divides the factor n-1
iii. n=-1 mod 3. Then 3 divides the factor n+1.

Q.E.D.

Normally, induction proofs are used when any or all of the following apply.
- you want to prove something for all natural numbers.
- it is not a matter of algebra (such as the above problem).
- a direct proof is unknown.
- induction simplifies the proof AND there is no logic issue.

For instance.
Example: For all k, the sum of the first k odd numbers is a square and equals k^2.

Proof.
(Note that the k-th odd number equals 2k-1)

Step 1. We prove it for k=1.
1=1^2 is a square. Nothing further to prove.

Step 2. Suppose it is true for k, then we prove it for k+1.
So, we assume the first k odd numbers to add up to k^2, then if we should prove that adding the (k+1)-th odd number we get (k+1)^2. The k+1)-th odd number equals 2(k+1)-1 = 2k+1, and if we add it to the sum of the previous k odd numbers we get the total sum of k^2+2k+1 = (k+1)^2. That is exactly what we wanted to prove.

Step 3. We conclude it is true for all k using logic.
Q.E.D.

I hope this was helpful too.