Bogus Proof by Strong Induction

So here is a bogus proof.

Let $$P(n) ::= \forall k \leq n, a^k =1,$$

where k is a nonnegative valued variable.

Base Case: $P(0)$ is equivalent to $a^0 = 1$, which is true by definition of $a^n$

Inductive Step: By induction hypothesis, $a^k = 1$ for all k $\in \mathbb{N}$ such that $k \leq n$. But then

$$a^{n+1} = \frac{a^n \times a^n}{a^{n-1}} = \frac{1 \times 1}{1} = 1$$which imples that $P(n+1)$ holds. It follows by induction that $P(n)$ holds for all $n \in \mathbb{N}$.

So I know this is bogus because we assumed that $P(n)$ is valid for $n \geq 1$ even though this was not our base case. So we cannot assume that $a^{n-1} = 1$

However, if I were to use the strong induction I am not quite sure why my logic fails.

Base case is the same.

Inductive Step: Assume that $P(0), P(1), ... P(n-1)$ is true.

Then I just need to show that $P(n) ::= \forall k \leq n + 1, a^k =1$ is implied by my induction hypothesis.

So for integers up to $n-1$, $a^{n-1} = 1$ by inductive hypothesis.

So I am only required to show that $a ^ {n} = 1$

$a ^ {n} = a^ {n-1} * a ^1 = 1 * 1 = 1$

Where did I fail?

• Check what happens when you try to prove $P(1)$ using only $P(0)$. – Paul Frost Jun 2 '18 at 9:52

The first proof fails because it makes $P(n+1)$ depend on $P(n-1)$ and $P(n)$ (since the calculation of $a_{n+1}$ makes reference to both $a_n$ and $a^{n-1}$), so this proof would need two base cases, rather than $1$.

Indeed, and much more simply put: you can't get $P(1)$ from $P(0)$ alone.

The second one (yours) does indeed not have that problem, but fails for a different reason:

$a ^ {n} = a^ {n-1} * a ^1 = 1 * 1 = 1$

No, that should be:

$a ^ {n} = a^ {n-1} * a ^1 = 1 * \color{red}a$

And note: you cannot save this proof by showing $a^1=1$, since all you are able to show is the base case $0$, i.e. that $a^0 = 1$

• Thank you! I'm still stuck though. Did we not assume that $P(0), ... , P(n-1)$ is true? I know the assumption goes against the knowledge that $a^1 = a$. Does this mean that we are not allowed to make false assumptions in inductive proofs? – morningMango Jun 3 '18 at 2:02
• @morningMango es, that is the assumption, but of course for $n=0$ there are no such elements (which is what makes i a base case, for it means that you need to show that $P(0)$ in and of itself without any assumptions ... though of course it is true that$a^0=1$, so you do have the base case, but the problem is with $n=1$: all you can assume there is that you have $P(0)$, and hence when you work out $a^1=a^{n-1} \cdot a^1$ you get $a^0 \cdot a^1=1 \cdot a^1=a^1$ ... and that $a^1=1$ is not part of the assumption, so this does not work out to $1$ – Bram28 Jun 3 '18 at 10:19

You know $P(1)$ is false. So see where the inductive step fails for $n=0$; how can you divide by $a^{n-1}$?

I know this in the following ironical form.

Theorem: Nobody understands induction.

Proof. Let $A(n)$ be the statement "In any group of $n$ people, nobody understands induction". Let's prove this by induction.

$A(0)$ is trivial.

Assume $A(n)$ is true.

Proof of $A(n+1)$: Consider any group of $n+1$ people. Removing one person $P$, we obtain a group of $n$ people; nobody of them will understand induction. Now pick one these $n$ people, say $P'$. Replacing $P'$ by $P$ we obtain another group of $n$ people and by $A(n)$ we conclude that $P$ (who now belongs to the group) does not understand induction. Thus none of the original $n+1$ people understands it.

To see where this "proof" fails consider $A(0+1)$.