Results 1 to 9 of 9

Math Help - A Bit Of Help Please. Induction Arguments

  1. #1
    AJL
    Guest

    A Bit Of Help Please. Induction Arguments

    If I could get some help on this as soon as possible, that would be great.

    Here are the quesitons (I took a screenshot because I'm lazy like that )

    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,707
    Thanks
    627
    Hello, AJL!

    Here's the first one . . .


    1)\;1 + 5 + 9 + \hdots + (4n+1) \:=\:(n+1)(2n+1)

    Verify S(1):\;1 + 5 \:=\:(1+1)(2\cdot1+1) . . . true!


    Assume S(k)\!:\;1 + 5 + 9 + \hdots + (4k+1) \:=\:(k+1)(2k+1)


    Add 4(k+1) + 1 to both sides:

    . . 1 + 5 + 9 + \hdots + (4k+1) +[4(k+1)+1]\:=\:(k+1)(2k+1) + [4(k+1)+1]


    The right side is: . 2k^2 + 3k + 1 + 4k + 4 + 1 \:=\:2k^2+7k+6 \:=\:(k+2)(2k+3)


    Hence, we have: . 1 + 5 + 9 + \hdots + (4k+1) +[4(k+1)+1]\:=\:[(k+1)+1][2(k+1) + 1]


    And we have proved S(k+1) . . . Therefore, S(n) is true.

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,888
    Thanks
    326
    Awards
    1
    2) 2^{2n}-1 is divisible by 3 for n = 1, 2, 3,...

    The n = 1 case is trivial: 2^{2 \cdot 1} - 1 = 3.

    So assume the problem is true for n = k. Then we need to show that
    2^{2(k+1)} - 1 is divisible by 3.

    Let 2^{2k} - 1 = 3m for some integer m. Then we know that 2^{2k} = 3m + 1.

    Now, 2^{2(k+1)} = 2^{2k+2} = 4 \cdot 2^{2k} = 4(3m + 1) = 12m + 4

    So 2^{2(k+1)} - 1 = 12m + 4 - 1 = 12m + 3 = 3(4m + 1).

    Thus 2^{2(k+1)} - 1 is divisible by 3.

    If you know modular Mathematics:

    2^{2k}-1 \equiv 0 (mod 3) then 2^{2k} \equiv 1 (mod 3). Thus 2^{2(k+1)} = 2^{2k+2} = 4 \cdot 2^{2k}\equiv 1 \cdot 1 = 1 (mod 3). Thus 2^{2(k+1)} - 1 \equiv 0 (mod 3).

    Thus 2^{2(k+1)} - 1 is also divisible by 3.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,888
    Thanks
    326
    Awards
    1
    3) \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + ... + \frac{1}{n \cdot (n+1)} = \frac{n}{n+1}

    For n = 1:
    \frac{1}{1 \cdot 2} = \frac{1}{1+1} = \frac{1}{2}
    Check!

    Assume this is true for some n = k. We need to show that
    \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + ... + \frac{1}{(k+1)(k+2)} = \frac{k+1}{k+2}

    Well, the first k terms of this sum to \frac{k}{k+1} according to assumption, so we need to show
    \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} = \frac{k+1}{k+2}

    \frac{k}{k+1} + \frac{1}{(k+1)(k+2)}

    \frac{k(k+2)}{(k+1)(k+2)} + \frac{1}{(k+1)(k+2)}

    \frac{k(k+2)+1}{(k+1)(k+2)}

    \frac{k^2+2k + 1}{(k+1)(k+2)}

    \frac{(k+1)^2}{(k+1)(k+2)}

    \frac{k+1}{k+2}

    As advertised.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,888
    Thanks
    326
    Awards
    1
    HINT: Use the same technique on 4 that I used in 3.

    HINT: The same comment applies for 5, but you need to add a lot of fractions to get there!

    -Dan
    Last edited by topsquark; November 11th 2006 at 05:00 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,888
    Thanks
    326
    Awards
    1
    6) 2n+1 < 2^n

    For n = 3:
    2 \cdot 3 + 1 = 7 < 8 = 2^3
    Check!

    Assume this is true for some n = k. We need to show that:
    2(k+1) + 1 < 2^{k+1}

    2k + 3 \, ? \, 2 \cdot 2^k <-- Divide both sides by 2

    k + \frac{3}{2} \, ? \, 2^k

    But we know that k + \frac{3}{2} < 2k + 1 (You can verify this yourself.)

    Thus k + \frac{3}{2} < 2k + 1 < 2^k

    Thus 2k + 3 < 2^{k+1} (After multiplying both sides by 2, just to make things clearer.)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,888
    Thanks
    326
    Awards
    1
    7) T(0) = 1 and T(n) = 2nT(n-1). Show that T(n) = 2^nn!.

    First, to get rid of the n = 0 case:
    T(0) = 2^00! = 1 \cdot 1 = 1
    Check!

    Now,
    T(1) = 2 \cdot 1 \cdot T(0) = 2
    and
    2^11! = 2 \cdot 1 = 2
    Check!

    So assume this is true for n = k.

    We need to show that T(k+1) = 2(k+1) T(k) = 2^{k+1}(k+1)!

    If the theorem is true for n = k, then T(k) = 2^kk!. So we need to show that
    2(k+1) \cdot 2^kk! = 2^{k+1}(k+1)!

    Well, rearranging the LHS a bit:
    2(k+1) \cdot 2^kk! = \left ( 2\cdot 2^k \right ) (k+1)k! = 2^{k+1}(k+1)!
    as advertised.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,707
    Thanks
    627
    Hello again, AJL!

    \text{If }\,T(0) = 1\,\text{ and }\,T(n) \,= \,2n\!\cdot\!T(n-1)\, \text{ for }n \geq 1,

    \text{then: }\:T(n) \:=\:2^n\!\cdot\!n!\,\text{ for all }n \geq 0.

    Verify S(1):\;\begin{array}{cc}T(1)\:= \\ T(1)\:=\end{array}<br />
\begin{array}{cc}2\!\cdot\!1\!\cdot\!1 \\ 2^1\!\cdot\!1!\end{array}<br />
\begin{array}{cc}=\:2 \\ =\:2\end{array} . . . True!

    Assume S(k):\;T(k) \:=\:2^k\!\cdot\!k!


    Multiply both sides by 2(k+1)\!:

    . . 2(k+1)\!\cdot\!T(k) \;= \;\underbrace{2^k\!\cdot\!2}_\downarrow\cdot\!\und  erbrace{(k+1)\!\cdot\!k!}_\downarrow
    . . \underbrace{2(k+1)\!\cdot\!T(k)}_{\text{This is S(k+1)}} \;=\;2^{k+1}\cdot(k+1)!

    Hence: . T(k+1) \:=\:2^{k+1}\!\cdot(k+1)!


    Therefore, S(n) is true for all n \geq 0.

    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    earboth's Avatar
    Joined
    Jan 2006
    From
    Germany
    Posts
    5,829
    Thanks
    123

    nr. 4 only

    Quote Originally Posted by AJL View Post
    If I could get some help on this as soon as possible, that would be great.

    ...
    Hello, AJL,

    I#ve found another way to solve your problem nr. 4 :

    \left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{4}\right)...\left(1-\frac{1}{n}\right) =

    \left(\frac{1}{2}\right)\left(\frac{2}{3}\right)\l  eft(\frac{3}{4}\right)...\left(\frac{n-1}{n}\right)

    Now you can cancel denominators and numerators except the first "1" and the last "n" which gives you the RHS of your equation.

    EB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. arguments for the distribution
    Posted in the Statistics Forum
    Replies: 1
    Last Post: June 5th 2010, 07:00 AM
  2. Combinatorial arguments
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 26th 2009, 05:02 AM
  3. Help... proving arguments.!!!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 17th 2007, 07:53 AM
  4. Please help translate these arguments.....
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 21st 2007, 12:07 PM
  5. Arguments and Logarithms...
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 4th 2007, 07:24 AM

/mathhelpforum @mathhelpforum