Mathematical induction with a summation in the problem.

[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?

Homework Statement

Homework Equations

The Attempt at a Solution

http://i48.tinypic.com/s118q8.png

 

[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)

 

[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

 

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

 

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

 

[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

 

[SammyS]

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

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)2^k+3 + 2

 

[izic]

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)2^k+3 + 2

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?

 

[SammyS]

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?

(k * 2^k *2² + 2) ≠ (2^k * 2)(k+2) .

Take (k+2)2^k2² and distribute the 2^k2² through the (k+2). By the way 2^k2² is 2^k+2 and 2 times that is 2^k+3, which you're looking for.

 

[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)?

 

[SammyS]

...

Take (k+2)2^k2² and distribute the 2^k2² through the (k+2). By the way 2^k2² is 2^k+2 and 2 times that is 2^k+3, which you're looking for.

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)?

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

 

[izic]

Added them together but it's equaling the right hand side.

http://i50.tinypic.com/33dfbls.png

 

[Infinitum]

Added them together but it's equaling the right hand side.

http://i50.tinypic.com/33dfbls.png

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.

 

[izic]

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.

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

 

[SammyS]

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

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