# Mathematical induction with a summation in the problem.

1. Jun 26, 2012

### izic

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. Jun 26, 2012

### CornMuffin

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)

3. Jun 27, 2012

### izic

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
4. Jun 27, 2012

### CornMuffin

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})$

5. Jun 27, 2012

### micromass

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.

6. Jun 27, 2012

### izic

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
7. Jun 27, 2012

### SammyS

Staff Emeritus
See what CornMuffin did?

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

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

Now show that the RHS is equivalent to (k+1)2k+3 + 2

8. Jun 27, 2012

### izic

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
9. Jun 27, 2012

### SammyS

Staff Emeritus
(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.

10. Jun 27, 2012

### izic

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
11. Jun 27, 2012

### SammyS

Staff Emeritus

Distributing as I suggested:

$\displaystyle (k+2)2^{k+2}=k\cdot2^{k+2}+2\cdot2^{k+2}\ .$

Now, add that to the other terms, $\displaystyle k\cdot2^{k+2}+2\ .$

12. Jun 28, 2012

### izic

13. Jun 28, 2012

### Infinitum

That's incorrect...how did you get a 5k??

You have,

$$2^{k+3} + k\cdot 2^{k+2} + k\cdot 2^{k+2} + 2$$

Try factoring out $2^{k+2}$ of the middle two terms, simplify, and then factor $2^{k+3}$ out of the term you get.

14. Jun 28, 2012

### izic

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

15. Jun 28, 2012

### SammyS

Staff Emeritus
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 $\displaystyle 2^{k+3}+k\cdot2^{k+2}+k\cdot2^{k+2}+2\,,$ which is what you started with in your graphic from last post.

You have a repeated term of $\displaystyle k\cdot2^{k+2}\,.$

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

$\displaystyle x+x=2x$

you have

$\displaystyle k\cdot2^{k+2}+k\cdot2^{k+2}=2\left(k\cdot2^{k+2} \right)\,.$

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

Now, how can you write $\displaystyle 2\left(k\cdot2^{k+2} \right)\,$ 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?

$\displaystyle 2^{k+3}+\underline{\quad\text{ ? }\quad}+2\,.$