(expand a bit -- haven't yet added an example proof...) |
(whoops... the 2nd example doesn't even need math induction to prove it) |
||
Line 1: | Line 1: | ||
'''Mathematical induction''' is a method of [[proof]] by which a statement about a [[variable]] can be demonstrated to be true for all [[integer]] values of that variable greater than or equal to a specified integer (usually 0 or 1). |
'''Mathematical induction''' is a method of [[proof]] by which a statement about a [[variable]] can be demonstrated to be true for all [[integer]] values of that variable greater than or equal to a specified integer (usually 0 or 1). |
||
− | + | An example of such a statement is: |
|
* The number of possible pairings of ''n'' distinct objects is <math>\frac{n(n+1)}{2}</math> (for any [[positive]] integer ''n''). |
* The number of possible pairings of ''n'' distinct objects is <math>\frac{n(n+1)}{2}</math> (for any [[positive]] integer ''n''). |
||
− | * The difference between the [[square (number)|square]]s of any two [[consecutive]] [[whole number]]s is an [[odd number]]. |
||
− | *: (This can be rephrased as: <math>(n+1)^2-n^2</math> is odd for any nonnegative integer ''n''.) |
||
A '''proof by induction''' proceeds as follows: |
A '''proof by induction''' proceeds as follows: |
Revision as of 22:56, 9 August 2009
Mathematical induction is a method of proof by which a statement about a variable can be demonstrated to be true for all integer values of that variable greater than or equal to a specified integer (usually 0 or 1).
An example of such a statement is:
- The number of possible pairings of n distinct objects is (for any positive integer n).
A proof by induction proceeds as follows:
- The statement is proved for the first possible value of n (usually 0 or 1, but other "starting values" are possible).
- The statement is assumed to be true for some fixed, but unspecified, value n and this assumption is used to prove that the statement is true for (the latter statement is simply the original statement with n replaced by ).
- The statement is then concluded to be true for all relevant values of n (all nonnegative values or all positive values, depending).
That the conclusion in step 3 above follows from steps 1 and 2 is the principle of mathematical induction.
More formally, given a proposition about the variable n that is to be proved for , the following must be proved.
The conclusion is then
- for .