# Identify the fallacy in strong induction proof

I was wondering what the fallacy was in the following proof:

Given $a \in \mathbb{R}$, one has that $a^n=1$ for all $n \in \mathbb{N}\cup\{0\}$.

"Proof"

If $n=0$ then $a^0=1$. Thus the claim is true for the base case. Next, fix $n \in \mathbb{N} \cup \{0\}$ and assume that the claim is true for all $k\in \mathbb{N}\cup \{0\}$ with $k \leq n$, i.e., assume that $a^k = 1$ for all $n \in \mathbb{N}\cup \{0\}$ with $k \leq n$. We want to show that the claim is true for $n+1$. Observe that

$$a^{n+1} = \dfrac{a^n \times a^n}{a^{n-1}} = \dfrac{1 \times 1}{1} =1$$

where we have used the induction hypothesis in the second equality. Thus the claim is true for $n+1$ and by PMI we can now conclude that the claim is true for all $\mathbb{N} \cup \{0\}$. $\Box$

Clearly the claim is false, and I have to find the error in the proof, not just present a counterexample. So, I think that the error is that you cannot extend the induction hypothesis to any given $a \in \mathbb{R}$ since, by the Peano Property, the induction step only holds for any given $n \in \mathbb{N}$.

Is my reasoning correct? Please let me know.

• No, your reasoning is not correct; the induction is on $n$, not on $a$. Try writing out what happens when $n = 0$; you're applying the induction assumption somewhere where it's not applicable. – user296602 Sep 24 '17 at 3:18
• $a^n = 1$ only holds in general for $n = 0$ or $a = 1$. Your inductive step is faulty. – Ryan A Sep 24 '17 at 3:19
• Check the claim for $n = 0$. Also strong induction doesn't have a base case. – DanielV Sep 24 '17 at 3:56

## 1 Answer

Your inductive step requires the assumption that the result holds (in particular) for $n$ and $n-1$. However, your base case only covers $n=0$ whereas you'd need $n=1$ also for this inductive step to apply.

Here's another example.

Claim that everyone in a group of any countable size has the same age.

Base case: Suppose we have a set of 1 person. Then obviously everyone has the same age.

Now suppose the hypothesis is true for a set of $n$ people, say. $\{a_1, \cdots , a_n\}$.

Take a group of $n+1$ people, $\{a_1, \cdots , a_{n+1}\}$.

We can split this into two smaller subsets $\{a_1, \cdots , a_n\}$ and $\{a_2, \cdots , a_{n+1}\}$ in which each set of people have the same age, as each set has size $n$. Therefore $a_{n+1}$ has the same age as some other $a_i:1<i<n+1$ has the same age as $a_1$, so everyone in that set of $n+1$ people have the same age.

The issue with this proof is that we are using the fact that if $\{a_1, \cdots , a_n\}$ have the same age, any two of them do too. But this assumes that any group of two people $\{a_1, a_2\}$ have the same age which is not true in general.

For this to work you'd need to show the base case of $n=2$, but you cannot do this.

Moral of the story - be careful with your base cases and with what you're assuming when using induction!

• Thank you, it seems rather obvious now :) – user353633 Sep 24 '17 at 13:02