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

proof by induction help

I get the jist of pbi but there are some cases where I think how on earth would I think that in the exam. IF you go to the link below in the last example, when n=k+2 how does the 3rd line simplify to the fourth line?

https://iitutor.com/mathematical-induction-divisibility/#:~:text=Basic%20Mathematical%20Induction%20Divisibility,is%20true%20for%20n%3D0%20.&text=Step%202%3A%20Assume%20that%20it,%E2%88%88I%20M%20%E2%88%88%20I%20.
Reply 1
Avatar for Sinnoh
Sinnoh
22
PBI often involves manipulating something from the assumed identity. A recurring theme in these questions is that when you're evaluating the case for n = k+1 or k+2, the expression for when n = k is 'hidden' in there, and the assumption you made about for n = k is required to build a case for n = k+1
Often when you're working with indices, this means reducing the index and bringing it down in front, e.g. 25(5k) instead of 5k+2
Reply 2
Avatar for Mad Man
Mad Man
OP
17
Original post by Sinnoh
PBI often involves manipulating something from the assumed identity. A recurring theme in these questions is that when you're evaluating the case for n = k+1 or k+2, the expression for when n = k is 'hidden' in there, and the assumption you made about for n = k is required to build a case for n = k+1
Often when you're working with indices, this means reducing the index and bringing it down in front, e.g. 25(5k) instead of 5k+2

But how does it simplify to the fourth line?
Reply 3
Avatar for Sinnoh
Sinnoh
22
Original post by Mad Man
But how does it simplify to the fourth line?


Do you mean going from 42×4k+52×5k+62×6k4^2 \times 4^k + 5^2 \times 5^k + 6^2 \times 6^k to 42(15M−5k−6k)+52×5k+62×6k4^2 (15M - 5^k - 6^k) + 5^2 \times 5^k + 6^2 \times 6^k?
Reply 4
Avatar for Mad Man
Mad Man
OP
17
Original post by Sinnoh
Do you mean going from 42×4k+52×5k+62×6k4^2 \times 4^k + 5^2 \times 5^k + 6^2 \times 6^k to 42(15M−5k−6k)+52×5k+62×6k4^2 (15M - 5^k - 6^k) + 5^2 \times 5^k + 6^2 \times 6^k?

No but it's okay, I understand now.
Reply 5
Avatar for Mad Man
Mad Man
OP
17
Why does, in 3) when you do (5+3) x 8^k-3 x 3^k that extra 3 disappear?
Screenshot 2020-09-27 at 1.20.51 PM.png391.9KB
Original post by Mad Man
Why does, in 3) when you do (5+3) x 8^k-3 x 3^k that extra 3 disappear?

It does not disappear. Look at the term 3(8k−3k)3(8^k - 3^k). It is moved here.
Reply 7
Avatar for Mad Man
Mad Man
OP
17
Original post by RDKGames
It does not disappear. Look at the term 3(8k−3k)3(8^k - 3^k). It is moved here.

Shouldn't it be 3^k+1?
Original post by Mad Man
Shouldn't it be 3^k+1?

No, why?
Reply 9
Avatar for Mad Man
Mad Man
OP
17
Original post by RDKGames
No, why?

Can you explain to me what is going on here please? I'm stuck.
Original post by Mad Man
Can you explain to me what is going on here please? I'm stuck.

(5+3)⋅8k⏟expand−3⋅3k\underbrace{(5+3)\cdot 8^k}_{\text{expand}} - 3 \cdot 3^k

=5⋅8k+3⋅8k−3⋅3k⏟factorise= 5 \cdot 8^k + \underbrace{3\cdot 8^k - 3 \cdot 3^k}_{\text{factorise}}

=5⋅8k+3(8k−3k)= 5 \cdot 8^k + 3(8^k - 3^k)
Reply 11
Avatar for Mad Man
Mad Man
OP
17
Original post by RDKGames
(5+3)⋅8k⏟expand−3⋅3k\underbrace{(5+3)\cdot 8^k}_{\text{expand}} - 3 \cdot 3^k

=5⋅8k+3⋅8k−3⋅3k⏟factorise= 5 \cdot 8^k + \underbrace{3\cdot 8^k - 3 \cdot 3^k}_{\text{factorise}}

=5⋅8k+3(8k−3k)= 5 \cdot 8^k + 3(8^k - 3^k)

Oh that makes sense, I like that dot notation, it is easier to understand.

Also, suppose you have 15(15^k) - 3(3^k)
Can you do (15-3)(15^k-3^k)=12f(k)?
Original post by Mad Man
Oh that makes sense, I like that dot notation, it is easier to understand.

Also, suppose you have 15(15^k) - 3(3^k)
Can you do (15-3)(15^k-3^k)=12f(k)?

Nope.

15k+1−3k+1=3k+1⋅5k+1−3k+1=3k+1(5k+1−1)15^{k+1} - 3^{k+1} = 3^{k+1} \cdot 5^{k+1} - 3^{k+1} = 3^{k+1}(5^{k+1} - 1)
Reply 13
Avatar for Mad Man
Mad Man
OP
17
Original post by RDKGames
Nope.

15k+1−3k+1=3k+1⋅5k+1−3k+1=3k+1(5k+1−1)15^{k+1} - 3^{k+1} = 3^{k+1} \cdot 5^{k+1} - 3^{k+1} = 3^{k+1}(5^{k+1} - 1)

How can I get an A* in further maths, because every question I answer is slightly wrong :frown:
Original post by Mad Man
How can I get an A* in further maths, because every question I answer is slightly wrong :frown:

Practice. Should also be said that this is quite a tough question IMHO.

I'm not clear if questions like this come up in FM often enough for it to be worth learning it, but a basic knowledge of modular arithmetic really helps.

For example, in this case it quickly points you to the fact that 4^(2k+1) - 4 is always a multiple of 15, as is 5^(2k+1) - 5 and 6^(2k+1)-6; you can either prove this by induction (after which the actual result is trivial) or at least use it to guide you.

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you