The Student Room Group
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>
Competition - post a photo you've taken of nature >>

More Proof by induction(the rearranging bit)

http://www.physicsandmathstutor.com/download/Maths/A-level/FP1/Papers-Edexcel/January%202013%20QP%20-%20FP1%20Edexcel.pdf

question 8

i can't for the life of me see an end to get to the result

i tried messing about by taking "factors out and compasating by adding or taking away what was needed to make it equal and i've also tried expanding everything and trying to figure out what i need and taking out what i need which should leave me with the answer. But it hasn't. Expanding things is what i've done down below

Uk+1=Uk+(k+1)(3(k+1)+1)U_{k+1}= U_k +(k+1)(3(k+1)+1)

Uk+1=k2(k−1)+1+(k+1)(3k+4)U_{k+1}=k^2 (k-1)+1+(k+1)(3k+4)

Uk+1=k3−k2++1+3k2+7k+4U_{k+1}=k^3 -k^2 ++1+3k^2 +7k+4

Uk+1=k3+2k2+7k+5U_{k+1}=k^3 +2k^2 +7k+5

*looks at what i have to prove

*sees he needs (k+1)2×(k+1−1)+1=k(k+1)2+1(k+1)^2 \times (k+1-1)+1=k(k+1)^2 +1

k(k+1)2+1=k3+2k2+kk(k+1)^2 +1=k^3 +2k^2 +k

*take out what he needs

(k3+2k2+k)+6k+5(k^3 +2k^2 +k)+6k+5

Uk+1=k(k+1)2+6k+5U_{k+1}=k(k+1)^2 +6k+5


so what can i do to get a 1? either i screwed up in my calculations or i'm doing it wrong(or the unrare case of both).

Scroll to see replies

Original post by huiop
...


What are you doing on your first line...? That's wrong.

uk+1=uk+k(3k+1)u_{k+1}=u_k+k(3k+1) for n=kn=k
Reply 2
Avatar for Notnek
Notnek
21
Original post by huiop
http://www.physicsandmathstutor.com/download/Maths/A-level/FP1/Papers-Edexcel/January%202013%20QP%20-%20FP1%20Edexcel.pdf

question 8

i can't for the life of me see an end to get to the result

i tried messing about by taking "factors out and compasating by adding or taking away what was needed to make it equal and i've also tried expanding everything and trying to figure out what i need and taking out what i need which should leave me with the answer. But it hasn't. Expanding things is what i've done down below

Uk+1=Uk+(k+1)(3(k+1)+1)U_{k+1}= U_k +(k+1)(3(k+1)+1)

Uk+1=k2(k−1)+1+(k+1)(3k+4)U_{k+1}=k^2 (k-1)+1+(k+1)(3k+4)

Uk+1=k3−k2++1+3k2+7k+4U_{k+1}=k^3 -k^2 ++1+3k^2 +7k+4

Uk+1=k3+2k2+7k+5U_{k+1}=k^3 +2k^2 +7k+5

*looks at what i have to prove

*sees he needs (k+1)2×(k+1−1)+1=k(k+1)2+1(k+1)^2 \times (k+1-1)+1=k(k+1)^2 +1

k(k+1)2+1=k3+2k2+kk(k+1)^2 +1=k^3 +2k^2 +k

*take out what he needs

(k3+2k2+k)+6k+5(k^3 +2k^2 +k)+6k+5

Uk+1=k(k+1)2+6k+5U_{k+1}=k(k+1)^2 +6k+5


so what can i do to get a 1? either i screwed up in my calculations or i'm doing it wrong(or the unrare case of both).

Your first line is wrong. Have another look at it.
Reply 3
Avatar for huiop
huiop
OP
1
Original post by RDKGames
What are you doing on your first line...? That's wrong.

uk+1=uk+k(3k+1)u_{k+1}=u_k+k(3k+1) for n=kn=k


Original post by notnek
Your first line is wrong. Have another look at it.


When u spend about 10 mins typing that out all to find that your first line was wrong ;____;


-.-' i subbed k into the UnU_n oh well.

so that means if uk+1=uk+k(3k+1)u_{k+1}=u_k+k(3k+1) when n=k

then

Uk+1+1=Uk+1+(k+1)(3(k+1)+1)U_{k+1+1}=U_{k+1} +(k+1)(3(k+1)+1)

Uk+2=Uk+(3k+1)+(k+1)(3k+4)U_{k+2}=U_k+(3k+1)+(k+1)(3k+4)

I don't see where i can go with this though... i don't know what value of n U_k takes and i can't see a way to arrange what i have back into the U_n, what i have to prove.
Original post by huiop
When u spend about 10 mins typing that out all to find that your first line was wrong ;____;


-.-' i subbed k into the UnU_n oh well.

so that means if uk+1=uk+k(3k+1)u_{k+1}=u_k+k(3k+1) when n=k

then

Uk+1+1=Uk+1+(k+1)(3(k+1)+1)U_{k+1+1}=U_{k+1} +(k+1)(3(k+1)+1)

Uk+2=Uk+(3k+1)+(k+1)(3k+4)U_{k+2}=U_k+(3k+1)+(k+1)(3k+4)

I don't see where i can go with this though... i don't know what value of n U_k takes and i can't see a way to arrange what i have back into the U_n, what i have to prove.


That's because you're trying to test something for k+1 when you're not required to!

First test the wanted result for n=1n=1
Then assume that result to be true for n=kn=k and write it out for n=k+1n=k+1 which should be in terms of k.
Substitute that in for uk+1u_{k+1} and rearrange for uku_k in the first equation.
You should get the required result to be in terms of k. Since we assumed that the result is true for n=kn=k, it has to be true in terms of n.

This is a slightly different proof than the summation of series. Been a while since I've proven these types by induction so I could be wrong but it makes sense to do it this way. I'm sure others will correct me in the case if I am.
(edited 7 years ago)
Reply 5
Avatar for Notnek
Notnek
21
Original post by huiop
When u spend about 10 mins typing that out all to find that your first line was wrong ;____;


-.-' i subbed k into the UnU_n oh well.

so that means if uk+1=uk+k(3k+1)u_{k+1}=u_k+k(3k+1) when n=k

then

Uk+1+1=Uk+1+(k+1)(3(k+1)+1)U_{k+1+1}=U_{k+1} +(k+1)(3(k+1)+1)

Uk+2=Uk+(3k+1)+(k+1)(3k+4)U_{k+2}=U_k+(3k+1)+(k+1)(3k+4)

I don't see where i can go with this though... i don't know what value of n U_k takes and i can't see a way to arrange what i have back into the U_n, what i have to prove.

An induction proof will always involve you assuming the thing you're trying to prove for e.g. n = k.

You haven't made/used this assumption in your working.

If you're ever stuck with induction, check you've done the initial steps:

Have I proved the base case?
Have I assumed true for n = k ?
Reply 6
Avatar for huiop
huiop
OP
1
Original post by RDKGames
That's because you're trying to test something for k+1 when you're not required to!

First test the wanted result for n=1n=1
Then assume that result to be true for n=kn=k and write it out for n=k+1n=k+1 which should be in terms of k.
Substitute that in for uk+1u_{k+1} and rearrange for uku_k in the first equation.
You should get the required result to be in terms of k. Since we assumed that the result is true for n=kn=k, it has to be true in terms of n.

This is a slightly different proof than the summation of series. Been a while since I've proven these types by induction so I could be wrong but it makes sense to do it this way. I'm sure others will correct me in the case if I am.

so i don't need to test for k+1 because Uk+1U_{k+1} is already the next term?
but then what have i assumed is true for n=k?
Original post by notnek
An induction proof will always involve you assuming the thing you're trying to prove for e.g. n = k.

You haven't made/used this assumption in your working.

If you're ever stuck with induction, check you've done the initial steps:

Have I proved the base case?
Have I assumed true for n = k ?


Ah ok but what about n+1?
Original post by huiop
so i don't need to test for k+1 because Uk+1U_{k+1} is already the next term?
but then what have i assumed is true for n=k?


No, you are not proving the next term of a sequence; you are proving that un=n2(n−1)+1u_n=n^2(n-1)+1 (i.e. the nth term can be expressed in terms of n). If you were proving for the next term, then you would need to prove for un+1u_{n+1}

You are assuming that un=n2(n−1)+1u_n=n^2(n-1)+1 is true for n=kn=k and getting an expression for uk+1u_{k+1} which you then use as a substitution. This is the 'induction' part.
(edited 7 years ago)
Reply 8
Avatar for huiop
huiop
OP
1
Original post by RDKGames
No, you are not proving the next term of a sequence; you are proving that un=n2(n−1)+1u_n=n^2(n-1)+1. If you were proving for the next term, then you would need to prove for un+1u_{n+1}

You are assuming that un=n2(n+1)+1u_n=n^2(n+1)+1 is true for n=kn=k and getting an expression for uk+1u_{k+1} which you then use as a substitution. This is the 'induction' part.


ah i gathered this just as you wrote this post ^-^

Thanks!

Also this is probably a stupid question but what if i sub in n=k and it's not true? o.o
Original post by huiop
ah i gathered this just as you wrote this post ^-^

Thanks!

Also this is probably a stupid question but what if i sub in n=k and it's not true? o.o


What do you mean? You're not subbing in n=kn=k. You're assuming it's true for n=k and subbing in n=k+1n=k+1. If you don't get the result then you're doing it wrong; or if you're 100% sure you do it right and others agree with you, then the proof does not hold. But other proof methods would be used before this is established.
Reply 10
Avatar for huiop
huiop
OP
1
Original post by RDKGames
What do you mean? You're not subbing in n=kn=k. You're assuming it's true for n=k and subbing in n=k+1n=k+1. If you don't get the result then you're doing it wrong; or if you're 100% sure you do it right and others agree with you, then the proof does not hold. But other proof methods would be used before this is established.


sorry bad wording

i'm even more confused now.so far i've assumed true for n=k then Uk=k2(k−1)+1U_k =k^2 (k-1)+1

and Uk+1=Uk+k(3k+1)U_{k+1}= U_k +k(3k+1)

∴Uk+1=k2(k−1)+k(3k+1) \therefore U_{k+1}= k^2 (k-1) +k(3k+1)
Original post by huiop
sorry bad wording

i'm even more confused now.so far i've assumed true for n=k then Uk=k2(k−1)+1U_k =k^2 (k-1)+1

and Uk+1=Uk+k(3k+1)U_{k+1}= U_k +k(3k+1)

∴Uk+1=k2(k−1)+k(3k+1) \therefore U_{k+1}= k^2 (k-1) +k(3k+1)


Again, you're trying to do some proof for with the next term of the sequence. That's not what we're looking for. Assuming it's true for n=k:
uk=k2(k−1)+1u_k=k^2(k-1)+1
∴uk+1=(k+1)2([k+1]−1)+1\therefore u_{k+1}=(k+1)^2([k+1]-1)+1

and use this as a substitution into uk+1=uk+k(3k+1)u_{k+1}=u_k+k(3k+1)
(edited 7 years ago)
Reply 12
Avatar for huiop
huiop
OP
1
Original post by RDKGames
Again, you're trying to do some proof for with the next term of the sequence. That's not what we're looking for. Assuming it's true for n=k:
uk=k2(k−1)+1u_k=k^2(k-1)+1
∴uk+1=(k+1)2([k+1]−1)+1\therefore u_{k+1}=(k+1)^2([k+1]-1)+1

and use this as a substitution into uk+1=uk+k(3k+1)u_{k+1}=u_k+k(3k+1)


so (k+1)2((k+1)+1)=Uk+k(3k+1)(k+1)^2 ((k+1)+1)=U_k +k(3k+1)??
Original post by huiop
so (k+1)2((k+1)+1)=Uk+k(3k+1)(k+1)^2 ((k+1)+1)=U_k +k(3k+1)??


Yes. (though it should be [(k+1)-1] in the bracket on the left)
Reply 14
Avatar for B_9710
B_9710
18
Original post by huiop
sorry bad wording

i'm even more confused now.so far i've assumed true for n=k then Uk=k2(k−1)+1U_k =k^2 (k-1)+1

and Uk+1=Uk+k(3k+1)U_{k+1}= U_k +k(3k+1)

∴Uk+1=k2(k−1)+k(3k+1) \therefore U_{k+1}= k^2 (k-1) +k(3k+1)


You should have Uk+1=k2(k−1)+1+k(3k+1) U_{k+1} = k^2(k-1)+1+k(3k+1) which does in fact simplify and gives the required result.
Reply 15
Avatar for huiop
huiop
OP
1
Original post by RDKGames
Yes. (though it should be [(k+1)-1] in the bracket on the left)

....
Original post by B_9710
You should have Uk+1=k2(k−1)+1+k(3k+1) U_{k+1} = k^2(k-1)+1+k(3k+1) which does in fact simplify and gives the required result.


oh i see so it does.... thanks!
Original post by huiop


oh i see so it does.... thanks!


Keep in mind that would give you the Uk+1U_{k+1}. For UkU_k you'd need to map k↦(k−1)k \mapsto (k-1) on the right side. This would give you the exact same thing as mine would and proof would hold.
(edited 7 years ago)
Reply 17
Avatar for B_9710
B_9710
18
Original post by RDKGames
Keep in mind that would give you the Uk+1U_{k+1}. For UkU_k you'd need to map k↦(k−1)k \mapsto (k-1) on the right side. Would give you the exact same thing as mine would and proof would hold.


The proof for showing the results for Uk U_k or Uk+1 U_{k+1} are equivalent, they're exactly the same. With induction all you need to show is that if the result is true for Uk U_k then using logical arguments it implies that the result is also true for Uk+1 U_{k+1} .
(edited 7 years ago)
Original post by B_9710
The proof for showing the results for Uk U_k or Uk U_k are equivalent, they're exactly the same. With induction all you need to show is that if the result is true for Uk U_k then using logical arguments it implies that the result is also true for Uk+1 U_{k+1} .


I understand that but I think the mark scheme would require you to have UkU_k at the end rather than Uk+1U_{k+1} because it fits their answer that way. Not sure if they're picky about that, though.
Reply 19
Avatar for B_9710
B_9710
18
Original post by RDKGames
I understand that but I think the mark scheme would require you to have UkU_k at the end rather than Uk+1U_{k+1} because it fits their answer that way. Not sure if they're picky about that, though.


It's the same thing, for one of them n=k n=k and for the other n=k+1 n=k+1 .

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you