0
$\begingroup$

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?

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

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$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – morningMango Jun 3 '18 at 2:02
  • $\begingroup$ @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$ $\endgroup$ – Bram28 Jun 3 '18 at 10:19
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.