2nd order recursion (1 Viewer)

idkkdi

Well-Known Member
Joined
Aug 2, 2019
Messages
2,454
Gender
Male
HSC
2021
My specialty is challenging the most able students :D

Addendum: I'm not trying to make anyone feel dumb, though. These are challenging questions. I hope that those students who can't do them will learn something about techniques / approaches and the proof topic by looking at them and their answers.
Dude I’m not joking. Will you write a book?
 

YonOra

Well-Known Member
Joined
Apr 21, 2020
Messages
375
Gender
Undisclosed
HSC
2021
My specialty is challenging the most able students :D

Addendum: I'm not trying to make anyone feel dumb, though. These are challenging questions. I hope that those students who can't do them will learn something about techniques / approaches and the proof topic by looking at them and their answers.
Could you do write up some challenging Q's for Ext1?
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
(b) Aren't terms in S_E decreasing and S_O increasing (other way around), or am I misundestanding?

...

(d) Again I think it's the other way around?
Yes, it was the other way around in both cases. Apologies for the typo which happened due to a momentary brain-o! Thanks for pointing it out. I have edited the post to make a correction, noting you as the person who picked it up. :)
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
Dude I’m not joking. Will you write a book?
It's something that I am considering. It's a huge task though, and would need to be done in a way that it was a useful addition to the selection of books already available.

Thanks for the encouragement and interest. :)
 

Qeru

Well-Known Member
Joined
Dec 30, 2020
Messages
368
Gender
Male
HSC
2021
Question 10

Consider the function


(a) Discuss the behaviour of as for a constant .

(b) Define as the set containing the ratios of the ()-th to the -th Fibonacci number for integers and construct two sequences, , and . That is




Are these sequences finite? Are they bounded? Discuss.

(c) Hence, using part (a) or otherwise, and assuming that the terms in are strictly increasing decreasing and those in are strictly decreasing increasing, prove that both sequences approach the same limit and find it.

(d) Challenge: Prove that the terms in are strictly increasing decreasing and those in are strictly decreasing increasing.

Edit note: Following Qeru's post below, I have corrected my mistake in mixing up increasing (which is what the terms in the sequence are doing) and decreasing (which is what the terms in the sequence are doing). I have also modified the start of part (c) so that it is a "hence or otherwise" question.
For part d:

R.T.P for positive k.

I will use Binet's formula again (I feel like I'm abusing it at this point lol):












but:





So in total since psi is negative and phi is positive



Everything's positive so can divide

Same idea for S_E
Fixed thanks to CMtutor
 
Last edited:

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
...

So in total since psi and phi are both positive

...

Im getting the opposite of what is required, I checked my alegbra and signs carefully and there seems to be no error, what did I do wrong?
The mistake is in the quoted bolded part in red, as is not positive.
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
I'd left question 2 and thought I should come back to it...

Question 2
(a) List the values of for and note the pattern of the even terms in the sequence. State a theorem related to generalise this pattern and prove it without using induction.

(b) Use induction to show that all terms of the form are divisible by 3.

(c) Prove that is a multiple of 12. You may use the fact that .

Solution to 2(a)

What I intended was that



And the even terms, that is, the terms that are even, are , , , , and . The pattern I sought was that terms of the form , are even. This can easily proven by induction, but also by noting that the terms follow a pattern of even - odd - odd - even - odd - odd - even - odd - odd - etc. Using the recursive formula from , and noting that
Hence:
and the pattern will continue...

Solution to 2(b)

Theorem: is divisible by 3 for all

Proof: By induction on

A Put :



B Put be a value of for which the result is true,

That is, let

We must now prove the result for .

That is, we must prove that



So, if the result is true for , then it follows that the result is also true for .

C It follows from A and B by the process of mathematical induction that the result is true for all positive integers .

Solution to 2(c)

The theorem that must be a multiple of 12 (for all positive integers ) can be done in exactly the same way as (b), but deriving the necessary result in part B of the proof is long. It can be shortened by using the given result, but there is a better option still.

We have seen that is divisible by 2 and that is divisible by 3, and so must be divisible by 3 (and also by 2). Any integer that is divisible by both and must be divisible by so long as and are coprime. Our given result points to finding a property of , which is that is divisible by 4.

Theorem: is divisible by 4 for all

Proof: By induction on

A Put :



B Put be a value of for which the result is true,

That is, let

We must now prove the result for .

That is, we must prove that



So, if the result is true for , then it follows that the result is also true for .

C It follows from A and B by the process of mathematical induction that the result is true for all positive integers .

We know that is divisible by 3 from part (b).

We now know that is divisible by 4 from the above induction proof.

3 and 4 are coprime, they share no common factors except for 1, and so is divisible by , as required.
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top