1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Mathematical induction with a summation in the problem.

  1. Jun 26, 2012 #1
    Hi, I'm currently taking Discrete Mathematics and I'm working on a mathematical induction problem that's a little different than usual because it has a summation in it. What I basically want to know is did I do parts A and C correctly?

    1. The problem statement, all variables and given/known data
    2. Relevant equations
    3. The attempt at a solution

    http://i48.tinypic.com/s118q8.png
     
    Last edited by a moderator: Jun 27, 2012
  2. jcsd
  3. Jun 26, 2012 #2
    This problem asks you to prove the statement for n greater or equal to 0, not 1, so you would need to use n=0 for part A. The base case is like your "starting point".


    For part C, write out all your steps, your equality is basically what you are trying to prove. (start by breaking up the summation into the summation from i=1 to i=k+1 plus the term when i=k+2, because we already know what this summation is equal to by assumptions. So, you'll have to manipulate this to show that it equals (k+1)2^{k+3}+2)
     
  4. Jun 27, 2012 #3
    Alright so I broke the summation up into three parts - i=1, i=k+1, and i=k+2 and since I already knew what i=k+1 and i=k+2 was, I plugged those values for it. This is what I have so far but to be honest I'm not sure how to go where from here.

    http://i45.tinypic.com/5158xu.jpg
     
    Last edited by a moderator: Jun 27, 2012
  5. Jun 27, 2012 #4
    this isn't the correct way to break up the summation.

    This is what the summation actually means: ##\sum_{i=1}^{k+2} i2^i = (1)(2^1) + (2)(2^2) + ... + (k+1)(2^{k+1}) + (k+2)(2^{k+2})##

    So, we can group the first k+1 terms together to get ##\sum_{i=1}^{k+2}i2^i = (\sum_{i=1}^{k+1}i2^i ) + (k+2)(2^{k+2})##
     
  6. Jun 27, 2012 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    izic: if you post images here, please make sure they are small enough to not distort the view. If you can't make them small enough, then please just link the images. I changed the images to links in your older posts.
     
  7. Jun 27, 2012 #6
    Oh so that's what I was missing. But yeah I took what you gave me and I was able to get the Left hand side to look like "(k+1)(k+2)(2^k+3)" which is close to the right hand side "(k+1)(2^k+3)". Did I go about this the right way? All I need to do is cancel (k+2) and the left hand side will finally look like the right hand side.

    http://i47.tinypic.com/2cdjsjd.jpg
     
    Last edited: Jun 27, 2012
  8. Jun 27, 2012 #7

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    See what CornMuffin did?

    Then, since we are assuming that [itex]\displaystyle \sum_{i=1}^{k+1}i\cdot2^i =k\cdot2^{k+2}+2\ ,[/itex]

    we now have that [itex]\displaystyle \sum_{i=1}^{k+2}i\cdot2^i=\left(k\cdot2^{k+2}+2 \right) +(k+2)(2^{k+2}) \ .[/itex]

    Now show that the RHS is equivalent to (k+1)2k+3 + 2
     
  9. Jun 27, 2012 #8
    First I get, (k * 2^k *2^2 + 2)+ (k+2)(2^k* 2^2).
    Then, (2^k * 2)(k+2) +(k+2)(2^k * 2)

    Can I factor out one "(2^k * 2)(k+2)" since I have two of them?
     
    Last edited: Jun 27, 2012
  10. Jun 27, 2012 #9

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    (k * 2k *22 + 2) ≠ (2k * 2)(k+2) .

    Take (k+2)2k22 and distribute the 2k22 through the (k+2). By the way 2k22 is 2k+2 and 2 times that is 2k+3, which you're looking for.
     
  11. Jun 27, 2012 #10
    I notice that after distributing it, I get k*(2^(k+2)) + (2^(k+3)) (2^(k+2)*k)

    Do you mind explaining how to get these bold parts in the RHS (2^(k+3)+2)(k+1)
    from the left hand side which is this k*(2^(k+2))+ (2^(k+3)) (2^(k+2)*k)?
     
    Last edited: Jun 27, 2012
  12. Jun 27, 2012 #11

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member


    Distributing as I suggested:

    [itex]\displaystyle (k+2)2^{k+2}=k\cdot2^{k+2}+2\cdot2^{k+2}\ .[/itex]

    Now, add that to the other terms, [itex]\displaystyle k\cdot2^{k+2}+2\ .[/itex]
     
  13. Jun 28, 2012 #12
  14. Jun 28, 2012 #13
    That's incorrect...how did you get a 5k?? :confused:

    You have,

    [tex]2^{k+3} + k\cdot 2^{k+2} + k\cdot 2^{k+2} + 2[/tex]

    Try factoring out [itex]2^{k+2}[/itex] of the middle two terms, simplify, and then factor [itex]2^{k+3}[/itex] out of the term you get.
     
  15. Jun 28, 2012 #14
    Alright, I tried that but ended up with (k+1)(2^(k+3)) instead of (k+1)(2^(k+3)+2)). How can I get the "+2" part?
    http://i49.tinypic.com/25q6g51.png
     
  16. Jun 28, 2012 #15

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    It's evident that your algebra skills are lacking. You also appear to skip steps.

    In sure that the main purpose of this exercise was to give you some practice working with inductive proofs. You gave gotten all bogged down in the algebra, which is really quite basic.

    The "+ 2" part never gets combined with anything.

    Let's start with [itex]\displaystyle 2^{k+3}+k\cdot2^{k+2}+k\cdot2^{k+2}+2\,,[/itex] which is what you started with in your graphic from last post.

    You have a repeated term of [itex]\displaystyle k\cdot2^{k+2}\,.[/itex]

    In my opinion, the easiest way to look at this is to recognize this as two of something (added together). So just as

    [itex]\displaystyle x+x=2x[/itex]

    you have

    [itex]\displaystyle k\cdot2^{k+2}+k\cdot2^{k+2}=2\left(k\cdot2^{k+2} \right)\,.[/itex]

    Of course, you can look at it as Infinitum suggested and factor out the common factor of [itex]\displaystyle 2^{k+2}\,.[/itex] This will give the same result.

    Now, how can you write [itex]\displaystyle 2\left(k\cdot2^{k+2} \right)\,[/itex] in simpler form?

    2 times k times "k+2" factors of 2 is the same thing as k times "k+3" factors of 2.

    What does that leave us with?

    [itex]\displaystyle 2^{k+3}+\underline{\quad\text{ ? }\quad}+2\,.[/itex]
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Mathematical induction with a summation in the problem.
Loading...