Induction

Pronunciation: /ɪnˈdʌk ʃən/ ?

Mathematical induction is used to prove things about infinite sets. Mathematical induction starts with a few examples of an infinite series. If you can show that the claim is true for the first case, and that if the claim is true for an arbitrary case, then the claim is always true for the next case, you have proved that the claim about the infinite set is true.

Example

StatementJustification
State the claim.
We will show that 1 + 2 + 3 + ... + n = n*( n + 1 ) / 2 Statement of claim.
Show that the first case is true.
When n=1, (1 + 1) / 2 = 1 Show the first case is true by substituting 1 for n.
Establish an arbitrary case.
Let 1 + 2 + 3 + ... + m = m*( m + 1 ) / 2 Assume the mth case is true.
Show that, if the arbitrary case is true, then the next case must be true.
1 + 2 + 3 + ... + m + (m + 1) = m*(m + 1) / 2 + (m + 1) Use the additive property of equality to add m + 1 to both sides. m + 1 is the next term.
= m·(m + 1) / 2 + 2*(m + 1) / 2 Multiply the second term by 2/2 = 1. This uses the fact that 1 is the multiplicative identity.
= ( m*(m + 1) + 2*(m + 1) ) / 2 Apply the distributive property of multiplication over addition and subtraction to combine the fractions.
= ( (m*m + m) + (2*m + 2) ) / 2 Apply the distributive property of multiplication over addition and subtraction to distribute the numerator.
= (m<sup>2</sup> + 3*m + 2) / 2 Apply the commutative property of addition to combine the terms in the numerator.
= (m + 1)(m + 2) / 2 Factor the numerator.
Let n = ( m + 1 ) blank space
Then 1 + 2 + 3 + ... + (n - 1) + n = n*(n + 1) / 2 QED.

References

  1. induction. http://wordnet.princeton.edu/. WordNet. Princeton University. (Accessed: 2011-01-08). http://wordnetweb.princeton.edu/perl/webwn?s=induction&sub=Search+WordNet&o2=&o0=1&o7=&o5=&o1=1&o6=&o4=&o3=&h=.
  2. Cupillari, Antonella. Nuts and Bolts of Proof: An Introduction to Mathematical Proofs, 3rd edition, pp 48-57. Academic Press, June 3, 2005.
  3. Gilbert, Jimmie; and Gilbert Linda. Elements of Modern Algebra, 6th edition, pp 63-70. Thomson, Brooks/Cole, 2005.

More Information

  • McAdams, David. Inductive Reasoning. allmathwords.org. All Math Words Encyclopedia. Life is a Story Problem LLC. 2009-03-12. http://www.allmathwords.org/article.aspx?lang=en&id=Inductive%20Reasoning.

Printed Resources

Cite this article as:


Induction. 2010-02-11. All Math Words Encyclopedia. Life is a Story Problem LLC. http://www.allmathwords.org/en/i/induction.html.

Translations

Image Credits

Revision History


2008-12-30: Added several vocabulary links (McAdams, David.)
2008-11-26: Changed equations to images (McAdams, David.)
2008-08-09: Changed equations to Hot_Eqn (McAdams, David.)
2008-03-25: Changed More Information to match current standard (McAdams, David.)
2007-09-03: Initial version (McAdams, David.)

All Math Words Encyclopedia is a service of Life is a Story Problem LLC.
Copyright © 2005-2011 Life is a Story Problem LLC. All rights reserved.
Creative Commons License This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 License