## mwmnj Group Title Proof help? http://imgur.com/bqFCa 2 years ago 2 years ago

1. mwmnj Group Title

So first step of mathematical induction is show the first case is true, so i plug in 1 for i on the left side and n on the right side:

2. neverforgetvivistee Group Title

lol that's from reddit

3. mwmnj Group Title

$\sum_{1}^{i=1}(1)2^{(1)}=$

4. mwmnj Group Title

Whats from reddit?

5. mwmnj Group Title

So above, on the left i have 2

6. mwmnj Group Title

on the right....

7. strobe Group Title

It's the sum up to n + 1, not n

8. mwmnj Group Title

$(1)2^{((1)+2)}+2 = 2^{3}+2 = 10$

9. mwmnj Group Title

@ strobe, so i am supposed to plug in a 2 instead of a 1?

10. strobe Group Title

It's the sum of the LHS subbed with 1 and 2

11. mwmnj Group Title

LHS?

12. mwmnj Group Title

left hand side

13. strobe Group Title

Yah

14. mwmnj Group Title

ok so the RHS is right

15. mwmnj Group Title

$\sum_{i = 2}^{2} = 2(2)^{2} = 8$

16. mwmnj Group Title

so add that to the first summation and i get 10 on the LHS

17. mwmnj Group Title

so 10 = 10 is true

18. mwmnj Group Title

Is that correct?

19. strobe Group Title

Yes

20. mwmnj Group Title

Ok, thanks, ill see if I can finish the rest from there :)

21. strobe Group Title

Good luck!

22. mwmnj Group Title

after step one (show p(1) is true: step 2 is assume p(k) is true and then show p(k) implies p(k+1)

23. mwmnj Group Title

Cant quite see how i can make that happen at the moment, heres what I have:

24. mwmnj Group Title

$p(k) : \sum_{i=1}^{k+1}i2^{i} = k2^{k+2}+2$

25. mwmnj Group Title

$p(k+1): \sum_{i=1}^{k+2}i2^{i}=(k+1)2^{k+3}+2$

26. mwmnj Group Title

RHS simplifies to $k2^{k+3}+2^{k+3}+2$

27. mwmnj Group Title

So now I need to add something to p(k) to make it match p(k+1)

28. mwmnj Group Title

and if after adding that to p(k) the RHS of p(k) = the RHS of p(k+1), that is sufficient proof

29. strobe Group Title

I wouldn't bother expanding the RHS. I would expand the LHS, then put it in terms of p(k) + something, replace p(k) with the LHS, then rearrange that result so it looks like the LHS of p(k+1)

30. mwmnj Group Title

$p(k)+(k+1)2^{k+1}: \sum_{i=1}^{k+1}i2^{i}+(k+1)2^{k+1}=k2^{k+2}+2+(k+1)2^{k+1}$

31. mwmnj Group Title

Hmm, i was always taught to modify add to p(k) then modify p(k)+ whateverRHS to make it the same as RHS of p(k+1)

32. mwmnj Group Title

This is so freakin complicated

33. mwmnj Group Title

"I would calculate the RHS for k + 1 and then leave it alone. Then try and change the LHS to the same form as the RHS but substituting in the the RHS of p(k) into the LHS."

34. mwmnj Group Title

So first I should calculate the right hand side of p(k+1)?

35. mwmnj Group Title

or of p(k)

36. strobe Group Title

p(k+1), but dont expand or simplify it, leave it as it is. This is what you're aiming for with the LHS.

37. mwmnj Group Title

the LHS of p(k+1)

38. mwmnj Group Title

ok so,

39. mwmnj Group Title

RHS of p(k+1): $(k+1)2^{(k+1)+2}+2$

40. mwmnj Group Title

isnt much calculation to do really, just plug in

41. mwmnj Group Title

Then I want to make LHS of P(k+1) the same as that:

42. mwmnj Group Title

RHS of p(k+1): $\sum_{i=1}^{(k+1)+1}i2^{i}$

43. mwmnj Group Title

*LHS rather

44. strobe Group Title

Yup, so that equals the LHS of p(k) + something, find that something

45. mwmnj Group Title

So I should expand the LHS of p(k+1) first?

46. strobe Group Title

Expand so it looks like LHS of p(k) + something

47. mwmnj Group Title

I would need to add (k+1)2^(k+1) to LHS of p(k) for them to be equal

48. mwmnj Group Title

I just have to show that...

49. strobe Group Title

Okay, so LHS p(k+1) = LHS p(k) + (k+2)2^(k+2) (you almost got it) but we know LHS = RHS of p(k), so substitute the LHS with the RHS

50. mwmnj Group Title

$(p(k)LHS)+(k+1)2 ^{k+1}-> (k2^{k+2}+2)+(k+1)2 ^{k+1}$

51. mwmnj Group Title

The substitution into (p(k)LHS) is p(k)RHS

52. mwmnj Group Title

Now I need to make that = the RHS or p(k+1)?

53. mwmnj Group Title

If so, that's the method I am familiar with

54. strobe Group Title

Yup, you'll find it all factorises nicely

55. mwmnj Group Title

ok, I must have bliped up somewhere before then, cause the Q i asked making the sides equal was my next step from here attempted

56. mwmnj Group Title

I'll try it here

57. mwmnj Group Title

so im trying to make $(k2^{k+2}+2)+(k+1)2^{k+1} = (k+1)2^{(k+1)+2}+2$

58. mwmnj Group Title

expanding everything out isnt the way to go?

59. neverforgetvivistee Group Title

yes

60. mwmnj Group Title

it is the way to go?

61. mwmnj Group Title

hmm

62. mwmnj Group Title

p(k): $k2^{k}4+2^{k}2+4$

63. mwmnj Group Title

Im not seeing it :/

64. mwmnj Group Title

Clearly, im totally lost

65. phi Group Title

You have to be very careful with the indices with this problem. We can show the expression works for n=1. Now assume it is true for n=m. Can we show it is true for m+1?

66. mwmnj Group Title

Thats what i tried to show

67. mwmnj Group Title

Did i make an arithmetic error somewhere or is my methodology wrong or what

68. phi Group Title

$\sum_{i=1}^{m+2}i2^i= \sum_{i=1}^{m+1}i2^i + (m+2)w^{m+2}$

69. phi Group Title

not sure where you went wrong. See how we start: We increased m by 1, and then break the sum into two parts.

70. phi Group Title

the first sum on the right hand side "works" because we assume it works for n=m. so we can replace it with $m 2^{m+2} +2$

71. phi Group Title

that "w" in the first formula is a 2 ! $\sum_{i=1}^{m+2}i2^i= \sum_{i=1}^{m+1}i2^i + (m+2)2^{m+2}$ $= 2+ m 2^{m+2} +(m+2)2^{m+2}$

72. mwmnj Group Title

ok

73. mwmnj Group Title

so now I need to set that equal to the right hand side of m+1

74. mwmnj Group Title

or make it equal that at least

75. phi Group Title

I'm still working on it. we want the right hand side equal to what the formula says if we use n= m+1

76. mwmnj Group Title

RHS of m+1:$(m+1)2^{m+3}+2$

77. phi Group Title

that "w" in the first formula is a 2 ! $\sum_{i=1}^{m+2}i2^i= \sum_{i=1}^{m+1}i2^i + (m+2)2^{m+2}$ $= 2+ m 2^{m+2} +(m+2)2^{m+2}$

78. mwmnj Group Title

right we need to make that equal what i just typed up right?

79. mwmnj Group Title

If so, that is this: http://imgur.com/P8Tnf

80. phi Group Title

yes and I believe they are.

81. mwmnj Group Title

Just with m

82. mwmnj Group Title

isnt it or am i missing something?

83. phi Group Title

we have m+2 now, you have k+1

84. phi Group Title

very close, but not close enough!

85. mwmnj Group Title

ok i must have messed that up somewhere

86. phi Group Title

Do you see how to get the "new" version? (with m+2), it's the next term we are adding, with i= (m+2)

87. phi Group Title

It's confusing because we go to n+1 instead of n, so going up one term means n+2. Anyways... can you simplify what we have?

88. mwmnj Group Title

yea, so confusing!

89. phi Group Title

multiply out (m+2) 2^(m+2)

90. mwmnj Group Title

making it m made it less tho

91. mwmnj Group Title

lets see

92. phi Group Title

we get $2+ m 2^{m+2}+m2^{m+2} + 2^{m+3}$

93. mwmnj Group Title

on LHS right

94. mwmnj Group Title

thats not the same tho

95. mwmnj Group Title

thats $2+2m ^{m+2}+2^{m+3}$

96. mwmnj Group Title

on the LHS

97. phi Group Title

add the two m2^(m+2) to get m*2*2^(m+2) = m*2^(m+3)

98. mwmnj Group Title

RHS is $2+m2^{m+3}+2^{m+3}+2$

99. mwmnj Group Title

Ah yes

100. mwmnj Group Title

Now I see it :)

101. phi Group Title

you have an extra 2 in there. But factor out 2^(m+3) to get $2+ (m+1) 2^{m+3}$

102. mwmnj Group Title

Let me try and write this out and think it out

103. mwmnj Group Title

hopefully fully see where i bliped up

104. phi Group Title

ok have fun

105. mwmnj Group Title

Thanks so much

106. mwmnj Group Title

Will post here when done

107. mwmnj Group Title
108. phi Group Title

I would tweak it a bit. Your statement showing that the formula works for p(1) is not clear. It is better to state: by definition $p(1)=\sum_{1}^{2} i2^i= 1\cdot2^1+2\cdot 2^2= 10$ From the formula, p(1) is $p(1)= 1 \cdot 2^{(1+2)}+2=10$ therefore the formula holds for n=1 Also add a short explanation of what you are doing in part 2b. For example, The formula gives p(k+1) as .... and for the second part: By definition, p(k+1)= .... Finally, point out where you are making use of the assumption that the formula is assumed to be true for p(k). This is where you replace the summation with the results of the formula.