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

  • risk map (risk heat map)

    A risk map, also known as a risk heat map, is a data visualization tool for communicating specific risks an organization faces.

  • 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 ...

SearchSecurity

  • FIDO (Fast Identity Online)

    FIDO (Fast ID Online) is a set of technology-agnostic security specifications for strong authentication. FIDO is developed by the...

  • cryptanalysis

    Cryptanalysis is the study of ciphertext, ciphers and cryptosystems with the aim of understanding how they work and finding and ...

  • Trojan horse (computing)

    In computing, a Trojan horse is a program that appears harmless, but is, in fact, malicious.

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

  • wear leveling

    Wear leveling is a process that is designed to extend the life of solid-state storage devices.

  • storage area network (SAN)

    A storage area network (SAN) is a dedicated high-speed network or subnetwork that interconnects and presents shared pools of ...

  • SSD TRIM

    SSD TRIM is an Advanced Technology Attachment (ATA) command that enables an operating system to inform a NAND flash solid-state ...

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