# Prove by induction that 2^1/2 is irrational.

1. Dec 2, 2005

### viren_t2005

Prove by induction that 2^1/2 is irrational.

2. Dec 2, 2005

### AKG

Induction? Induction on what. There's a standard proof by contradiction for this one.

3. Dec 2, 2005

### viren_t2005

ya I know that there is a standard proof buit has been asked in one of the books of maths olympiad.

4. Dec 3, 2005

### CRGreathouse

That's a good question. Usually a proof by induction proves that something is true for n=1 and that if it is true for a given n it is true for n+1. Let's try:

For n=1: Suppose $$\sqrt{2}$$ is rational. Write $$\sqrt{2}=\frac ab$$ with (a,b)=1. Then $$2b^2=a^2$$. But this is a contradiction, since (a,b)=1 (unless a=0, but this is also a contradiction). Thus $$\sqrt{2}$$ is irrational.

Given $$\sqrt2$$ is irrational for n=k, suppose $$\sqrt{2}$$ is rational. Write $$\sqrt{2}=\frac ab$$ with (a,b)=1. Then $$2b^2=a^2$$. But this is a contradiction, since (a,b)=1. Thus $$\sqrt{2}$$ is irrational for n=k+1.

Inductively, $$\sqrt2$$ is irrational for all positive integers n.

5. Dec 3, 2005

### TenaliRaman

Probably OP meant 2^(1/n) ?

-- AI

6. Dec 3, 2005

### CrankFan

hmmm?

Maybe they want him to stop here, then to prove inductively that $$2b^2=a^2$$ doesn't hold for any positive integers? I'm baffled as to what the correct approach should be, it seems like any use of induction based on the standard proof is a bit contrived.

Viren. I am curious, what book is this from?

Last edited: Dec 3, 2005
7. Dec 3, 2005

### CRGreathouse

That could be, but even that doesn't lend itself to a proof by induction -- the proof is direct, and I can't see any benefit from knowing the previous case works.

8. Dec 3, 2005

### viren_t2005

the name of the book from where I have taken this problem is "Challenges & Thrills of Pre-college Mathematics" by krishnamurthy & venkatachala.

9. Dec 3, 2005

### shmoe

They probably want an "infinite decent" type proof where you assume sqrt(2)=p/q then show sqrt(2)=r/t where r<p and t<q

10. Dec 3, 2005

### HallsofIvy

Did you intend "infinite descent" or "infinitely decent"?:rofl:

11. Dec 3, 2005

### shmoe

Considering it is likely responsible for years of wasted time trying to fill in margins with remarkable proofs, I conjecture that "infinite descent" has only finite decency :tongue2:

12. Dec 3, 2005

### CrankFan

As long as it isn't infinitely indecent ... those are the worst kind of proofs.
Speaking of Challenges and Thrills of Pre-college Mathematics by krishnamurthy & venkatachala.
I found only one link to that name on the web although I gather from that one link that it's somewhat well known. Is there a way to get more info on it?

13. Dec 5, 2005

### vaishakh

It is a book used by Indian lads to prepare for national and regional math olympiads in India.

14. Dec 23, 2005

Perhaps you want to do an induction like so:

a la Cantor's proof of denumerability of rationals?

15. Dec 23, 2005

### matt grime

That isn't a proof by induction (in the modern sense certainly and not in any sense I can think of). what is statement P(n) for n in N? what well ordered set are you inducting on? That is a proof by construction, perhaps, if one were careful to explicitly work out the position in the grid of a given rational.

16. Dec 23, 2005

Last edited: Dec 24, 2005
17. May 14, 2008

### Ray Eston Smith Jr

Contrarian proof by induction that SQRT(2) is RATIONAL

SQRT(2) = 1.413213562373...
= 1 + .4 + .01 + .003 + .0002 + ...
There is an infinite sequence of partial sums (1, 1.4, 1.41, 1.413,...) approaching SQRT(2).

(a) The first term in the sequence is 1, which is a rational number.

(b) Assume the nth term in the sequence is rational.
To go from the nth term to the (n+1)th term, you add a rational number (the next digit).
The sum of 2 rational numbers is a rational number,
therefore the (n+1)th term is also rational.

(c) From (a) & (b), by induction, every term in the sequence is rational.

(d) Therefore if 1.413213562373... exists, it is rational.

I've been told that the jump from (c) to (d) is invalid.
They say SQRT(2) = = 1.413213562373... does exist but is not in the sequence.
I don't understand that. The sequence is infinite, why wouldn't induction take it all the way? I believe the answer is that "completed (or actual)" infinities are invalid, so irrational numbers aren't really numbers - they're just labels for unlimited processes of approximation.

18. May 14, 2008

### CRGreathouse

(a) and (b) are correct. Induction allows you to conclude (c), but not (d). Where does (d) come from? Induction is: "Given $\phi(n)\Rightarrow\phi(n+1)$ and $\phi(1)$, $\phi(n)$ for all natural n."

The defenition of real numbers includes their completeness, so of course the square root of 2 is a real number -- they're defined that way. Perhaps you mean that you don't think real numbers are 'real' in some philosophical sense?

19. May 14, 2008

### robert Ihnot

Let suppose that sqrt2 = a/b and thus is rational. Squaring we arrive at 2b^2 = a^2. Since two divides a^2 and is prime, 2 divides a. Thus we have the form 2b^2 = 4(a')^2. This then tells us that b is also divisible by 2 resulting in a simplification of 2(b')^2 = (a')^2.

In the event that we have removed n twos from both sides and are left with a reduced case of $$2\beta^2 = \alpha^2$$ We can use the same process to remove another set of 2s.

Thus an infinity of 2s can be removed from both sides of the equation, but since we are speaking of integers this is an impossibility. Thus the sqrt2 is irrational.

Last edited: May 14, 2008
20. May 19, 2008

### mathwonk

the original proof by euclid is by the well ordering principle, i.e. inductiion.

he proves that if 2 B^2 = A^2, then A is even, hence B is even, and then reduces the fraction further. he comments this reduction process cannot go on forever.

indeed the assumption in greathouses proof that it is possible to choose A,B which gcd = 1, is proved by well ordering, since one takes the denominator as small as possible, say.

i.e. induction is so basic to the usual proofs that we have ceased noticing it.

Last edited: May 19, 2008