Difference between revisions of "Induction"
(Introduction to Induction) |
m (Stupid LaTeX problems...) |
||
Line 8: | Line 8: | ||
Base Case: <math>{n=1}</math>. <math>1=\frac{1(2)}{2}</math>. | Base Case: <math>{n=1}</math>. <math>1=\frac{1(2)}{2}</math>. | ||
− | Induction Step: Suppose the conclusion is valid for <math>{n=k}</math>. That is, suppose we have <math>1+2+\cdots +k=\frac{k(k+1)}{2}</math>. Adding <math>k+1</math> to both sides, we get <1+2+\cdots +k+(k+1)=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}=\frac{(k+1)(k+2)}{2}</math>, so we can see that the conclusion holding for <math>{n=k}</math> implies that it holds for <math>{n=k+1}</math>, and our induction is complete. | + | Induction Step: Suppose the conclusion is valid for <math>{n=k}</math>. That is, suppose we have <math>\displaystyle 1+2+ \cdots + k = \frac{k(k+1)}{2} </math>. Adding <math>{k+1}</math> to both sides, we get <math>\displaystyle 1+2+\cdots +k+(k+1)= \frac{k(k+1)}{2}+\frac{2(k+1)}{2} = \frac{(k+1)(k+2)}{2}</math>, so we can see that the conclusion holding for <math>{n=k}</math> implies that it holds for <math>\displaystyle { n = k+1 }</math>, and our induction is complete. |
==Uses== | ==Uses== |
Revision as of 18:56, 18 June 2006
Induction is a method of proof where the desired result is first shown to hold for a certain value (the Base Case); it is then shown that if the desired result holds for a certain value, it then holds for another, closely related value. Typically, this means proving first that the result holds for (in the Base Case), and then proving that having the result hold for
implies that the result holds for
. In this way, we can shown that the result holds for all positive integers; we will have showed that it works for
, and that implies that it works for
, which in turn means it works for
, and so on.
Other, odder inductions are possible. If a problem asks you to prove something for all integers greater than 3, you can use as your base case instead. You might have to induct over the even positive integers numbers instead of all of them; in this case, you would take
as your base case, and show that if
gives the desired result, so does
. If you wish, you can similarly induct over the powers of 2.
Example
Here is a simple example of how induction works. Below is a proof (by induction, of course) that the nth Triangular Number is indeed equal to (the nth triangular number is defined as
; imagine an equilateral triangle composed of evenly spaced dots).
Base Case: .
.
Induction Step: Suppose the conclusion is valid for . That is, suppose we have
. Adding
to both sides, we get
, so we can see that the conclusion holding for
implies that it holds for
, and our induction is complete.
Uses
Induction can be useful in almost any branch of mathematics. Often, problems in Number Theory and Combinatorics are especially susceptible to induction solutions, but that's not to say that there aren't any problems in other areas, such as Inequalities, that can be solved with induction.
Induction is also useful in any level of mathematics that has an emphasis on proof. Induction problems can be found anywhere from the Power Round of the ARML up through the USAMTS all the way up to the USAMO and IMO. A good example of an upper-level problem that can be solved with induction isProblem 5 of the 2006 USAMO.