Results 1 to 8 of 8

Thread: 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
    11,152
    Thanks
    731
    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 $\displaystyle 2n$ where n is some integer. (This is how an even number is defined.) Now square this:
    $\displaystyle (2n)^2 = 4n^2 = 2(2n^2)$

    Now, since n is an integer, so is $\displaystyle n^2$. Again, since 2 and [tex]n^2 are integers so is $\displaystyle 2n^2$. Thus $\displaystyle 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
    12,028
    Thanks
    848
    Hello, m777!

    Here's some help . . .


    Use mathematical induction to prove:
    . . $\displaystyle 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 $\displaystyle n$.

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

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


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

    . . $\displaystyle \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 $\displaystyle S(k+1)$


    The right side is: .$\displaystyle 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 $\displaystyle 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
    12,028
    Thanks
    848
    Hello again, m777!

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

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

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


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

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


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


    $\displaystyle \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: .$\displaystyle 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 $\displaystyle \sqrt{3}$ is irrational.

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

    Prime decompose $\displaystyle a$.
    Prime decompose $\displaystyle b$.

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

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

    But,
    $\displaystyle 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
    21,780
    Thanks
    2823
    Awards
    1
    This is a very general proof.
    If p is a positive integer that is not a perfect square then $\displaystyle \sqrt p $ is irrational.

    Suppose that it is rational, $\displaystyle \sqrt p = \frac{a}{b}$ where a & b are integers.
    Let $\displaystyle 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:
    $\displaystyle \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.$

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

    But $\displaystyle K\left( {\sqrt p - \left\lfloor {\sqrt p } \right\rfloor } \right)$ is an integer less than K.
    But $\displaystyle \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: Apr 25th 2010, 12:24 PM
  2. Proves in Group Theory
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: Apr 4th 2010, 09:34 AM
  3. Induction on irrational and rational numbers
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 2nd 2010, 03:34 AM
  4. Replies: 7
    Last Post: Jan 29th 2009, 03:26 AM
  5. proves -discrete math !!! please help!!!
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Oct 20th 2008, 07:40 PM

Search Tags


/mathhelpforum @mathhelpforum