## mwmnj 4 years ago Proof help? http://imgur.com/bqFCa

1. mwmnj

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

lol that's from reddit

3. mwmnj

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

4. mwmnj

Whats from reddit?

5. mwmnj

So above, on the left i have 2

6. mwmnj

on the right....

7. strobe

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

8. mwmnj

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

9. mwmnj

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

10. strobe

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

11. mwmnj

LHS?

12. mwmnj

left hand side

13. strobe

Yah

14. mwmnj

ok so the RHS is right

15. mwmnj

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

16. mwmnj

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

17. mwmnj

so 10 = 10 is true

18. mwmnj

Is that correct?

19. strobe

Yes

20. mwmnj

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

21. strobe

Good luck!

22. mwmnj

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

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

24. mwmnj

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

25. mwmnj

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

26. mwmnj

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

27. mwmnj

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

28. mwmnj

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

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

$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

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

This is so freakin complicated

33. mwmnj

"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

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

35. mwmnj

or of p(k)

36. strobe

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

the LHS of p(k+1)

38. mwmnj

ok so,

39. mwmnj

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

40. mwmnj

isnt much calculation to do really, just plug in

41. mwmnj

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

42. mwmnj

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

43. mwmnj

*LHS rather

44. strobe

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

45. mwmnj

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

46. strobe

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

47. mwmnj

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

48. mwmnj

I just have to show that...

49. strobe

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

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

51. mwmnj

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

52. mwmnj

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

53. mwmnj

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

54. strobe

Yup, you'll find it all factorises nicely

55. mwmnj

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

I'll try it here

57. mwmnj

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

58. mwmnj

expanding everything out isnt the way to go?

59. neverforgetvivistee

yes

60. mwmnj

it is the way to go?

61. mwmnj

hmm

62. mwmnj

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

63. mwmnj

Im not seeing it :/

64. mwmnj

Clearly, im totally lost

65. phi

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

Thats what i tried to show

67. mwmnj

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

68. phi

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

69. phi

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

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

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

ok

73. mwmnj

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

74. mwmnj

or make it equal that at least

75. phi

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

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

77. phi

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

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

79. mwmnj

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

80. phi

yes and I believe they are.

81. mwmnj

Just with m

82. mwmnj

isnt it or am i missing something?

83. phi

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

84. phi

very close, but not close enough!

85. mwmnj

ok i must have messed that up somewhere

86. phi

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

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

yea, so confusing!

89. phi

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

90. mwmnj

making it m made it less tho

91. mwmnj

lets see

92. phi

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

93. mwmnj

on LHS right

94. mwmnj

thats not the same tho

95. mwmnj

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

96. mwmnj

on the LHS

97. phi

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

98. mwmnj

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

99. mwmnj

Ah yes

100. mwmnj

Now I see it :)

101. phi

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

102. mwmnj

Let me try and write this out and think it out

103. mwmnj

hopefully fully see where i bliped up

104. phi

ok have fun

105. mwmnj

Thanks so much

106. mwmnj

Will post here when done

107. mwmnj
108. phi

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.