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

1. anonymous

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

lol that's from reddit

3. anonymous

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

4. anonymous

Whats from reddit?

5. anonymous

So above, on the left i have 2

6. anonymous

on the right....

7. anonymous

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

8. anonymous

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

9. anonymous

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

10. anonymous

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

11. anonymous

LHS?

12. anonymous

left hand side

13. anonymous

Yah

14. anonymous

ok so the RHS is right

15. anonymous

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

16. anonymous

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

17. anonymous

so 10 = 10 is true

18. anonymous

Is that correct?

19. anonymous

Yes

20. anonymous

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

21. anonymous

Good luck!

22. anonymous

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

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

24. anonymous

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

25. anonymous

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

26. anonymous

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

27. anonymous

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

28. anonymous

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

29. anonymous

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

$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. anonymous

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

This is so freakin complicated

33. anonymous

"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. anonymous

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

35. anonymous

or of p(k)

36. anonymous

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

the LHS of p(k+1)

38. anonymous

ok so,

39. anonymous

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

40. anonymous

isnt much calculation to do really, just plug in

41. anonymous

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

42. anonymous

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

43. anonymous

*LHS rather

44. anonymous

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

45. anonymous

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

46. anonymous

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

47. anonymous

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

48. anonymous

I just have to show that...

49. anonymous

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

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

51. anonymous

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

52. anonymous

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

53. anonymous

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

54. anonymous

Yup, you'll find it all factorises nicely

55. anonymous

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

I'll try it here

57. anonymous

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

58. anonymous

expanding everything out isnt the way to go?

59. anonymous

yes

60. anonymous

it is the way to go?

61. anonymous

hmm

62. anonymous

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

63. anonymous

Im not seeing it :/

64. anonymous

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

Thats what i tried to show

67. anonymous

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

ok

73. anonymous

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

74. anonymous

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

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

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

79. anonymous

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

80. phi

yes and I believe they are.

81. anonymous

Just with m

82. anonymous

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

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

yea, so confusing!

89. phi

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

90. anonymous

making it m made it less tho

91. anonymous

lets see

92. phi

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

93. anonymous

on LHS right

94. anonymous

thats not the same tho

95. anonymous

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

96. anonymous

on the LHS

97. phi

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

98. anonymous

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

99. anonymous

Ah yes

100. anonymous

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

Let me try and write this out and think it out

103. anonymous

hopefully fully see where i bliped up

104. phi

ok have fun

105. anonymous

Thanks so much

106. anonymous

Will post here when done

107. anonymous
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.