Results 1 to 2 of 2

Math Help - Discrete math hw

  1. #1
    Newbie
    Joined
    Nov 2008
    From
    san diego, Ca
    Posts
    2

    Discrete math hw

    This is my hw for this week, with which I am having much trouble with:

    http://kodiak.ucsd.edu/alon/cse20/homework/hw5.pdf

    mostly, I need help with #3 and #4.

    For #3, I proved the basis, and am trying to solve the inductive step:

    P(n) + (n+1_step) = P(n+1)

    [ (2(1)+1)/(1+2+3) + ... + [(2n+1)/n(n+1)(n+1)] + [(2(n+1)+1)/(n+1)(n+2)(n+3)] = (n+1)(5(n+1)+7)/4(n+2)(n+3)

    and I'm trying to solve, but keep getting very complicated equations that i can't solve.

    -------------------------

    For #4, I (think I) figured out the formula, (or something like it, because it only works for n>=1), which is number_of_circles_after_nth_generation = [1+4(3^0 + 3^1 + ... + 3^n)]. I'm trying to prove the inductive step:

    P(n) + step = P(n+1)
    (1+4(3^0 + ... + 3^n [+3^(n+1)]) = (2^(n+1)+1) - 4(n+1) - 3

    and I keep backing myself into a corner with solving it ( I'm getting really complicated equations that I know are wrong because he doesn't expect us to know how to solve cubic equations, etc).

    Thank you for helping!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Rhymes with Orange Chris L T521's Avatar
    Joined
    May 2008
    From
    Santa Cruz, CA
    Posts
    2,844
    Thanks
    3
    Quote Originally Posted by entropic.color View Post
    This is my hw for this week, with which I am having much trouble with:

    http://kodiak.ucsd.edu/alon/cse20/homework/hw5.pdf

    mostly, I need help with #3 and #4.

    For #3, I proved the basis, and am trying to solve the inductive step:

    P(n) + (n+1_step) = P(n+1)

    [ (2(1)+1)/(1+2+3) + ... + [(2n+1)/n(n+1)(n+1)] + [(2^(n+1)+1)/(n+1)(n+2)(n+3)] = (n+1)(5(n+1)+7)/4(n+2)(n+3)

    and I'm trying to solve, but keep getting very complicated equations that i can't solve.

    -------------------------

    For #4, I (think I) figured out the formula, (or something like it, because it only works for n>=1), which is number_of_circles_after_nth_generation = [1+4(3^0 + 3^1 + ... + 3^n)]. I'm trying to prove the inductive step:

    P(n) + step = P(n+1)
    (1+4(3^0 + ... + 3^n [+3^(n+1)]) = (2^((n+1)+1)) - 4(n+1) - 3

    and I keep backing myself into a corner with solving it ( I'm getting really complicated equations that I know are wrong because he doesn't expect us to know how to solve cubic equations, etc).

    Thank you for helping!
    I'll help you get started on #3:

    You've already showed that this is true when n=1.

    We now need to assume that this is true for n=k

    This means that \sum_{i=1}^k\frac{2i+1}{i(i+1)(i+2)}=\frac{k(5k+7)  }{4(k+1)(k+2)}

    Now we have to show that its true for n=k+1:

    This means that we need to show that \sum_{i=1}^{k+1}\frac{2i+1}{i(i+1)(i+2)}=\frac{(k+  1)(5k+12)}{4(k+2)(k+3)}

    But \sum_{i=1}^{k+1}\frac{2i+1}{i(i+1)(i+2)}=\sum_{i=1  }^k\frac{2i+1}{i(i+1)(i+2)}+\frac{2k+3}{(k+1)(k+2)  (k+3)}

    Thus, we now see that \sum_{i=1}^k\frac{2i+1}{i(i+1)(i+2)}+\frac{2k+3}{(  k+1)(k+2)(k+3)}=\frac{(k+1)(5k+12)}{4(k+2)(k+3)}

    However, we already know that \sum_{i=1}^k\frac{2i+1}{i(i+1)(i+2)}=\frac{k(5k+7)  }{4(k+1)(k+2)}.

    Therefore we now have to show that \frac{k(5k+7)}{4(k+1)(k+2)}+\frac{2k+3}{(k+1)(k+2)  (k+3)}=\frac{(k+1)(5k+12)}{4(k+2)(k+3)}

    Can you try to take it from here?

    --Chris
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete math
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 22nd 2008, 12:56 AM
  2. Help me, I am new to discrete math
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 25th 2008, 05:15 PM
  3. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 8th 2007, 10:07 AM
  4. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: April 26th 2007, 08:49 AM
  5. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 26th 2007, 12:01 AM

Search Tags


/mathhelpforum @mathhelpforum