1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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

    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.

    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
    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.

    Last edited: Jun 27, 2012
  8. Jun 27, 2012 #7


    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


    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


    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?
  16. Jun 28, 2012 #15


    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]
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Mathematical induction summation Date
Induction Proof Jan 16, 2015
Solve this mathematical induction Aug 27, 2014
Mathematical induction ''all horses are the same color'' Aug 12, 2014
Mathematical Induction Jul 11, 2014
Mathematical induction inequality Sep 20, 2013