Description
The simplest and most common form of mathematical induction proves that a statement involving a natural number n holds for all values of n. The proof consists of two steps:
- The basis (base case): showing that the statement holds when n is equal to the lowest value that n is given in the question. Usually, n = 0 or n = 1.
- The inductive step: showing that if the statement holds for some n, then the statement also holds when n + 1 is substituted for n.
The assumption in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for n + 1.
The choice between n = 0 and n = 1 in the base case is specific to the context of the proof: If 0 is considered a natural number, as is common in the fields of combinatorics and mathematical logic, then n = 0. If, on the other hand, 1 is taken as the first natural number, then the base case is given by n = 1.
This method works by first proving the statement is true for a starting value, and then proving that the process used to go from one value to the next is valid. If these are both proven, then any value can be obtained by performing the process repeatedly. It may be helpful to think of the domino effect; if one is presented with a long row of dominoes standing on end, one can be sure that:
- The first domino will fall
- Whenever a domino falls, its next neighbor will also fall,
so it is concluded that all of the dominoes will fall, and that this fact is inevitable.
Read more about this topic: Mathematical Induction
Famous quotes containing the word description:
“Why does philosophy use concepts and why does faith use symbols if both try to express the same ultimate? The answer, of course, is that the relation to the ultimate is not the same in each case. The philosophical relation is in principle a detached description of the basic structure in which the ultimate manifests itself. The relation of faith is in principle an involved expression of concern about the meaning of the ultimate for the faithful.”
—Paul Tillich (1886–1965)
“The type of fig leaf which each culture employs to cover its social taboos offers a twofold description of its morality. It reveals that certain unacknowledged behavior exists and it suggests the form that such behavior takes.”
—Freda Adler (b. 1934)
“I was here first introduced to Joe.... He was a good-looking Indian, twenty-four years old, apparently of unmixed blood, short and stout, with a broad face and reddish complexion, and eyes, methinks, narrower and more turned up at the outer corners than ours, answering to the description of his race. Besides his underclothing, he wore a red flannel shirt, woolen pants, and a black Kossuth hat, the ordinary dress of the lumberman, and, to a considerable extent, of the Penobscot Indian.”
—Henry David Thoreau (1817–1862)