Difference between revisions of "Induction"
Loverslane22 (talk | contribs) (→Introductory) |
Michael5210 (talk | contribs) m (→Video Lecture) |
||
(16 intermediate revisions by 8 users not shown) | |||
Line 1: | Line 1: | ||
− | '''Induction''' is a method of proof which 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 <math>n=1</math> (in the Base Case), and then proving that having the result hold for <math>{n=k}</math> implies that the result holds for <math>n=k+1</math>. In this way, we can | + | '''Induction''' is a method of proof in which 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 <math>n=1</math> (in the Base Case), and then proving that having the result hold for <math>{n=k}</math> implies that the result holds for <math>n=k+1</math>. In this way, we can show that the result holds for all positive integers; we will have shown that it works for <math>n=1</math>, and that implies that it works for <math>n=1+1=2</math>, which in turn means it works for <math>n=2+1=3</math>, 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 <math>n=4</math> 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 <math>n=2</math> as your base case, and show that if <math>{n=k}</math> gives the desired result, so does <math>n=k+2</math>. If you wish, you can similarly induct over the powers of 2. | Other, odder inductions are possible. If a problem asks you to prove something for all integers greater than 3, you can use <math>n=4</math> 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 <math>n=2</math> as your base case, and show that if <math>{n=k}</math> gives the desired result, so does <math>n=k+2</math>. If you wish, you can similarly induct over the powers of 2. | ||
Line 7: | Line 7: | ||
Here is a simple example of how induction works. Below is a proof (by induction, of course) that the <math>n</math>th [[triangular number]] is indeed equal to <math>\frac{n(n+1)}{2}</math> (the <math>n</math>th triangular number is defined as <math>1+2+\cdots +n</math>; imagine an [[equilateral polygon | equilateral]] [[triangle]] composed of evenly spaced dots). | Here is a simple example of how induction works. Below is a proof (by induction, of course) that the <math>n</math>th [[triangular number]] is indeed equal to <math>\frac{n(n+1)}{2}</math> (the <math>n</math>th triangular number is defined as <math>1+2+\cdots +n</math>; imagine an [[equilateral polygon | equilateral]] [[triangle]] composed of evenly spaced dots). | ||
− | Base Case: <math> | + | '''Base Case:''' If <math>n=1,</math> then <math>1+2+\ldots+n = 1,</math> and <math>\frac{1(2)}{2} = 1.</math> So, <math>1+2+\ldots+n = \frac{n(n+1)}{2}</math> for <math>n=1.</math> |
− | + | '''Inductive 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 <cmath>1+2+\cdots +k+(k+1)= \frac{k(k+1)}{2}+\frac{2(k+1)}{2} = \frac{(k+1)(k+2)}{2},</cmath> so the conclusion holding for <math>n=k</math> implies that it holds for <math>n = k+1</math>, and our induction is complete. <math>\blacksquare</math> | |
==Uses== | ==Uses== | ||
Line 15: | Line 15: | ||
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 [[American Regions Math League | ARML]] up through the [[United States of America Mathematics Talent Search | USAMTS]] all the way up to the [[United States of America Mathematics Olympiad | USAMO]] and [[International Mathematics Olympiad | IMO]]. A good example of an upper-level problem that can be solved with induction is [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=490682#p490682 USAMO 2006/5]. | 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 [[American Regions Math League | ARML]] up through the [[United States of America Mathematics Talent Search | USAMTS]] all the way up to the [[United States of America Mathematics Olympiad | USAMO]] and [[International Mathematics Olympiad | IMO]]. A good example of an upper-level problem that can be solved with induction is [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=490682#p490682 USAMO 2006/5]. | ||
+ | |||
+ | ==Video Lecture== | ||
+ | https://www.youtube.com/watch?v=Bp6jbrkQf_4&t | ||
==Problems== | ==Problems== | ||
Line 20: | Line 23: | ||
===Introductory=== | ===Introductory=== | ||
− | Prove that <math>1^3+2^3+...+n^3=(1+2+...+n)^2</math>. | + | * The Fibonacci numbers are a sequence of numbers that satisfy <math>F_{1}=1</math>, <math>F_{2}=1</math>, and the recursion <math>F_{n}=F_{n-1}+F_{n-2}</math> when <math>n \geq 3</math>. Prove that <math>F_{1}+F_{2}+ \ldots +F_{n}=F_{n+2}-1</math>. |
+ | |||
+ | * Prove that <math>6|(7^n - 1)</math> for all positive integers <math>n.</math> (From ''[[The Art and Craft of Problem Solving]]'') | ||
+ | |||
+ | * Prove that <math>1^3+2^3+...+n^3=(1+2+...+n)^2</math>. | ||
+ | |||
+ | * Prove Bernoulli's inequality. | ||
===Intermediate=== | ===Intermediate=== | ||
− | + | ||
* For any set <math>T</math> whose elements are positive integers, define <math>f(T)</math> to be the square of the product of the elements of <math>T</math>. For example, if <math>T = \{1, 3, 6\}</math>, then <math>f(T) = (1 \cdot 3 \cdot 6)^2 = 18^2 = 324</math>. For any positive integer <math>n</math>, consider all nonempty subsets <math>S</math> of <math>\{1, 2, . . . , n\}</math> that do not contain two consecutive integers. Prove that the sum of all the f(S)’s of these subsets is <math>(n + 1)! - 1</math>. | * For any set <math>T</math> whose elements are positive integers, define <math>f(T)</math> to be the square of the product of the elements of <math>T</math>. For example, if <math>T = \{1, 3, 6\}</math>, then <math>f(T) = (1 \cdot 3 \cdot 6)^2 = 18^2 = 324</math>. For any positive integer <math>n</math>, consider all nonempty subsets <math>S</math> of <math>\{1, 2, . . . , n\}</math> that do not contain two consecutive integers. Prove that the sum of all the f(S)’s of these subsets is <math>(n + 1)! - 1</math>. | ||
+ | |||
+ | * A function <math>f(x)</math> defined on the positive integers satisfies <math>f(1) = 1996</math> and <math>f(1)+f(2)+\ldots + f(n) = n^2f(n)\qquad (n > 1)</math>. Calculate <math>f(1996)</math>. (United Kingdom 1996/2) | ||
===Olympiad=== | ===Olympiad=== | ||
* Prove [[Fermat's Little Theorem]]. | * Prove [[Fermat's Little Theorem]]. | ||
− | + | * Prove [[AM-GM Inequality]] by the first principle of mathematical induction. | |
− | * | + | * Prove that the number of odd binomial coefficients in any row of the Pascal triangle is a power of 2. (1956 Putnam Competition) |
==See also== | ==See also== |
Latest revision as of 23:59, 28 September 2024
Induction is a method of proof in which 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 show that the result holds for all positive integers; we will have shown 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.
Contents
[hide]Example
Here is a simple example of how induction works. Below is a proof (by induction, of course) that the th triangular number is indeed equal to (the th triangular number is defined as ; imagine an equilateral triangle composed of evenly spaced dots).
Base Case: If then and So, for
Inductive Step: Suppose the conclusion is valid for . That is, suppose we have . Adding to both sides, we get so 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 is USAMO 2006/5.
Video Lecture
https://www.youtube.com/watch?v=Bp6jbrkQf_4&t
Problems
Introductory
- The Fibonacci numbers are a sequence of numbers that satisfy , , and the recursion when . Prove that .
- Prove that for all positive integers (From The Art and Craft of Problem Solving)
- Prove that .
- Prove Bernoulli's inequality.
Intermediate
- For any set whose elements are positive integers, define to be the square of the product of the elements of . For example, if , then . For any positive integer , consider all nonempty subsets of that do not contain two consecutive integers. Prove that the sum of all the f(S)’s of these subsets is .
- A function defined on the positive integers satisfies and . Calculate . (United Kingdom 1996/2)
Olympiad
- Prove Fermat's Little Theorem.
- Prove AM-GM Inequality by the first principle of mathematical induction.
- Prove that the number of odd binomial coefficients in any row of the Pascal triangle is a power of 2. (1956 Putnam Competition)