Question

Prove that the sum of i*2^(i-1) from i=1 to n equals (n-1)*2^n using mathematical induction, where n is all natural numbers.

Answer 1

Am I doing something stupid, because for some reason I'm getting different answers for the right and left sides for n = 1

Answer 2

\[\sum_{i=1}^{n}i \cdot 2^{i-1}=(n-1)2^n\]

Answer 3

^ Yes, that's correct.

Answer 4

n=1 we have
\[1 \cdot 2^{1-1}=1 \\ (1-1)2^{1}=0\]
you are right two different things

Answer 5

My teacher's the one who made this worksheet... maybe he made a mistake. I'll ask him tmw thanks.

Answer 6

i wonder if it works for some restriction on the natural numbers...

Answer 7

does it work for n=2?

Answer 8

\[1 \cdot 2^{1-1}+2 \cdot 2^{2-1}=1+4=5 \\ (2-1)2^{2}=1(4)=4\]

Answer 9

Yup.

Answer 10

He probably just made a mistake... I hope, our test is on Wednesday, ha ha.

Answer 11

@ganeshie8 do you think you see the mistake

Answer 12

I wonder if we can correct the problem and then do the problem
because you know you want to be prepared for this test in case he puts correct problems on there

Answer 13

Seems to be off by 1. Adding a 1 to RHS might do it.

Answer 14

You know, he did go on a rant the other day about how we need to know the struggle of coming up with the formula the other day... I'll give it a shot.

Answer 15

yeah

= (n-1)*2^n + 1

Answer 16

@aum noticed something
all the things we got differ by 1

Answer 17

Right of course.

Answer 18

Do you want to try to do the problem now that has been corrected before we assist?

Answer 19

Yup, I'll probably be able to do it now. Thanks :D

Answer 20

i also agree it should be (n-1)*2^n+1

Answer 21

Yup, induction proof works now. Thanks everyone.

Answer 22

seems to me n=3 doesn't work!

Answer 23

\[1 \cdot 2^{1-1}+2 \cdot 2^{2-1}+3 \cdot 2^{3-1}=1+4+12=17 \\ (3-1)2^{3}=2(8)=16\]

Answer 24

oh and of course add 1 to the bottom there

Answer 25

unless i didn't plug in correctly
i'm kinda feeling jittery a little so my screen is shaking in mind

Answer 26

it is working! i just miss calculated

Answer 27

\[\large \sum\limits_{i=0}^nx^i = \dfrac{x^{n+1}-1}{x-1}\]

Answer 28

for a non induction version of the proof, this trick works i think

differentiate both sides with respect to x and plugin in x=2

Answer 29

This is what I did (ignore the stuff in the corner and at the bottom)

Answer 30

im not seeing the base case n=1 ?

Answer 31

Also the "i" on the LHS should remain as "i".
Only the n should be replaced with "k".

Answer 32

also the index variable on left hand side is dummy, don't touch it

Answer 33

Dummy?

Answer 34

\[\sum_{i=1}^{n}i \cdot 2^{i-1}=(n-1)2^n\]

\[\sum_{j=1}^{n}j \cdot 2^{j-1}=(n-1)2^n\]

\[\sum_{\spadesuit =1}^{n}\spadesuit \cdot 2^{\spadesuit -1}=(n-1)2^n\]

Answer 35

the sum doesn't depend on what index variable you choose

Answer 36

thats the reason we call it dummy

Answer 37

** add +1 on right hand side

Answer 38

Okay got it. Thanks.

Answer 39

for an induction proof, the base case is very important. you can't get away with the proof without showing the statement works for n=1

Answer 40

Proposition\(\large P(n)\) : \(\sum\limits_{i=1}^ni\cdot2^{i-1} = (n-1)2^n+1\)

Step1 (Basis of the induction) : \( P(1) = \sum\limits_{i=1}^1i\cdot2^{i-1} = 1\cdot 2^0 = (1-1)2^1 + 1 ~\color{red}{\checkmark } \)

so the given statement works for n=1

Answer 41

Step2 (Assumption) : assume \(\large P(k)\) is true
\[\large \sum\limits_{i=1}^ki\cdot 2^{i-1} = (k-1)2^k+1 \]

Answer 42

Step3 (Induction step) : prove \(\large P(k+1)\) is true
\[\large \cdots \]
\[\large \cdots \]

Answer 43

thats the general structure you need to show in any induction proof

Answer 44

all 3 steps are necessary for the proof to work

Answer 45

Alright. I just cut corners because I knew it worked in my head/here and my teacher never checks the homework anyways. I'd write the whole thing on a test.

Answer 46

that sounds good, your work for P(k+1) looks nice :)

Answer 47

Thanks, but I know it was a simple question, I'm 100% sure that it's gonna be ten times harder on my test... my teacher loves making questions so hard half the class fails, ha ha. but it preps us for uni I guess.