# Definition:Induction Step

## Terminology of Mathematical Induction

Consider a **proof by mathematical induction**:

**Mathematical induction** is a proof technique which works in two steps as follows:

- $(1): \quad$ A statement $Q$ is established as being true for some distinguished element $w_0$ of a well-ordered set $W$.

- $(2): \quad$ A proof is generated demonstrating that if $Q$ is true for an arbitrary element $w_p$ of $W$, then it is also true for its immediate successor $w_{p^+}$.

The conclusion is drawn that $Q$ is true for all elements of $W$ which are successors of $w_0$.

The proof that the truth of $Q$ for $w_p$ implies the truth of $Q$ for $w_{p^+}$is called the **induction step**.

Expressed in the various contexts of mathematical induction:

### First Principle of Finite Induction

The step which shows that $n \in S \implies n + 1 \in S$ is called the **induction step**.

### First Principle of Mathematical Induction

The step which shows that $\map P k \implies \map P {k + 1}$ is called the **induction step**.

### Second Principle of Finite Induction

The step which shows that $n + 1 \in S$ follows from the assumption that $k \in S$ for all values of $k$ between $n_0$ and $n$ is called the **induction step**.

### Second Principle of Mathematical Induction

The step which shows that the truth of $\map P {k + 1}$ follows from the assumption of truth of $P$ for all values of $j$ between $n_0$ and $k$ is called the **induction step**.

### Principle of General Induction

The step which shows that $\map P x = \T \implies \map P {\map g x} = \T$ is called the **induction step**.

### Principle of General Induction for Minimally Closed Class

The step which shows that $\map P x = \T \implies \map P {\map g x} = \T$ is called the **induction step**.

### Principle of Superinduction

The step which shows that $\map P x = \T \implies \map P {\map g x} = \T$ is called the **induction step**.

## Also known as

The **induction step** can also be referred to as the **inductive step**.

## Also see

## Sources

- 1980: David M. Burton:
*Elementary Number Theory*(revised ed.) ... (previous) ... (next): Chapter $1$: Some Preliminary Considerations: $1.1$ Mathematical Induction