---
tag: 7JRT7X7F29
kind: proof
name: Proof of induction on the integers
msc: [11A99]
proves: 0HBS1F00DN
uses: [0C4JS9RF5M, 0ASJVEFA9J]
methods: [0ASJVEFA9J]
sources:
  - url: https://en.wikipedia.org/wiki/Mathematical_induction
    locator: Variants
---

## Proof

We apply ordinary [[induction|0ASJVEFA9J]] two times, once upward and once downward.
Let $P$ be a property of [[integers|0C4JS9RF5M]] that satisfies the three hypotheses.

1. For each natural number $n$, let $Q_1(n)$ be the claim "$P(n)$ holds".
2. $Q_1(0)$ holds, because $P(0)$ holds. If $Q_1(n)$ holds, then $P(n + 1)$ holds by the second hypothesis, so $Q_1(n + 1)$ holds.
3. By induction, $P(n)$ holds for every natural number $n$.
4. For each natural number $n$, let $Q_2(n)$ be the claim "$P(-n)$ holds".
5. $Q_2(0)$ holds, because $-0 = 0$ and $P(0)$ holds.
6. If $Q_2(n)$ holds, then $P(-n - 1)$ holds by the third hypothesis. Since $-n - 1 = -(n + 1)$, $Q_2(n + 1)$ holds.
7. By induction, $P(-n)$ holds for every natural number $n$.
8. Each integer $z$ is $n$ or $-n$ for some natural number $n$. So $P(z)$ holds by step 3 or by step 7.

## Idea

The integers are two copies of the natural numbers glued at $0$: one going up and one going down.
Ordinary induction covers each copy, starting from the shared base case $P(0)$.