Results 1 to 8 of 8

Math Help - induction,irrational and proves......

  1. #1
    Member
    Joined
    Jul 2006
    Posts
    95

    induction,irrational and proves......

    please try to solve these questions.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,211
    Thanks
    419
    Awards
    1
    Quote Originally Posted by m777 View Post
    please try to solve these questions.
    1a) What the heck is the definition of Q?

    1b) Any even integer is of the form 2n where n is some integer. (This is how an even number is defined.) Now square this:
    (2n)^2 = 4n^2 = 2(2n^2)

    Now, since n is an integer, so is n^2. Again, since 2 and [tex]n^2 are integers so is 2n^2. Thus 2(2n^2) is an integer it is also an even integer.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,904
    Thanks
    765
    Hello, m777!

    Here's some help . . .


    Use mathematical induction to prove:
    . . 1 + \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^{n-1}} \;=\;2\left(1 - \frac{1}{2^n}\right) for any positive integer n.

    Verify S(1)\!:\;1\:=\:2\left(1 - \frac{1}{2}\right) \:=\:1 . . . true!

    Assume S(k)\!:\;1 + \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^{k-1}} \:=\:2\left(1 - \frac{1}{2^k}\right)


    Add \frac{1}{2^k} to both sides:

    . . \underbrace{1 + \frac{1}{2} + \frac{1}{4} + \cdots + \frac{1}{2^{k-1}} + \frac{1}{2^k}} \:=\:2\left(1 - \frac{1}{2^k}\right) + \frac{1}{2^k}
    . . This is the left side of S(k+1)


    The right side is: . 2 - \frac{2}{2^k} + \frac{1}{2^k} \;=\;2 - \frac{1}{2^k} \;=\; 2 - \frac{2}{2^{k+1}} \:=\:2\left(1 - \frac{1}{2^{k+1}}\right)

    . . which is the right side of S(k+1) . . . We're done!

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,904
    Thanks
    765
    Hello again, m777!

    3) Prove by induction that 5^n - 2^n is divisible by 3.

    Verify S(1)\!:\;5^1 - 2^1 \:=\:3 is divisible by 3 . . . true!

    Assume S(k)\!:\;5^k - 2^k is divisible by 3.
    . . Then: . 5^k - 2^k \;=\;3a for some integer a.


    Add 4\!\cdot\!5^k - 2^k to both sides:

    . . 5^k + 4\!\cdot\!5^k - 2^k - 2^k \;=\;3a + 4\!\cdot\!5^k - 2^k


    We have: . 5\!\cdot\!5^k - 2\!\cdot\!2^k\;=\;3a + 3\!\cdot\!5^k + 5^k - 2^k


    \text{Then: }5^{k+1} - 2^{k+1} \;= \;\underbrace{3(a + 5^k)}_{\text{div by 3}} + \underbrace{(5^k - 2^k)}_{\text{div by 3}}


    Therefore: . 5^{k+1} - 2^{k+1} is divisible by 3 . . . We're done!

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2006
    Posts
    95

    reply to topsquark

    Hello,
    Topsquark.
    In part(a) of question no 1 i have done this so far.
    Q(a,b)= o if a<b.
    Q(a-b,b)+1 if b is less than equal to a.
    so
    Q(3,4)=0 SINCE 3<4
    GIVEN Q(a,b)= Q(a-b,b)+1) if b is less than equal to a
    NOW
    Q(14,3)=Q(11,3)+1
    =Q(8,3)+1
    =Q(5,3)+1
    =Q(2,3)+1
    SO AT THAT POINT 2 IS LESS THAN 3.
    THEREFORE
    =0+4
    =4 IS THE ANSWER
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    To prove \sqrt{3} is irrational.

    Assume,
    \sqrt{3}=\frac{a}{b}
    Thus,
    3=\frac{a^2}{b^2}
    Thus,
    3b^2=a^2.

    Prime decompose a.
    Prime decompose b.

    Note,
    a^2 has an even number of prime factors.

    Note,
    b^2 has an even number of prime factors.

    But,
    3b^2 has an odd number of primes factors.

    Thus, we have a contradiction because both sides are note equal by the uniquess part of the fundamental theorem of arithmetic.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1780
    Awards
    1
    This is a very general proof.
    If p is a positive integer that is not a perfect square then \sqrt p is irrational.

    Suppose that it is rational, \sqrt p  = \frac{a}{b} where a & b are integers.
    Let T = \left\{ {n \in Z^ +  :n\sqrt p  \in Z^ +  } \right\}\quad  \Rightarrow \quad b \in T \not= \emptyset.
    By well ordering there is a first term in T, call it K.
    Using the floor function and because p is not a square we have the following:
    \left\lfloor {\sqrt p } \right\rfloor  < \sqrt p  < \left\lfloor {\sqrt p } \right\rfloor  + 1\quad  \Rightarrow \quad 0 < \sqrt p  - \left\lfloor {\sqrt p } \right\rfloor  < 1.

    0 < K\left( {\sqrt p  - \left\lfloor {\sqrt p } \right\rfloor } \right) < K.

    But K\left( {\sqrt p  - \left\lfloor {\sqrt p } \right\rfloor } \right) is an integer less than K.
    But \left[ {K\left( {\sqrt p  - \left\lfloor {\sqrt p } \right\rfloor } \right)} \right]\sqrt p is an integer which contradicts the minimumality of K.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jun 2006
    Posts
    59
    YOu guys are awesome!!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. question on notion of 'proves'...
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 25th 2010, 01:24 PM
  2. Proves in Group Theory
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: April 4th 2010, 10:34 AM
  3. Induction on irrational and rational numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 2nd 2010, 04:34 AM
  4. Replies: 7
    Last Post: January 29th 2009, 04:26 AM
  5. proves -discrete math !!! please help!!!
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 20th 2008, 08:40 PM

Search Tags


/mathhelpforum @mathhelpforum