2nd order recursion (2 Viewers)

idkkdi · Jan 29, 2021

CM_Tutor said:
My specialty is challenging the most able students

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 · Jan 29, 2021

CM_Tutor said:
My specialty is challenging the most able students

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 · Jan 31, 2021

Qeru said:
(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 · Jan 31, 2021

idkkdi said:
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.

CM_Tutor · Jan 31, 2021

YonOra said:
Could you do write up some challenging Q's for Ext1?

I can. If you start a thread in the MX1 forum asking for challenging questions on a particular topic, I'll see what I can put up.

Qeru · Jan 31, 2021

CM_Tutor said:
Question 10

Consider the function

$f(x)=\frac{1-x^{n+1}}{1-x^n}$

(a) Discuss the behaviour of $f(x)$ as $n\to\infty$ for a constant $|x|<1$ .

(b) Define $R= \{R_i\}$ as the set containing the ratios of the ( $i+1$ )-th to the $i$ -th Fibonacci number for integers $i\geqslant1$ and construct two sequences, $S_E=\{R_i \text{, where $i$ is an even number}\}$ , and $S_O=\{R_i \text{, where $i$ is an odd number}\}$ . That is

$S_O = \left\{R_1=\frac{F_2}{F_1} = 1, R_3=\frac{F_4}{F_3} = \frac{3}{2}, R_5=\frac{F_6}{F_5} = \frac{8}{5}, ...\right\}$

$S_E = \left\{R_2=\frac{F_3}{F_2} = 2, R_4=\frac{F_5}{F_4} = \frac{5}{3}, R_6=\frac{F_7}{F_6} = \frac{13}{8}, ...\right\}$

Are these sequences finite? Are they bounded? Discuss.

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

(d) Challenge: Prove that the terms in $S_E$ are strictly ~~increasing~~ decreasing and those in $S_O$ 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 $S_O$ are doing) and decreasing (which is what the terms in the sequence $S_E$ 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 $\frac{F_{2k}}{F_{2k-1}}<\frac{F_{2k+2}}{F_{2k+1}}$ for positive k.

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

$F_{2k+2}F_{2k-1}-F_{2k}F_{2k+1}$
$=\frac{(\phi^{2k+2}-\psi^{2k+2})}{\sqrt{5}} \cdot \frac{(\phi^{2k-1}-\psi^{2k-1})}{\sqrt{5}}-\frac{(\phi^{2k}-\psi^{2k})}{\sqrt{5}} \cdot \frac{(\phi^{2k+1}-\psi^{2k+1})}{\sqrt{5}}$

$=\frac{1}{5} \left(\phi^{4k+1}-\phi^{2k+2}\psi^{2k-1}-\phi^{2k-1}\psi^{2k+2}+\psi^{4k+1}-\phi^{4k+1}+\phi^{2k}\psi^{2k+1}+\phi^{2k+1}\psi^{2k}-\psi^{4k+1}\right)$

$=\frac{1}{5}(\phi^{2k-1}\psi^{2k-1} (\phi \psi^2+\phi^2 \psi -\phi^3-\psi^3))$

$=\frac{\phi^{2k-1}\psi^{2k-1}}{5}(\phi (\psi^2-\phi^2)-\psi (\psi^2 -\phi^2))$

$=\frac{\phi^{2k-1}\psi^{2k-1}}{5}(\phi-\psi)(\psi-\phi)(\psi+\phi)$

but: $\phi-\psi=\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}=\sqrt{5}$

$\phi+\psi=\frac{1+\sqrt{5}}{2}+\frac{1-\sqrt{5}}{2}=1$

$\psi-\phi=\frac{1-\sqrt{5}}{2}-\frac{1+\sqrt{5}}{2}=- \sqrt{5}$

So in total $F_{2k+2}F_{2k-1}-F_{2k}F_{2k+1}>0$ since psi is negative and phi is positive

$\implies F_{2k+2}F_{2k-1}>F_{2k}F_{2k+1}$

$\implies \frac{F_{2k+2}}{F_{2k+1}}>\frac{F_{2k}}{F_{2k-1}}$ Everything's positive so can divide

Same idea for S_E
Fixed thanks to CMtutor

CM_Tutor · Jan 31, 2021

Qeru said:
...

So in total $F_{2k+2}F_{2k-1}-F_{2k}F_{2k+1}<0$ 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 $\psi$ is not positive.

CM_Tutor · Feb 17, 2021

I'd left question 2 and thought I should come back to it...

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}$ .

Solution to 2(a)

What I intended was that

$\left\{F_n, n \leqslant 12\right\} = \left\{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144\right\}$

And the even terms, that is, the terms that are even, are $F_0 = 0$ , $F_3 = 2$ , $F_6 = 8$ , $F_9 = 34$ , and $F_{12} = 144$ . The pattern I sought was that terms of the form $F_{3n}, n \in \mathbb{N}$ , 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 $F_2$ , and noting that

$\text{even } + \text{ even} = 2a + 2b = 2(a + b) = \text{ even}$
$\text{odd } + \text{ odd} = (2a + 1) + (2b + 1) = 2(a + b + 1) = \text{ even}$
$\text{odd } + \text{ even} = \text{even } + \text{ odd} = (2a + 1) + 2b = 2(a + b) + 1 = \text{ odd}$

Hence:

$F_2 = F_1 + F_0 = \text{even } + \text{ odd} = \text{ odd}$
$F_3 = F_2 + F_1 = \text{odd } + \text{ odd} = \text{ even}$
$F_4 = F_3 + F_2 = \text{even } + \text{ odd} = \text{ odd}$
$F_5 = F_4 + F_3 = \text{odd } + \text{ even} = \text{ odd}$
$F_6 = F_5 + F_4 = \text{odd } + \text{ odd} = \text{ even}$

and the pattern will continue...

Solution to 2(b)

Theorem: $F_{4k}$ is divisible by 3 for all $k\in\mathbb{Z}^+$

Proof: By induction on $k$

A Put $k = 1$ :

$F_{4k} = F_4 = 3 \qquad \text{which is divisible by 3}$

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

That is, let $F_{4j} = 3M \qquad \text{for some integer $M$} \qquad \qquad \text{(**)}$

We must now prove the result for $k=j+1$ .

That is, we must prove that $F_{4(j+1)} = 3N \qquad \text{for some integer $N$}$

$\begin{align*} \text{LHS } &= F_{4(j+1)} \\ &= F_{4j+4} \\ &= F_{4j+3} + F_{4j+2} \qquad \text{using the recursive definition of the Fibonacci Sequence, $F_n = F_{n-1} + F_{n-2}$, with $n=4j+4$} \\ &= \left(F_{4j+2} + F_{4j+1}\right) + F_{4j+2} \qquad \text{using the recursive definition of the Fibonacci Sequence with $n=4j+3$} \\ &= 2F_{4j+2} + F_{4j+1} \\ &= 2\left(F_{4j+1} + F_{4j}\right) + F_{4j+1} \qquad \text{using the recursive definition of the Fibonacci Sequence with $n=4j+2$} \\ &= 3F_{4j+1} + 2F_{4j} \\ &= 3F_{4j+1} + 2 \times 3M \qquad \text{using the induction hypothesis (**)} \\ &= 3N \qquad \text{where $N = F_{4j+1} + 2M$ is an integer} \\ &= \text{ RHS} \end{align*}$

So, if the result is true for $k = j$ , then it follows that the result is also true for $k = j + 1$ .

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

Solution to 2(c)

The theorem that $F_{12k}$ must be a multiple of 12 (for all positive integers $k$ ) 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 $F_{3k}$ is divisible by 2 and that $F_{4k}$ is divisible by 3, and $F_{12k} = F_{4(3k)}$ so $F_{12k}$ must be divisible by 3 (and also by 2). Any integer $N$ that is divisible by both $a$ and $b$ must be divisible by $ab$ so long as $a$ and $b$ are coprime. Our given result points to finding a property of $F_{6k}$ , which is that $F_{6k}$ is divisible by 4.

Theorem: $F_{6k}$ is divisible by 4 for all $k\in\mathbb{Z}^+$

Proof: By induction on $k$

A Put $k = 1$ :

$F_{6k} = F_6 = 8 \qquad \text{which is divisible by 4}$

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

That is, let $F_{6j} = 4M \qquad \text{for some integer $M$} \qquad \qquad \text{(**)}$

We must now prove the result for $k=j+1$ .

That is, we must prove that $F_{6(j+1)} = 4N \qquad \text{for some integer $N$}$

$\begin{align*} \text{LHS } &= F_{6(j+1)} \\ &= F_{6j+6} \\ &= 8F_{6j+6-5} + 5F_{6j+6-6} \qquad \text{using the given result $F_{6k} = 8F_{6k-5} + 5F_{6k-6}$ with $k=j+1$} \\ &= 8F_{6j+1} + 5F_{6j} \\ &= 8F_{6j+1} + 5 \times 4M \qquad \text{using the induction hypothesis (**)} \\ &= 4N \qquad \text{where $N = 2F_{6j+1} + 5M$ is an integer} \\ &= \text{ RHS} \end{align*}$

So, if the result is true for $k = j$ , then it follows that the result is also true for $k = j + 1$ .

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

We know that $F_{12k}=F_{4(3k)}$ is divisible by 3 from part (b).

We now know that $F_{12k}=F_{6(2k)}$ is divisible by 4 from the above induction proof.

3 and 4 are coprime, they share no common factors except for 1, and so $F_{12k}$ is divisible by $3 \times 4 = 12$ , as required.

2nd order recursion (2 Viewers)

idkkdi

Well-Known Member

YonOra

Well-Known Member

CM_Tutor

Moderator

CM_Tutor

Moderator

CM_Tutor

Moderator

Qeru

Well-Known Member

CM_Tutor

Moderator

CM_Tutor

Moderator

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