Reply With Quote
@(you need an account to see links)
Basically proving using the following logic:
1. prove first one is true
2. prove that every subsequent one is true, using the fact that the first one is true.
3. therefore everything is true.
For example, it's true when n = 1. As long as we prove that it's true for n + 1, it will be true for 2, which is 1 + 1, or 3, which is 2 + 1, or 4, and so on.... so therefore everything becomes true.
Analogy time: John has a rare disease. Somehow, we prove that everybody who has the disease will pass it on to their kids. That means John's kids will have the disease, and so will their kids, and so will their kids, etc. By induction we prove that all of John's decendants have the disease as long as 1. we prove John has the disease and 2. proving that the sick people's kids get the disease as well.
Simple example of the method: prove that n^3 - n is divisible by 3.
step one: prove n = 1 is true (proving that John has the disease)
Substitute n = 1 into the equation to check if it actually IS true.
(1)^3 - (1) = 0, which is divisible by 3. Yes, John does have the disease!
Step two: prove John's kids get the disease, proving it's true for n + 1. We first assume that n^3 - n is divisible by 3. We can assume this because we just proved it for n = 1 in the first step.
Substitute n + 1 into the equation:
(n + 1) ^ 3 - (n + 1)
= n^3 + 3n^2 + 3n + 1 - (n + 1)
= n^3 - n + 3n^2 + 3n
We assumed n^3 - n is divisible by 3, so the first part is true. The second part is also clearly divisible by three. Therefore, the statement is true for n + 1 (the offspring).
We have successfully proved the statement.
Originally Posted by Raj
