Definition

mathematical induction

Mathematical induction is a a specialized form of deductive reasoning used to prove a fact about all the elements in an infinite set by performing a finite number of steps. 

In order for mathematical induction to work with an infinite set, that set must be denumerable, meaning that a one-to-one correspondence must exist between the elements of the set in question and the set of positive integers. In other words, it must be possible to express the set in the form an implied list of discrete elements such as {1, 2, 3, 4, ...}.

Consider a denumerably (also called countably) infinite set X with elements x1, x2, x3, x4, and so on. In order to prove a proposition about all the elements of X, we begin by proving that the proposition holds true for x1, the first element in the set X. Then we must prove that if the proposition holds true for some arbitrary element xn in X (where n is a positive integer), then the proposition also holds true for the next element xn+1 in set X. If we can do both of these two things successfully using deductive reasoning, we create an infinite chain of true statements by rigorous logical implication, proving the proposition true for all of the elements in X.

The first explicit formalization of the induction principle was composed by the French mathematician Blaise Pascal in 1665. Mathematical induction should not be confused with inductive reasoning. The former principle is mathematically rigorous (meaning that the conclusions are logically certain), but the latter methodology deals with probability and allows for some uncertainty.

This was last updated in June 2013
Posted by: Margaret Rouse

Related Terms

Definitions

  • semi-structured data

    - Semi-structured data is data that has not been organized into a specialized format, such as a table, a record, an array or a tree but that nevertheless has associated information, such as metadata,... (WhatIs.com)

  • clinical decision support system (CDSS)

    - A CDSS, or clinical decision support system, is data analysis software or an application that care providers reference during treatment. (SearchHealthIT.com)

  • recommendation engine

    - Recommendation engines are common among online retail websites, such as Amazon. Also known as recommender systems, these applications suggest products (or something else a visitor might search for,... (WhatIs.com)

Glossaries

  • Business intelligence - business analytics

    - Terms related to business intelligence, including definitions about business analytics and words and phrases about gathering, storing, analyzing and providing access to business data.

  • Internet applications

    - This WhatIs.com glossary contains terms related to Internet applications, including definitions about Software as a Service (SaaS) delivery models and words and phrases about web sites, e-commerce ...

Ask a Question About mathematical inductionPowered by ITKnowledgeExchange.com

Get answers from your peers on your most technical challenges

Tech TalkComment

Share
Comments

    Results

    Contribute to the conversation

    All fields are required. Comments will appear at the bottom of the article.