Thread: What's wrong with this proof (complete induction)

1. What's wrong with this proof (complete induction)

I've been having a bit of a a think about this question but still haven't come up with a particuarly good answer yet.

So what's wrong with the following proof that x^n=1 for all non negative intergers n, and all non zero real x. Let P(n) be the proposition that x^n=1.

The base case x^0=1 (so that's fine)

Inductive hypothesis: suppose n greater than equal to 0, and that P(m) true for all m less than or equal to n. (i.e we're assuming everything up to P(n) is true. Then x^n=x^(n-1)=1 based on our assumption.

Then x^(n+1)=(x^n*x^n)/(x^(n-1))=1*1/1=1

So p(n+1) is true. So by complete induction P(n) is true.

*

2. Originally Posted by Power Out
I've been having a bit of a a think about this question but still haven't come up with a particuarly good answer yet.

So what's wrong with the following proof that x^n=1 for all non zero intergers n, and all non zero real x. Let P(n) be the proposition that x^n=1.

The base case x^0=1 (so that's fine)

Inductive hypothesis: suppose n greater than equal to 0, and that P(m) true for all m less than or equal to n. (i.e we're assuming everything up to P(n) is true. Then x^n=x^(n-1)=1 based on our assumption.

Then x^(n+1)=(x^n*x^n)/(x^(n-1))=1*1/1=1

So p(n+1) is true. So by complete induction P(n) is true.

*
the error occurs at the base case. the claim was for nonzero (positive) n. so using the base case n = 0 was invalid. the base case would be that x^1 = 1. but then that would mean x = 1. and in that case, x^n = 1. thus the claim is false since it says x can be any nonzero real number, the faulty base case got you around this though

3. Sorry my fault I did mean to put for all non negative intergers n, rather than all non zero, x can be any non zero real (I've edited the original post now).

4. Just been looking at the proof a bit more, think I may have got somewhere.

We've assumed that P(m) is true for all m less than or equal to n, and n is greater than or equal to 0.

From this we got x^n=x^(n-1)=1.

If we choose n=0 then we're told to assume x^n=1. But n-1=-1, which isn't greater than or equal to 0. As such we can't assume that x^n-1=1.

Hence x^(n+1)= (x^n*x^n)/x^(n-1)=1.1/1=1 only when n is greater than or equal to 1. So the problem is getting between the base case and the n=1 step (one doesn't lead to the other).

This seems right as if you know x^1=1 it follows that x^2=x*x=1, x^3=x*x*x=1 and so on. But just knowing x^0=1 doesn't enable you to say x^1=1.

Does this sound along the right lines?

5. Induction

Hello Power Out
Originally Posted by Power Out
Just been looking at the proof a bit more, think I may have got somewhere.

We've assumed that P(m) is true for all m less than or equal to n, and n is greater than or equal to 0.

From this we got x^n=x^(n-1)=1.

If we choose n=0 then we're told to assume x^n=1. But n-1=-1, which isn't greater than or equal to 0. As such we can't assume that x^n-1=1.

Hence x^(n+1)= (x^n*x^n)/x^(n-1)=1.1/1=1 only when n is greater than or equal to 1. So the problem is getting between the base case and the n=1 step (one doesn't lead to the other).

This seems right as if you know x^1=1 it follows that x^2=x*x=1, x^3=x*x*x=1 and so on. But just knowing x^0=1 doesn't enable you to say x^1=1.

Does this sound along the right lines?
Yes. The fact is that, no matter where you start, you'll always need two consecutive integers $n$ and $(n-1)$ for which $x^n =1$ and $x^{n-1} = 1$, in order to be able to construct the expression $\frac{x^nx^n}{x^{n-1}}$. And you simply don't have that for any base case.