2nd order recursion (1 Viewer)

tito981

Well-Known Member
Joined
Apr 28, 2020
Messages
326
Location
Orange
Gender
Male
HSC
2021
anyone know where to find good q's for 2nd order recursion proofs, Cambridge only has a handful of basic ones, not sure where to find anymore. Also i dont want to look through past papers as i would like to keep them for trial period. thanks.
 

idkkdi

Well-Known Member
Joined
Aug 2, 2019
Messages
2,454
Gender
Male
HSC
2021
anyone know where to find good q's for 2nd order recursion proofs, Cambridge only has a handful of basic ones, not sure where to find anymore. Also i dont want to look through past papers as i would like to keep them for trial period. thanks.
isnt recursion 3u?
 

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
Are you after examples of proving the formula for given a recursion relationship and initial conditions, or more challenging material that uses second order recursions?
 

tito981

Well-Known Member
Joined
Apr 28, 2020
Messages
326
Location
Orange
Gender
Male
HSC
2021
Are you after examples of proving the formula for given a recursion relationship and initial conditions, or more challenging material that uses second order recursions?
both ive seen the Un realtionships but i can only find first order ones. I would also like more challenging recursion material if possible.
 

CM_Tutor

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


The Fibonacci Sequence is defined as follows:





for all integers

One formula for the general formula for is called Binet's formula, which states that, for all non-negative integers :



Question 1
(a) Prove by induction that
.​

(b) Prove, without using induction, that
.​

(c) Hence, simplify
.​

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 .

Question 3
(a) Show that for all .

(b) Find the smallest integer such that .

(c) Hence, prove that for all integers

Question 4
(a) Using induction, prove that, if then for all integers .

(b) Using the result in part (a), derive Binet's formula.

(c) Use strong induction to provide a different proof of Binet's formula, that

where and .​
Note that is often called the "golden ratio."

(d) Show that
and hence show that as .

(e) Use Binet's formula to prove that
and hence, or otherwise, show that

Question 5
Let

(a) Show that
.​
Note: This result is only true if .

(b) Explain why the result is invalid for and .

(c) Find the value of

Question 6
The Lucas Numbers are a set of numbers that are closely related to the Fibonacci sequence. They are defined by:





for all integers

(a) Prove that for all

(b) Prove that for all integers

(c) A general formula used for calculating large Fibonacci numbers is .

(c)(i) Prove this result by induction on by taking as a constant.

(c)(ii) A result given in question 2(c) was that . Show that this is a special case of the general formula.

(c)(iii) Show that the results in 4(e) are also special cases of this formula.

(d) Use the formula in part (c) to prove that .

(e) Using Binet's formula, derive a general formula for .

(f) Show that and hence prove that is irrational for all .
 
Last edited:

CM_Tutor

Moderator
Moderator
Joined
Mar 11, 2004
Messages
2,644
Gender
Male
HSC
N/A
Question 7
In question 2(a), you found that the the , and thus established that .

In question 4(e), the formulae and were established.

(a) Using only the values in the Fibonacci sequence shown above and the formulae from question 4(e), establish that .

(b) Using Binet's formula and the binomial theorem, and without using a calculator, establish the value of . Check your answer using one of the above formulae and comment on the relative difficulty in these approaches for determining the values of members of the Fibonacci sequence without determining them sequentially from the recurrence relation.

(c) Earlier members of the sequence can be calculated from later values if those are known. Show that


and use this result to confirm that .

(d) Find the value of and use your result to find the value of . Check your results using the recurrence relation and your results from (a) and (b).

(e) Show that the prime factorisation of and find the prime factorisation of .

(f) Determine the percentage error in the estimate

(g) In question 6(c), a general calculating formula was proved. Use it to show that, in scientific notation,


and determine the value of the integer .
 

idkkdi

Well-Known Member
Joined
Aug 2, 2019
Messages
2,454
Gender
Male
HSC
2021
Question 7
In question 2(a), you found that the the , and thus established that .

In question 4(e), the formulae and were established.

(a) Using only the values in the Fibonacci sequence shown above and the formulae from question 4(e), establish that .

(b) Using Binet's formula and the binomial theorem, and without using a calculator, establish the value of . Check your answer using one of the above formulae and comment on the relative difficulty in these approaches for determining the values of members of the Fibonacci sequence without determining them sequentially from the recurrence relation.

(c) Earlier members of the sequence can be calculated from later values if those are known. Show that


and use this result to confirm that .

(d) Find the value of and use your result to find the value of . Check your results using the recurrence relation and your results from (a) and (b).

(e) Show that the prime factorisation of and find the prime factorisation of .

(f) Determine the percentage error in the estimate

(g) In question 6(c), a general calculating formula was proved. Use it to show that, in scientific notation,


and determine the value of the integer .
u might as well just write and publish a question book lol.
 

Qeru

Well-Known Member
Joined
Dec 30, 2020
Messages
368
Gender
Male
HSC
2021
A few questions to ponder...


The Fibonacci Sequence is defined as follows:





for all integers

One formula for the general formula for is called Binet's formula, which states that, for all non-negative integers :



Question 1
(a) Prove by induction that
.​

(b) Prove, without using induction, that
.​

(c) Hence, simplify
.​

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 .

Question 3
(a) Show that for all .

(b) Find the smallest integer such that .

(c) Hence, prove that for all integers

Question 4
(a) Using induction, prove that, if then for all integers .

(b) Using the result in part (a), derive Binet's formula.

(c) Use strong induction to provide a different proof of Binet's formula, that

where and .​
Note that is often called the "golden ratio."

(d) Show that
and hence show that as .

(e) Use Binet's formula to prove that
and hence, or otherwise, show that

Question 5
Let

(a) Show that
.​
Note: This result is only true if .

(b) Explain why the result is invalid for and .

(c) Find the value of

Question 6
The Lucas Numbers are a set of numbers that are closely related to the Fibonacci sequence. They are defined by:





for all integers

(a) Prove that for all

(b) Prove that for all integers

(c) A general formula used for calculating large Fibonacci numbers is .

(c)(i) Prove this result by induction on by taking as a constant.

(c)(ii) A result given in question 2(c) was that . Show that this is a special case of the general formula.

(c)(iii) Show that the results in 4(e) are also special cases of this formula.

(d) Use the formula in part (c) to prove that .

(e) Using Binet's formula, derive a general formula for .

(f) Show that and hence prove that is irrational for all .
Since I have no life Ill attempt these (some working may be left out due to sheer number of questions):

1.
(a) n=1 is easy to see. Assume: . Add to both sides: , now use the definition of the fibonacci sequence to get: , therefore true for n=k+1.

(b)The idea is to repeatedly use the definition of the fibonacci sequence on the RHS so:





.
.
.




(c) Replace n with 2n in the result in (a) then subtract the result in (b) to get:






2. (a) 0,1,1,2,3,5,8,13,21,34,55,89,144, even terms are 0,1,3,8,21,55,144... Notice how 3=(2x1)+1. 8=(2x3+1)+1, 21=(2x8+3+1)+1, 55=(2x21+8+3+1)+1 and so on. Therefore a pattern is: . To prove this we use the result in 1(b) replacing n with n-2 to get:







(b) k=0 is trivally true. Assume for k=r i.e. where B is an integer. For k=r+1:



assumption and know that F_4=3

(c) We use a similar method to (b) knowing that the identity could also be used to compute f_12 faster.

3.

(a) Trivial for n=0 and n=1 and n=2 (if you dont count 0 as a natural number). Assume for n=k and n=k+1: and and these two to get:







(b) We can just guess and check this by first writing out a few fibonacci numbers: 0,1,1,2,3,5,8,13 and conclude that m=2 since 5>1x4.

(c) m=2 proven in b. m=3 is also easy to verify . Assume for n=k and n=k+1 and Adding these two:





4.

(a) base case trivial, assume n=k: prove n=k+1,



Fibonacci definition

using the given identity.



assumption

(b) Solving the initial quadratic gives solutions: and let these be and respectively. Therefore we have the simultaneous equations:





Subtracting the equations gives:







So:

(c) n=0,1 basic algebra. Assume true for n=k and n=k+1 and adding:





But we know and since these two constants satisfy the equation:



(d) also: .

As since therefore:

(e)








By product of roots:



it was proven eariler that



To prove the second identity we use the prev identity:


and: Replacing n with n-1 gives:



Now using the definition of the fibonacci sequence in eqn 1:



subbing in eqn 2:












The rest coming soon......
 

Drdusk

Moderator
Moderator
Joined
Feb 24, 2017
Messages
2,025
Location
a VM
Gender
Male
HSC
2018
Uni Grad
2023
Since I have no life Ill attempt these (some working may be left out due to sheer number of questions):

1.
(a) n=1 is easy to see. Assume: . Add to both sides: , now use the definition of the fibonacci sequence to get: , therefore true for n=k+1.

(b)The idea is to repeatedly use the definition of the fibonacci sequence on the RHS so:





.
.
.




(c) Replace n with 2n in the result in (a) then subtract the result in (b) to get:






2. (a) 0,1,1,2,3,5,8,13,21,34,55,89,144, even terms are 0,1,3,8,21,55,144... Notice how 3=(2x1)+1. 8=(2x3+1)+1, 21=(2x8+3+1)+1, 55=(2x21+8+3+1)+1 and so on. Therefore a pattern is: . To prove this we use the result in 1(b) replacing n with n-2 to get:







(b) k=0 is trivally true. Assume for k=r i.e. where B is an integer. For k=r+1:



assumption and know that F_4=3

(c) We use a similar method to (b) knowing that the identity could also be used to compute f_12 faster.

3.

(a) Trivial for n=0 and n=1 and n=2 (if you dont count 0 as a natural number). Assume for n=k and n=k+1: and and these two to get:







(b) We can just guess and check this by first writing out a few fibonacci numbers: 0,1,1,2,3,5,8,13 and conclude that m=2 since 5>1x4.

(c) m=2 proven in b. m=3 is also easy to verify . Assume for n=k and n=k+1 and Adding these two:





4.

(a) base case trivial, assume n=k: prove n=k+1,



Fibonacci definition

using the given identity.



assumption

(b) Solving the initial quadratic gives solutions: and let these be and respectively. Therefore we have the simultaneous equations:





Subtracting the equations gives:







So:

(c) n=0,1 basic algebra. Assume true for n=k and n=k+1 and adding:





But we know and since these two constants satisfy the equation:



(d) also: .

As since therefore:

(e)








By product of roots:



it was proven eariler that



To prove the second identity we use the prev identity:


and: Replacing n with n-1 gives:



Now using the definition of the fibonacci sequence in eqn 1:



subbing in eqn 2:












The rest coming soon......
Nice job! You should attend the BOS trials this year because you seem to really like Maths.
 

Etho_x

Joined
Jun 21, 2019
Messages
824
Location
Sydney
Gender
Male
HSC
N/A
Since I have no life Ill attempt these (some working may be left out due to sheer number of questions):

1.
(a) n=1 is easy to see. Assume: . Add to both sides: , now use the definition of the fibonacci sequence to get: , therefore true for n=k+1.

(b)The idea is to repeatedly use the definition of the fibonacci sequence on the RHS so:





.
.
.




(c) Replace n with 2n in the result in (a) then subtract the result in (b) to get:






2. (a) 0,1,1,2,3,5,8,13,21,34,55,89,144, even terms are 0,1,3,8,21,55,144... Notice how 3=(2x1)+1. 8=(2x3+1)+1, 21=(2x8+3+1)+1, 55=(2x21+8+3+1)+1 and so on. Therefore a pattern is: . To prove this we use the result in 1(b) replacing n with n-2 to get:







(b) k=0 is trivally true. Assume for k=r i.e. where B is an integer. For k=r+1:



assumption and know that F_4=3

(c) We use a similar method to (b) knowing that the identity could also be used to compute f_12 faster.

3.

(a) Trivial for n=0 and n=1 and n=2 (if you dont count 0 as a natural number). Assume for n=k and n=k+1: and and these two to get:







(b) We can just guess and check this by first writing out a few fibonacci numbers: 0,1,1,2,3,5,8,13 and conclude that m=2 since 5>1x4.

(c) m=2 proven in b. m=3 is also easy to verify . Assume for n=k and n=k+1 and Adding these two:





4.

(a) base case trivial, assume n=k: prove n=k+1,



Fibonacci definition

using the given identity.



assumption

(b) Solving the initial quadratic gives solutions: and let these be and respectively. Therefore we have the simultaneous equations:





Subtracting the equations gives:







So:

(c) n=0,1 basic algebra. Assume true for n=k and n=k+1 and adding:





But we know and since these two constants satisfy the equation:



(d) also: .

As since therefore:

(e)








By product of roots:



it was proven eariler that



To prove the second identity we use the prev identity:


and: Replacing n with n-1 gives:



Now using the definition of the fibonacci sequence in eqn 1:



subbing in eqn 2:












The rest coming soon......
Are you aiming for over a 99.95?
 

Etho_x

Joined
Jun 21, 2019
Messages
824
Location
Sydney
Gender
Male
HSC
N/A
Nice job! You should attend the BOS trials this year because you seem to really like Maths.
Despite what I've heard about the BOS trials being challenging I think this guy gonna ace it, better put some hard as hell q for him if he decides to participate
 

Qeru

Well-Known Member
Joined
Dec 30, 2020
Messages
368
Gender
Male
HSC
2021
Despite what I've heard about the BOS trials being challenging I think this guy gonna ace it, better put some hard as hell q for him if he decides to participate
Trust me every question I've answered on this site is nothing compared to BOS.
 

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

Top