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

**nubshat** · May 24th 2014, 04:58 PM

Statement: For any integer $n\geq 0, (x^n)'=0$

Proof

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

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

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

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

By induction hypothesis, $( x^k)'=0$ and $(x)'=0$ . Therefore, $(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.
Can someone please help me figure out which part is wrong? or give me a hint?

**JeffM** · May 24th 2014, 06:54 PM

$x' = 1 \ne 0.$

**JeffM** · May 24th 2014, 07:19 PM

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 (x¹)' = 0 is not permissible (as well as being false).

**johng** · May 24th 2014, 08:37 PM

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:

**Deveno** · May 24th 2014, 10:09 PM

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.

**HallsofIvy** · May 25th 2014, 03:53 AM

Originally Posted by nubshat

Statement: For any integer $n\geq 0, (x^n)'=0$

Proof

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

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

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

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

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

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

Therefore, $(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.
Can someone please help me figure out which part is wrong? or give me a hint?

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

LinkBack

Thread Tools

Display

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

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

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

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

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

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

Similar Math Help Forum Discussions

proof by strong induction

Proof Using Strong Induction

Proof Using Strong Induction

Strong Induction proof

Strong induction proof

Search Tags