Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Dec 2, 2005 #1
    Prove by induction that 2^1/2 is irrational.
  2. jcsd
  3. Dec 2, 2005 #2


    User Avatar
    Science Advisor
    Homework Helper

    Induction? Induction on what. There's a standard proof by contradiction for this one.
  4. Dec 2, 2005 #3
    ya I know that there is a standard proof buit has been asked in one of the books of maths olympiad.
  5. Dec 3, 2005 #4


    User Avatar
    Science Advisor
    Homework Helper

    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 [tex]\sqrt{2}[/tex] is rational. Write [tex]\sqrt{2}=\frac ab[/tex] with (a,b)=1. Then [tex]2b^2=a^2[/tex]. But this is a contradiction, since (a,b)=1 (unless a=0, but this is also a contradiction). Thus [tex]\sqrt{2}[/tex] is irrational.

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

    Inductively, [tex]\sqrt2[/tex] is irrational for all positive integers n.
  6. Dec 3, 2005 #5
    Probably OP meant 2^(1/n) ?

    -- AI
  7. Dec 3, 2005 #6

    Maybe they want him to stop here, then to prove inductively that [tex]2b^2=a^2[/tex] 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
  8. Dec 3, 2005 #7


    User Avatar
    Science Advisor
    Homework Helper

    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.
  9. Dec 3, 2005 #8
    the name of the book from where I have taken this problem is "Challenges & Thrills of Pre-college Mathematics" by krishnamurthy & venkatachala.
  10. Dec 3, 2005 #9


    User Avatar
    Science Advisor
    Homework Helper

    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
  11. Dec 3, 2005 #10


    User Avatar
    Science Advisor

    Did you intend "infinite descent" or "infinitely decent"?:rofl:
  12. Dec 3, 2005 #11


    User Avatar
    Science Advisor
    Homework Helper

    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:
  13. Dec 3, 2005 #12
    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?
  14. Dec 5, 2005 #13
    It is a book used by Indian lads to prepare for national and regional math olympiads in India.
  15. Dec 23, 2005 #14
    Perhaps you want to do an induction like so:


    a la Cantor's proof of denumerability of rationals?
  16. Dec 23, 2005 #15

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
  17. Dec 23, 2005 #16
    Last edited: Dec 24, 2005
  18. May 14, 2008 #17
    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.
  19. May 14, 2008 #18


    User Avatar
    Science Advisor
    Homework Helper

    (a) and (b) are correct. Induction allows you to conclude (c), but not (d). Where does (d) come from? Induction is: "Given [itex]\phi(n)\Rightarrow\phi(n+1)[/itex] and [itex]\phi(1)[/itex], [itex]\phi(n)[/itex] 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?
  20. May 14, 2008 #19
    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 [tex] 2\beta^2 = \alpha^2[/tex] 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
  21. May 19, 2008 #20


    User Avatar
    Science Advisor
    Homework Helper

    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook