2nd order recursion (1 Viewer)

Etho_x · Jan 24, 2021

Qeru said:
Trust me every question I've answered on this site is nothing compared to BOS.

Do you have any tips lol whenever I come across some big question sometimes I don't even know where to begin or I just can't find a way to get the answer

Qeru · Jan 24, 2021

Etho_x said:
Do you have any tips lol whenever I come across some big question sometimes I don't even know where to begin or I just can't find a way to get the answer

Ill show you my full thought process for q5 tommorow if you want from seeing the question to answering.

Etho_x · Jan 24, 2021

Qeru said:
Ill show you my full thought process for q5 tommorow if you want from seeing the question to answering.

If this is proof which I'm assuming it is I haven't learnt proof yet

Qeru · Jan 24, 2021

Etho_x said:
If this is proof which I'm assuming it is I haven't learnt proof yet

Nah its not, it's just series.

Etho_x · Jan 24, 2021

Qeru said:
Nah its not, it's just series.

Still haven’t learnt

Etho_x · Jan 24, 2021

Qeru said:
Nah its not, it's just series.

Was asking though if you had general tips for math questions in general since you seem to be good at everything with maths on here lol

Trebla · Jan 24, 2021

Etho_x said:
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

Noted

idkkdi · Jan 25, 2021

Trebla said:
Noted

past BOS papers are hard enough. the current record by the imo guy probably wont be broken if the paper is kept at a similar difficulty.
but sure, make the paper more difficult, just don't go beyond STEP III level by too much lol.
*actually don't go past STEP III level plz lol.

Qeru · Jan 25, 2021

CM_Tutor said:
A few questions to ponder...

The Fibonacci Sequence is defined as follows:

$F_0 = 0$

$F_1 = 1$

$F_n = F_{n-1} + F_{n-2}$ for all integers $n \geqslant 2$

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

$F_n = \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n$

Question 1
(a) Prove by induction that

$F_1 + F_2 + F_3 + ... + F_n = F_{n+2} - 1$ .

(b) Prove, without using induction, that

$\sum_{k=0}^n{F_{2k} = F_{2n+1} - 1$ .

(c) Hence, simplify

$F_1 + F_3 + F_5 + ... + F_{2n-1}$ .

Question 2
(a) List the values of $F_n$ for $n \leqslant 12$ 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 $F_{4k}$ are divisible by 3.

(c) Prove that $F_{12k}$ is a multiple of 12. You may use the fact that $F_{6k} = 8F_{6k-5} + 5F_{6k-6}$ .

Question 3
(a) Show that $F_n < 2^n$ for all $n \in \mathbb{N}$ .

(b) Find the smallest integer $m$ such that $F_{m+3} \geqslant 4F_m$ .

(c) Hence, prove that $F_{n+3} \geqslant 4F_n$ for all integers $n \geqslant m$

Question 4
(a) Using induction, prove that, if $x^2 = x + 1$ then $x^n = xF_n + F_{n-1}$ for all integers $n \geqslant 2$ .

(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

$F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$
where $\phi = \frac{1+\sqrt{5}}{2}$ and $\psi = \frac{1-\sqrt{5}}{2}$ .
Note that $\phi$ is often called the "golden ratio."

(d) Show that

$F_n = \frac{\phi^n-(1-\phi)^n}{\sqrt{5}} = \frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}$
and hence show that $F_n \to \frac{\phi^n}{\sqrt{5}}$ as $n \to \infty$ .

(e) Use Binet's formula to prove that

$F_{2n+1} = {F_n}^2 + {F_{n+1}}^2$
and hence, or otherwise, show that

$F_{2n} = F_n\left(F_{n+1} + F_{n-1}\right)$

Question 5
Let $s(x) = \sum_{k=0}^\infty F_k x^k$

(a) Show that

$s(x) = \frac{x}{1-x-x^2}$ .
Note: This result is only true if $|x|<\frac{1}{\phi}$ .

(b) Explain why the result is invalid for $x=1$ and $x=\frac{1}{\phi}$ .

(c) Find the value of

$\frac{F_1}{10} + \frac{F_2}{10^2} + \frac{F_3}{10^3} + ...$

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

$L_0 = 2$

$L_1 = 1$

$L_n = L_{n-1} + L_{n-2}$ for all integers $n \geqslant 2$

(a) Prove that $L_n = F_{n+1} + F_{n-1}$ for all $n \in \mathbb{Z}^+$

(b) Prove that $L_n = F_{n+2} - F_{n-2}$ for all integers $n \geqslant 2$

(c) A general formula used for calculating large Fibonacci numbers is $F_{m+n} = F_{m-1} F_n + F_m F_{n+1}$ .

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

(c)(ii) A result given in question 2(c) was that $F_{6k} = 8F_{6k-5} + 5F_{6k-6}$ . 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 $L_n = \frac{F_{2n}}{F_n}$ .

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

(f) Show that $\phi^n = \frac{L_n + F_n \sqrt{5}}{2} = F_n \phi + F_{n-1}$ and hence prove that $\phi^n$ is irrational for all $n \in \mathbb{Z}^+$ .

Ok Ill show my thought process anyways.

Question 5, the first thing I see is the result as well as the condition: $|x|<\frac{1}{\phi}$ . Without even thinking about how to solve it, the condition should look really familiar if you have done sequences/series, it's very similar to the condition for the infinite geometric sequence. So I know I have to do something with the formula:
$\sum_{k=0}^\infty ar^k=\frac{a}{1-r}$
So the first thing we can learn from this is to know formulas inside out and the look for clues throughout the question.

The next thing I note is how am I actually going to use this formula, and an idea is to use the binet formula descrived eariler (always look for ways to use previous parts of the question) so I replace F_k to get:

$s(x)=\sum_{k=0}^\infty \frac{(\phi^k-\psi^k)}{\sqrt{5}} x^k$

$s(x)=\frac{1}{\sqrt{5}}\sum_{k=0}^\infty (\phi^k-\psi^k) x^k$

$s(x)=\frac{1}{\sqrt{5}}\sum_{k=0}^\infty \phi^kx^k-\frac{1}{\sqrt{5}}\sum_{k=0}^\infty\psi^k x^k$

Ok that was the hard part done then from here it's just applying the formula so:

$s(x)=\frac{1}{\sqrt{5}}\left(\frac{\phi x}{1-\phi x}\right)-\frac{1}{\sqrt{5}}\left(\frac{\psi x}{1-\psi x}\right)$

From here I pause and think what I need to get at the end, and see that it has a common denominator so logically we should form a common denominator:

$s(x)=\frac{1}{\sqrt{5}}\left(\frac{\phi x(1-\psi x)-\psi x(1-\phi x)}{(1-\psi x)(1-\phi x)}\right)$

Now I know I have to expand out the denominator so: $(1-\psi x)(1-\phi x)=1-(\psi +\phi)x+\psi \phi x^2$ . Since $\phi=\frac{\sqrt{5}+1}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}$ $\psi +\phi=1$ and $\psi \phi =-1$ by using simple year 11 algebra. Expanding out the numerator gives: $(\phi-\psi)x=\sqrt{5}x$ again by simple algebra. So in total:

$s(x)=\frac{x}{1-x-x^2}$

So the stuff I did in this question can apply to like 99% of grinding/algebra questions.

1. Most of highschool math is about manipulating symbols and changing forms of stuff. If you master basic algebra+basic identites taught most of these type of questions become a breeze (the only exception I would say is perms/combs+some reasoning questions).

2. Always think about how you are going to relate what you know the question. In this case I knew I had to use the GP sum formula but didn't know how at first (it's ok not to know completely how to do a question at first infact thats normal). Then you gradually unwind the puzzle i.e. using binet's formula made F_k quantifable so that allowed me to use the GP sum formula.

3. Try to look at what you are trying to get to in show questions. Show questions are really cheating because you already know the answer and someone else did the work and got to there, so try to fathom how they got to that point. (again the 1-x-x^2 in the denominator screamed GP sum to me as well as the restriction).

Thats pretty much all I have to say. Not sure if that was useful at all lol.

Qeru · Jan 25, 2021

idkkdi said:
past BOS papers are hard enough. the current record by the imo guy probably wont be broken if the paper is kept at a similar difficulty.
but sure, make the paper more difficult, just don't go beyond STEP III level by too much lol.
*actually don't go past STEP III level plz lol.

Lol the paper is already impossible to do timed (even for a freaking olympiad medalist), and it's getting even harder geez.

idkkdi · Jan 25, 2021

Qeru said:
Lol the paper is already impossible to do timed (even for a freaking olympiad medalist), and it's getting even harder geez.

what did he get again? 80?

Trebla · Jan 25, 2021

idkkdi said:
what did he get again? 80?

Yeah that was the highest ever mark in a BoS trial. However, the guy didn't state rank in the HSC iirc

YonOra · Jan 25, 2021

Trebla said:
Yeah that was the highest ever mark in a BoS trial. However, the guy didn't state rank in the HSC iirc

Who's writing them now?

Trebla · Jan 25, 2021

YonOra said:
Who's writing them now?

There is a team of us who come up with question ideas. I’m mainly responsible for putting those ideas onto the paper itself in a HSC-friendly format and overseeing the process.

YonOra · Jan 25, 2021

Trebla said:
There is a team of us who come up with question ideas. I’m mainly responsible for putting those ideas onto paper and overseeing the process.

Put ur profile pic as a proof for a Q16

idkkdi · Jan 25, 2021

Trebla said:
There is a team of us who come up with question ideas. I’m mainly responsible for putting those ideas onto paper and overseeing the process.

r u an actual mathematician?

Trebla · Jan 25, 2021

idkkdi said:
r u an actual mathematician?

None of us who write the BoS trials are actual mathematicians lol. The only commonality is that we all have studied or are currently studying Maths/Stats at uni. Also, we all have different topic strengths, for example I lean towards applied/stats and others lean more towards the pure side.

jimmysmith560 · Jan 25, 2021

Statistics is a pretty interesting field of study. I completed a stats unit last semester and contrary to my expectations (thinking stats is extremely hard) and me being not so good at maths in general, I actually enjoyed and ended up performing quite well in that unit.

Etho_x · Jan 25, 2021

Trebla said:
None of us who write the BoS trials are actual mathematicians lol. The only commonality is that we all have studied or are currently studying Maths/Stats at uni. Also, we all have different topic strengths, for example I lean towards applied/stats and others lean more towards the pure side.

I’m assuming you’ve done first/second year stats? If so is stats manageable in University

Trebla · Jan 25, 2021

Etho_x said:
I’m assuming you’ve done first/second year stats? If so is stats manageable in University

Yeah, but it’s not for everyone. To really understand stats, you need to see the world in shades of grey (i.e. in relative uncertainties and imperfections) rather than in black/white like you do in maths (i.e. absolute certainties and perfection). If you struggle to have that perspective, then stats will be quite hard to understand.

You kind of already have a taste of stats in HSC Maths Adv (e.g. probability density functions, linear regression) so uni is just an extension of those same concepts.

It also depends on whether you do stats under the business faculty (which is heavy on rote learning and applying formulas in business contexts with little/no derivations) or stats under the science faculty (which is more mathematical/derivations focused).

2nd order recursion (1 Viewer)

ツ

Well-Known Member

ツ

Well-Known Member

ツ

ツ

Administrator

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Administrator

Well-Known Member

Administrator

Well-Known Member

Well-Known Member

Administrator

Le Phénix Trilingue

ツ

Administrator

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