Mathematical induction

From Simple English Wikipedia, the free encyclopedia
(Redirected from Proof by induction)

Mathematical induction is a special way of proving a mathematical truth. It can be used to prove that something is true for all the natural numbers (or all positive numbers from a point onwards).[1][2] The idea is that if:

  1. Something is true for the first case (base case);
  2. Whenever that same thing is true for a case, it will be true for the next case (inductive case),

then

In the careful language of mathematics, a proof by induction often proceeds as follows:

  • State that the proof will be by induction over . ( is the induction variable.)
  • Show that the statement is true when is 1.
  • Assume that the statement is true for any natural number . (This is called the induction step.)
    • Show then that the statement is true for the next number, .

Because it is true for 1, then it is true for 1+1 (=2, by the induction step), then it is true for 2+1 (=3), then it is true for 3+1 (=4), and so on.

Examples of proof by induction[change | change source]

Sum of the first n natural numbers[change | change source]

Prove that for all natural numbers n:

Proof:

First, the statement can be written as:

(for all natural numbers n)

By induction on n,

First, for n=1:

,

so this is true.

Next, assume that for some n=n0 the statement is true. That is,:

Then for n=n0+1:

can be rewritten as

Since

Hence the proof is complete by induction.

The sum of the interior angles of a polygon[change | change source]

Mathematical induction is often stated with the starting value 0 (rather than 1). In fact, it will work just as well with a variety of starting values. Here is an example when the starting value is 3: "The sum of the interior angles of a -sided polygon is degrees."

The initial starting value is 3, and the interior angles of a triangle is degrees. Assume that the interior angles of a -sided polygon is degrees. Add on a triangle which makes the figure a -sided polygon, and that increases the count of the angles by 180 degrees degrees. Since both the base case and the inductive case are handled, the proof is now complete.

There are a great many mathematical objects for which proofs by mathematical induction works. The technical term is a well-ordered set.

Inductive definition[change | change source]

The same idea can work to define a set of objects, as well as to prove statements about that set of objects.

For example, we can define th degree cousin as follows:

  • A st degree cousin is the child of a parent's sibling.
  • A st degree cousin is the child of a parent's th degree cousin.

There is a set of axioms for the arithmetic of the natural numbers which is based on mathematical induction. This is called "Peano's Axioms". The undefined symbols are | and =.The axioms are

  • | is a natural number.
  • If is a natural number, then is a natural number.
  • If then .

One can then define the operations of addition and multiplication and so on by mathematical induction. For example:

Related pages[change | change source]

References[change | change source]

  1. "The Definitive Glossary of Higher Mathematical Jargon". Math Vault. 2019-08-01. Retrieved 2020-09-23.
  2. "3.4: Mathematical Induction - An Introduction". Mathematics LibreTexts. 2018-04-25. Retrieved 2020-09-23.
  3. "Induction". discrete.openmathbooks.org. Retrieved 2020-09-23.