The Student Room Group

Proof by induction question

Image and question below
Reply 1
Original post by Sha.xo527
Image and question below

6E639023-005C-4703-9504-03071C1B9C1F.jpg
Solution:
90037000-5680-4CCD-BF51-F9170D985A07.png

For the “induction” part of the solution, I don’t understand at all what was done to [the second line] for it to become [the third line]
(edited 6 months ago)
Reply 2
The first term should be (-1)^k, not just (-1). Then factorise out
1/2(-1)^(k+1) (k+1)
from both terms and simplify.
Reply 3
Original post by mqb2766
The first term should be (-1)^k, not just (-1). Then factorise out
1/2(-1)^(k+1) (k+1)
from both terms and simplify.

Ohh. Why (-k…. though? Yes, I understand that 1/2(-1)^(k+1) (k+1) multiplied by -k, would give the original 1/2(-1)^k+1(k+1), but exactly how would it give it?
Reply 4
Original post by Sha.xo527
Ohh. Why (-k…. though? Yes, I understand that 1/2(-1)^(k+1) (k+1) multiplied by -k, would give the original 1/2(-1)^k+1(k+1), but exactly how would it give it?


Not sure what you mean. You want a (-1)^(k+1) and (-1)^k = -1*(-1)^(k+1).
Strictly you divide by -1, but thats obv the same.
Maybe as a passing comment:

I don't like how the marking scheme has written the solution. Aside from the the lack of words, which seems to be something I complain a lot about, the key ingredient in induction is to show where you actually use the induction assumption by literally writing the phrase "by induction assumption" on the correct line (or if you're lazy like me, write "I.A." on the correct equal sign), not at the end.

Also, I tend to start the induction step with "we would like to show that 'blah'", just to know what the goal is.
Sometime (and in fact more often than not) you could get lost in a bunch of calculations that you just forgot what you're trying to achieve. Writing down your goal often gives you a hint as to what your next logical step should be.

For instance in this case, you have in the induction step:
r=1k+1(1)rr2=r=1k(1)rr2+(1)k+1(k+1)2=I.A.12(1)kk(k+1)+(1)k+1(k+1)2\displaystyle\sum^{k+1}_{r=1}(-1)^{r}r^2 =\sum^{k}_{r=1}(-1)^{r}r^2 + (-1)^{k+1}(k+1)^2 \\ \stackrel{I.A.}{=} \frac{1}{2}(-1)^{k}k(k+1)+ (-1)^{k+1}(k+1)^2

If we know explicitly what your goal is, i.e. ...=12(1)k+1(k+1)(k+2)\displaystyle...=\frac{1}{2}(-1)^{k+1}(k+1)(k+2), there is a strong hint that factorizing is a good idea. Of course now it comes down to how good are you at factorizing expressions... (again, borrowing from calculus, people often say calculus is not hard, it's the algebra)
Reply 6
Original post by tonyiptony
Maybe as a passing comment:

I don't like how the marking scheme has written the solution. Aside from the the lack of words, which seems to be something I complain a lot about, the key ingredient in induction is to show where you actually use the induction assumption by literally writing the phrase "by induction assumption" on the correct line (or if you're lazy like me, write "I.A." on the correct equal sign), not at the end.

Also, I tend to start the induction step with "we would like to show that 'blah'", just to know what the goal is.
Sometime (and in fact more often than not) you could get lost in a bunch of calculations that you just forgot what you're trying to achieve. Writing down your goal often gives you a hint as to what your next logical step should be.

For instance in this case, you have in the induction step:
r=1k+1(1)rr2=r=1k(1)rr2+(1)k+1(k+1)2=I.A.12(1)kk(k+1)+(1)k+1(k+1)2\displaystyle\sum^{k+1}_{r=1}(-1)^{r}r^2 =\sum^{k}_{r=1}(-1)^{r}r^2 + (-1)^{k+1}(k+1)^2 \\ \stackrel{I.A.}{=} \frac{1}{2}(-1)^{k}k(k+1)+ (-1)^{k+1}(k+1)^2

If we know explicitly what your goal is, i.e. ...=12(1)k+1(k+1)(k+2)\displaystyle...=\frac{1}{2}(-1)^{k+1}(k+1)(k+2), there is a strong hint that factorizing is a good idea. Of course now it comes down to how good are you at factorizing expressions... (again, borrowing from calculus, people often say calculus is not hard, it's the algebra)

I agree - I advise writing something like Assume true for some n = k then state it

So for n = k+ 1 we have etc.

I guess they are not writing the solution in detail to save space.
Reply 7
Original post by tonyiptony
If we know explicitly what your goal is, i.e. ...=12(1)k+1(k+1)(k+2)\displaystyle...=\frac{1}{2}(-1)^{k+1}(k+1)(k+2), there is a strong hint that factorizing is a good idea. Of course now it comes down to how good are you at factorizing expressions... (again, borrowing from calculus, people often say calculus is not hard, it's the algebra)


Thats true in quite a few questions (trig identities, mechanics, ...) where you should have a clear idea of how you get to the goal, even if the fine detail is a bit uncertain (so think a couple of steps ahead before you start writing in the words of Siklos). Even working back a step or two from the answer sometimes can often make the algebra "obvious" as questions usually require a few lines of algebra.using the right approach.
(edited 6 months ago)
Reply 8
Original post by mqb2766
Not sure what you mean. You want a (-1)^(k+1) and (-1)^k = -1*(-1)^(k+1).
Strictly you divide by -1, but thats obv the same.

I’ll show my question visually so maybe you can understand what I mean:
image.jpg
Reply 9
Original post by tonyiptony
Maybe as a passing comment:

I don't like how the marking scheme has written the solution. Aside from the the lack of words, which seems to be something I complain a lot about, the key ingredient in induction is to show where you actually use the induction assumption by literally writing the phrase "by induction assumption" on the correct line (or if you're lazy like me, write "I.A." on the correct equal sign), not at the end.

Also, I tend to start the induction step with "we would like to show that 'blah'", just to know what the goal is.
Sometime (and in fact more often than not) you could get lost in a bunch of calculations that you just forgot what you're trying to achieve. Writing down your goal often gives you a hint as to what your next logical step should be.

For instance in this case, you have in the induction step:
r=1k+1(1)rr2=r=1k(1)rr2+(1)k+1(k+1)2=I.A.12(1)kk(k+1)+(1)k+1(k+1)2\displaystyle\sum^{k+1}_{r=1}(-1)^{r}r^2 =\sum^{k}_{r=1}(-1)^{r}r^2 + (-1)^{k+1}(k+1)^2 \\ \stackrel{I.A.}{=} \frac{1}{2}(-1)^{k}k(k+1)+ (-1)^{k+1}(k+1)^2

If we know explicitly what your goal is, i.e. ...=12(1)k+1(k+1)(k+2)\displaystyle...=\frac{1}{2}(-1)^{k+1}(k+1)(k+2), there is a strong hint that factorizing is a good idea. Of course now it comes down to how good are you at factorizing expressions... (again, borrowing from calculus, people often say calculus is not hard, it's the algebra)

Understood! I appreciate your help, I was wondering too why the mark scheme did things different from my class
Original post by Sha.xo527
I’ll show my question visually so maybe you can understand what I mean:

(1)k[k(k+1)]=(1)k+1[k(k+1)]=(1)k+1[k(k+1)](-1)^k \left[ k(k+1) \right] = -(-1)^{k+1} \left[ k(k+1)\right] = (-1)^{k+1} \left[-k(k+1) \right]
Reply 11
Original post by Sha.xo527
I’ll show my question visually so maybe you can understand what I mean:
image.jpg


Similar to Dfranklins reply, basically you have
a^k * #
for some expression # and you know the "answer" needs an a^(k+1) factor, so multiply what you have by 1 = a/a, so
a^k * a/a * #
a^(k+1) * #/a
You have your a^(k+1) factor and whats left is #/a. Its really a combination of knowing what you need at the end (a^(k+1) factor as Tony alluded to) and doing a simple operation (multiply by 1=a/a) to get there. Obv for your case a=-1 and #=k so
k/(-1) = -k
(edited 6 months ago)
Reply 12
Original post by mqb2766
a^k * a/a * #
a^(k+1) * #/a
You have your a^(k+1) factor and whats left is #/a.

It all made sense, until this part and specifically the bolded part

I thought that, if you multiplied a^k * a/a * #, it would give you a^k+1 * #, because you only need to multiply a term once with another term. For example, when you do 2 x 3 x 4, it becomes 6 x 4, not 6 x 8. Why why the #/a (bolded part)?
(edited 6 months ago)
Reply 13
Original post by Sha.xo527
It all made sense, until this part and specifically the bolded part

I thought that, if you multiplied a^k * a/a * #, it would give you a^k+1 * #, because you only need to multiply a term once with another term. For example, when you do 2 x 3 x 4, it becomes 6 x 4, not 6 x 8. Why why the #/a (bolded part)?


12 = 3*4 = 3*(3/3)*4 = (3^2)*(4/3)
Youre effectively multiplying by 1 = 3/3. You use the *3 to increase the power of the first term, then you must divide the second term by 3.
Reply 14
Original post by DFranklin
(1)k[k(k+1)]=(1)k+1[k(k+1)]=(1)k+1[k(k+1)](-1)^k \left[ k(k+1) \right] = -(-1)^{k+1} \left[ k(k+1)\right] = (-1)^{k+1} \left[-k(k+1) \right]

Thank you! :smile: One question, the brackets are basically useless right? Because if I had these brackets in mind, I wouldn’t have been able to realise that k becomes -k, given that k was attached to the k+1 via the [ ]” brackets. Are the brackets just for convention, or do they actually serve a purpose? (which would be confusing if they do, because again, I wouldn’t have been able to recognise that k also becomes affected despite being attached to the k+1 via the [ ]” brackets)
(edited 6 months ago)
Reply 15
Original post by mqb2766
12 = 3*4 = 3*(3/3)*4 = (3^2)*(4/3)
Youre effectively multiplying by 1 = 3/3. You use the *3 to increase the power of the first term, then you must divide the second term by 3.

Ahh I understand ^^
Original post by Sha.xo527
Thank you! :smile: One question, the brackets are basically useless right? Because if I had these brackets in mind, I wouldn’t have been able to realise that k becomes -k, given that k was attached to the k+1 via the [ ]” brackets. Are the brackets just for convention, or do they actually serve a purpose? (which would be confusing if they do, because again, I wouldn’t have been able to recognise that k also becomes affected despite being attached to the k+1 via the [ ]” brackets)

The brackets are needed at the end - you'd have a different expression without the brackets. C.f. 3(-4) is -12, but without the brackets you have 3-4 which is -1.

I tried to make it very obvious where the "-k" comes from, but apparently not sufficiently so...

Quick Reply

Latest