# What's wrong with the following proof? (Strong induction)

• May 24th 2014, 04:58 PM
nubshat
What's wrong with the following proof? (Strong induction)
Statement: For any integer $\displaystyle n\geq 0, (x^n)'=0$

Proof

Base Case: For $\displaystyle n=0, x^0=1, so \, (x^0)'=(1)'=0$

Induction hypothesis: Assume that for some $\displaystyle k, (x^i)'=0$ for all $\displaystyle 0 \leq i \leq k$

Induction step: Consider $\displaystyle x^{k+1}$. Note that $\displaystyle x^{k+1} = x* x^k$

Using product rule, $\displaystyle (x^{k+1})'=(x*x^k)'=x*(x^k)' + (x)'*x^k$

By induction hypothesis, $\displaystyle ( x^k)'=0$ and $\displaystyle (x)'=0$. Therefore, $\displaystyle (x^{k+1})'=0$. So the result holds by induction

I know this statement is obviously false, but I can't seem to find anything wrong with the proof that is provided.
I looked through my notes and it looks like every step of the induction process is followed correctly.
• May 24th 2014, 06:54 PM
JeffM
Re: What's wrong with the following proof? (Strong induction)
$x' = 1 \ne 0.$
• May 24th 2014, 07:19 PM
JeffM
Re: What's wrong with the following proof? (Strong induction)
Upon reflection, my post above is too curt.

When you show that $(x^0)' = 0$ you have proved that

$the\ set\ J\ such\ that\ i \in J \implies i \in \mathbb Z\ and\ i \ge 0\ and\ (x^i)' = 0\ is\ not\ empty.$

Thus I dislike the traditional phraseology "$Assume\ for\ some\ integer\ k \ge 0\ that\ (x^k)' = 0."$

You have proved that J contains at least one such integer. So I prefer to say, "Let k be any member of J." But you have not proved that 1 is in set J, and so (x1)' = 0 is not permissible (as well as being false).
• May 24th 2014, 08:37 PM
johng
Re: What's wrong with the following proof? (Strong induction)
Hi,
I hope this helps. Whenever doing a "strong" inductive proof, it's probably a bad idea to use n+1 as m as in the following:

http://i62.tinypic.com/5x5w29.png
• May 24th 2014, 10:09 PM
Deveno
Re: What's wrong with the following proof? (Strong induction)
Hint: what happens for k = 1?

A variation of this proof is used to prove that all horses are the same color. Basically, you are using the wrong base case.
• May 25th 2014, 03:53 AM
HallsofIvy
Re: What's wrong with the following proof? (Strong induction)
Quote:

Originally Posted by nubshat
Statement: For any integer $\displaystyle n\geq 0, (x^n)'=0$

Proof

Base Case: For $\displaystyle n=0, x^0=1, so \, (x^0)'=(1)'=0$

Induction hypothesis: Assume that for some $\displaystyle k, (x^i)'=0$ for all $\displaystyle 0 \leq i \leq k$

Induction step: Consider $\displaystyle x^{k+1}$. Note that $\displaystyle x^{k+1} = x* x^k$

Using product rule, $\displaystyle (x^{k+1})'=(x*x^k)'=x*(x^k)' + (x)'*x^k$

By induction hypothesis, $\displaystyle ( x^k)'=0$ and $\displaystyle (x)'=0$.

This step does not work for k= 0 because you are using "$\displaystyle (x)'= 0$ before you have proved it.

Quote:

Therefore, $\displaystyle (x^{k+1})'=0$. So the result holds by induction

I know this statement is obviously false, but I can't seem to find anything wrong with the proof that is provided.
I looked through my notes and it looks like every step of the induction process is followed correctly.