Can the base case be a negative number?

Yes. The base case $n_0$ can be any integer, provided the inductive step proves $P(k) \implies P(k+1)$ for all $k \ge n_0.

What if the inductive step requires multiple previous terms?

Use strong induction. Assume $P(j)$ is true for all $n_0 \le j \le k$ to prove $P(k+1)$.

Do I need to prove the base case if the inductive step is obvious?

Yes. An inductive step without a true base case proves nothing. Both conditions must hold to establish truth for all integers.

How to write a proof by induction

Proof by induction establishes that a given statement $P(n)$ is true for all integers $n \ge n_0$ . It applies when a problem involves a sequence of propositions indexed by integers, such as summation formulas, divisibility properties, or recurrence relations.

The setup

Define the proposition $P(n)$ clearly. Identify the starting integer $n_0$ , which is usually 0 or 1.

The steps

Base case: Prove that $P(n_0)$ is true by direct substitution.
Inductive hypothesis: Assume that $P(k)$ is true for an arbitrary integer $k \ge n_0$ .
Inductive step: Show that $P(k+1)$ follows logically from $P(k)$ .

Checking the result

Verify that the inductive step explicitly uses the inductive hypothesis. If it does not, the proof is either incomplete or induction was not required.

Common errors

Failing to state the inductive hypothesis explicitly is the most frequent error. Another common mistake is assuming $P(k+1)$ is true at the beginning of the inductive step instead of deriving it from $P(k)$ .

Worked example

Prove that $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ for all integers $n \ge 1$ .

Let $P(n)$ be the statement $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ .

Base case ( $n=1$ ): The left side is $\sum_{i=1}^1 i = 1$ . The right side is $\frac{1(1+1)}{2} = 1$ . Both sides are equal, so $P(1)$ is true.

Inductive hypothesis: Assume $P(k)$ is true for an arbitrary integer $k \ge 1$ , meaning $\sum_{i=1}^k i = \frac{k(k+1)}{2}$ .

Inductive step: We must show $P(k+1)$ is true. Consider the sum up to $k+1$ : $\sum_{i=1}^{k+1} i = \sum_{i=1}^k i + (k+1)$ . By the inductive hypothesis, substitute the sum up to $k$ : $= \frac{k(k+1)}{2} + (k+1)$ . Factor out $(k+1)$ : $= (k+1)(\frac{k}{2} + 1)$ $= (k+1)(\frac{k+2}{2})$ $= \frac{(k+1)(k+2)}{2}$ . This is exactly $P(k+1)$ . Therefore, by the principle of mathematical induction, $P(n)$ is true for all $n \ge 1$ .

FAQ

Run your own problem

Answer form

References: Discrete Mathematics and Its Applications by Kenneth H. Rosen · Khan Academy Unit: Series and induction