Bogus Proof by Strong Induction

Question

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?

Answer 1

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$

Answer 2

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

Answer 3

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)$.