The Student Room Group

Recurrence induction help needed

http://www.mathshelper.co.uk/STEP%20III%202005.pdf

How do we do question 4, first part?

My working:

Spoiler

(edited 8 years ago)
Um, you start by not using k as an indexing variable {i.e. don't write things like u2ku_{2k}), because k is also used as a constant in the question. What you've written is basically incomprehensible because of this.
Reply 2
Original post by DFranklin
Um, you start by not using k as an indexing variable {i.e. don't write things like u2ku_{2k}), because k is also used as a constant in the question. What you've written is basically incomprehensible because of this.


You make a good point, I'm surprised I didn't realise the flaw myself, I've changed all the k's, which I meant as an arbitary positive integer which we assume the assumption holds for, to m's, which fixes that problem. I just have a habit of using k for that but it's invalid in this question. Please have another look.
Original post by Omghacklol
You make a good point, I'm surprised I didn't realise the flaw myself, I've changed all the k's, which I meant as an arbitary positive integer which we assume the assumption holds for, to m's, which fixes that problem. I just have a habit of using k for that but it's invalid in this question. Please have another look.


Hint: Use the first to prove the second, then use the second to prove the first
Original post by Omghacklol
http://www.mathshelper.co.uk/STEP%20III%202005.pdf

How do we do question 4, first part?

My working:

Spoiler

I'm really not clear why you're trying to do here.

By induction hypothesis, we "know stuff" about u2mu_{2m} and u2m+1u_{2m+1}. We want to prove stuff about u2m+2u_{2m+2} and u2m+3u_{2m+3}.
Since the given recurrence doesn't let use find un+2u_{n+2} without knowing un,un+1u_n, u_{n+1}, it's pretty clear that we can only go one step at a time. That is, any attempt to jump straight to u2m+3u_{2m+3} is likely to fail.

Instead, we use the given recurrence to write u2m+2u_{2m+2} in terms of u2m+1u_{2m+1} and u2mu_{2m}. We then use our induction hypothesis to show u2m+2=(b/a)u2m+1u_{2m+2} = (b/a) u_{2m+1}. Then we use the given recurrence to write u2m+3u_{2m+3} in terms of u2m+2u_{2m+2} and u2m+1u_{2m+1}. And then use our IH and what we've just proved to show that u2m+3=cu2m+2u_{2m+3} = c u_{2m+2}
Reply 5
Original post by DFranklin
I'm really not clear why you're trying to do here.

By induction hypothesis, we "know stuff" about u2mu_{2m} and u2m+1u_{2m+1}. We want to prove stuff about u2m+2u_{2m+2} and u2m+3u_{2m+3}.
Since the given recurrence doesn't let use find un+2u_{n+2} without knowing un,un+1u_n, u_{n+1}, it's pretty clear that we can only go one step at a time. That is, any attempt to jump straight to u2m+3u_{2m+3} is likely to fail.

Instead, we use the given recurrence to write u2m+2u_{2m+2} in terms of u2m+1u_{2m+1} and u2mu_{2m}. We then use our induction hypothesis to show u2m+2=(b/a)u2m+1u_{2m+2} = (b/a) u_{2m+1}. Then we use the given recurrence to write u2m+3u_{2m+3} in terms of u2m+2u_{2m+2} and u2m+1u_{2m+1}. And then use our IH and what we've just proved to show that u2m+3=cu2m+2u_{2m+3} = c u_{2m+2}


Original post by Renzhi10122
Hint: Use the first to prove the second, then use the second to prove the first


Thank you very much, I get it now.

Quick Reply

Latest