Browse Definitions:
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

Start the conversation

Send me notifications when other members comment.

By submitting you agree to receive email from TechTarget and its partners. If you reside outside of the United States, you consent to having your personal data transferred to and processed in the United States. Privacy

Please create a username to comment.

-ADS BY GOOGLE

File Extensions and File Formats

Powered by:

SearchCompliance

  • internal audit (IA)

    An internal audit (IA) is an organizational initiative to monitor and analyze its own business operations in order to determine ...

  • pure risk (absolute risk)

    Pure risk, also called absolute risk, is a category of threat that is beyond human control and has only one possible outcome if ...

  • risk assessment

    Risk assessment is the identification of hazards that could negatively impact an organization's ability to conduct business.

SearchSecurity

  • phishing

    Phishing is a form of fraud in which an attacker masquerades as a reputable entity or person in email or other communication ...

  • vulnerability disclosure

    Vulnerability disclosure is the practice of publishing information about a computer security problem, and a type of policy that ...

  • incident response

    Incident response is an organized approach to addressing and managing the aftermath of a security breach or cyberattack, also ...

SearchHealthIT

SearchDisasterRecovery

  • business continuity and disaster recovery (BCDR)

    Business continuity and disaster recovery (BCDR) are closely related practices that describe an organization's preparation for ...

  • business continuity plan (BCP)

    A business continuity plan (BCP) is a document that consists of the critical information an organization needs to continue ...

  • call tree

    A call tree -- sometimes referred to as a phone tree -- is a telecommunications chain for notifying specific individuals of an ...

SearchStorage

  • flash memory

    Flash memory, also known as flash storage, is a type of nonvolatile memory that erases data in units called blocks.

  • NAND flash memory

    NAND flash memory is a type of nonvolatile storage technology that does not require power to retain data.

  • NOR flash memory

    NOR flash memory is one of two types of nonvolatile storage technologies.

SearchSolidStateStorage

  • hybrid hard disk drive (HDD)

    A hybrid hard disk drive is an electromechanical spinning hard disk that contains some amount of NAND Flash memory.

Close