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

1. ## 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.

2. ## Re: What's wrong with the following proof? (Strong induction)

$x' = 1 \ne 0.$

3. ## 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).

4. ## 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:

5. ## 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.

6. ## Re: What's wrong with the following proof? (Strong induction)

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.

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.