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

[viren_t2005]

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

 

[AKG]

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

 

[viren_t2005]

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

 

[CRGreathouse]

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

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.

 

[TenaliRaman]

Probably OP meant 2^(1/n) ?

-- AI

 

[CrankFan]

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.

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?

 

[CRGreathouse]

Probably OP meant 2^(1/n) ?

-- AI

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.

 

[viren_t2005]

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

 

[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

 

[HallsofIvy]

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

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

 

[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

 

[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?

 

[vaishakh]

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

 

[Treadstone 71]

Perhaps you want to do an induction like so:

a la Cantor's proof of denumerability of rationals?

 

[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.

 

[Treadstone 71]

What if you can show that n => n+1 AND n => n/(n+1)?

i.e., https://www.physicsforums.com/showthread.php?p=864802#post864802

 

[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.

 

[CRGreathouse]

(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.

(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?

 

[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.

 

[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.

 

[mathwonk]

i see i have inadverdently repeated robert ihnot's post.

 

[al-mahed]

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.

you're right, we start the proof assuming that gcd(A,B) = 1, and then showing that writing 2 in a rational form A/B is a contradition with that fact that A/B have no common factor, then we cannot write 2 as a rational form.

I wrote a general proof for these cases in another thread:

if the nth-root of a positive whole number is not a positive whole number**, also will not be a rational number.

This should generalize our results.

consider gcd(p,q) = 1 (p/q in lowest terms)

k^1/n = p/q ==> kq^n = p^n ==> k | p ==> kq^n = (k^n)*(x^n) ==>

==> q^n = k^(n-1)*x^n ==> k | q ==> k | p and q ==> contradiction

** note that if k^1/n is a whole number ==> p/q will not be in lowest terms

 

[robert Ihnot]

mathwonk: i see i have inadverdently repeated robert ihnot's post.

I take a long time to write stuff. I revise things a lot.

However, i am please to realize what you said was not a criticism of what i said for being, after all, obvious.

 

[mathwonk]

i often begin reading at the beginning of a thread, and then write a comment based on reading a post at the bottom of a page, which turns out not to be the last one. then my post turns up appended to one i have not yet seen.