2nd order recursion (2 Viewers)

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

5
(b) For an infinite GP $|r|<1$ so $|\phi x|<1 \implies |x|<\frac{1}{\phi}$ since $|\phi|=\phi$ . Therefore $x\neq \frac{1}{\phi}$ Also $\phi>1 \implies \frac{1}{\phi}<1$ so $x\neq 1$ . Another more intuitive explanation, $x=\frac{1}{\phi}$ satisfies the quadratic in the denominator for $s(x)$ so we are dividing by zero. As for x=1, the initial sum becomes the sum of the fibonacci sequence. As the fibanacci sequence increases without bound s(x) diverges.

(c) subbing in x=1/10 gives $s\left(\frac{1}{10}\right)=\frac{\frac{1}{10}}{1-\frac{1}{10}-\frac{1}{10^2}}=\frac{10}{89}$

Q6

(a). n=1 , n=2 is easy to see. Assume n=k and n=k+1 so $L_k=F_{k+1}+F_{k-1}$ and $L_{k+1}=F_{k+2}+F_{k}$ Add these two:

$L_k+L_{k+1}=F_{k+2}+F_{k+1}+F_k+F_{k-1}$

$L_{k+2}=F_{k+3}+F_{k+1}$

$L_{k+2}=F_{(k+2)+1}+F_{(k+2)-1}$

Therefore true for n=k+2.

(b) Using the definition of F_n:

$\text{RHS}=F_{n+1}+F_n-F_{n-2}$

$\text{RHS}=F_{n+1}+F_{n-1}+F_{n-2}-F_{n-2}$

$\text{RHS}=L_n=\text{LHS}$ from (a)

(c) n=0: $\text{LHS}=F_m$ and $\text{RHS}=F_{m-1}F_n+F_mF_1=F_m$

n=1: $\text{LHS}=F_{m+1}$ and $\text{RHS}=F_{m-1}F_1+F_mF_2=F_{m-1}+F_m=F_{m+1}$ by definition.

Assume n=k and n=k+1 and add them up to get:

$F_{m+k}+F_{m+k+1}=F_{m-1}F_k+F_mF_{k+1}+F_{m-1}F_{k+1}+F_mF_{k+2}$

$F_{m+k+2}=F_{m-1}(F_k+F_{k+1})+F_{m}(F_{k+1}+F_{k+2})$

$F_{m+k+2}=F_{m-1}F_{k+2}+F_mF_{k+3}$

$F_{m+k+2}=F_{m-1}F_{(k+2)}+F_mF_{(k+2)+1}$

Therefore true for n=k+1.

(ii)Let m=6 and n=6k-6 in the equation in c (i) so:

$F_{6k}=F_5F_{6k-6}+F_6F_{6k-5}=5F_{6k-6}+8F_{6k-5}$ by knowing what the 5th and 6th fibonacci number is.

(iii) let m=n+1 in the equation in (c) therefore:

$F_{2n+1}=F_nF_n+F_{n+1}F_{n+1}=F_n^2+F_{n+1}^2$

let m=n in the equation in (c) therefore:

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

(d) Using this equation: $F_{2n}=F_{n-1}F_n+F_{n}F_{n+1}=F_n(F_{n-1}+F_{n+1})$

$\frac{F_{2n}}{F_n}=\frac{F_n(F_{n-1}+F_{n+1})}{F_n}=F_{n-1}+F_{n+1}=L_n$ from part (a)

(e) $L_n=\frac{\frac{\phi^{2n} - \psi^{2n}}{\sqrt{5}}}{\frac{\phi^n - \psi^n}{\sqrt{5}}}$ from d

$L_n=\frac{(\phi^n-\psi^n)(\phi^n+\psi^n)}{\phi^n-\psi^n}$

$L_n=\phi^n+\psi^n$

The middle equals:

(f) $\frac{1}{2}\left(\phi^n+\psi^n+\sqrt{5}\left(\frac{\phi^n - \psi^n}{\sqrt{5}}\right)\right)$

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

$=\frac{1}{2}\left(2\phi^n\right)$

$=\phi^n=\text{LHS}$

Also:

$\text{RHS}=\frac{\phi^n - \psi^n}{\sqrt{5}}\phi+\frac{\phi^{n-1} - \psi^{n-1}}{\sqrt{5}}$

$\text{RHS}=\frac{1}{\sqrt{5}}(\phi^{n-1}(\phi^2+1)-\psi^{n-1}(\phi\psi+1)$

$\text{RHS}=\frac{1}{\sqrt{5}}\phi^{n-1}(\phi(\phi-\psi)-\psi^{n-1}((-1)+1))$ since $\phi \psi=-1$

$\text{RHS}=\frac{1}{\sqrt{5}}\phi^{n} \times \sqrt{5}$ since $\phi-\psi=\sqrt{5}$

$\text{RHS}=\phi^{n}=\text{LHS}$

Assume $\phi^n$ is rational so: $\phi^n=\frac{p}{q}$ where p and q are coprime. Then we have the equation:

$\frac{p}{q}=\frac{L_n+F_n\sqrt{5}}{2}$

Since F_n and L_n are both integers the RHS is irrational since $\sqrt{5}$ is irrational. However the LHS is clearly rational therefore there is a contradiction and hence $\phi^n$ is irrational.

CM_Tutor · Jan 27, 2021

@Qeru has done a great job of providing answers, and I'd like to expand on a few parts...

Question 1(a)
Prove by induction that

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

Qeru said:
(a) n=1 is easy to see. Assume: $F_1 + F_2 + F_3 + ... + F_k = F_{k+2} - 1$ . Add $F_{k+1}$ to both sides: $F_1 + F_2 + F_3 + ... + F_k +F_{k+1}= F_{k+2}+F_{k+1} - 1$ , now use the definition of the fibonacci sequence to get: $F_1 + F_2 + F_3 + ... + F_k +F_{k+1}= F_{k+3} - 1$ , therefore true for n=k+1.

Qeru's method is sound and correct, outlining the core of the induction proof approach to this question.

Yes, $n=1$ case is easy to see as $\text{RHS } = F_3 - 1 = 2-1=1=F_1=\text{ LHS}$ but I feel it is important that I state what should be obvious:

In an exam, you must put the evidence to show even the obvious.

I am confident that Qeru knows this... but as someone who has taught for a long time and set and marked exams, it is astonishing to me what can be left out of answers in exams. You only need look at the solutions to past trials where there are comments on common mistakes that repeat that sufficient working is needed for "Show" questions to recognise that this remains a common source of lost marks.

Since we are also looking at exam techniques, it is worth noting that there is a shorter proof possible. The hint is in the form of the RHS being a difference between two terms from the Fibonacci sequence. This suggests that a telescoping sequence might be present here, as indeed it is:

Rearranging the recurrence relation, we find that $F_{n-1}=F_n-F_{n-2}$ (or equivalently $F_k=F_{k+1}-F_{k-1}$ ), which we can use repeatedly in the LHS:

$\begin{align*} \text{LHS } &= F_1 + F_2 + F_3 + ... + F_n \\ &= F_1 + (F_3 - F_1) + (F_4 - F_2) + (F_5 - F_3) + ... + (F_k - F_{k-2}) + (F_{k+1} - F_{k-1}) \\ &= (F_1 - F_1) - F_2 + (F_3 - F_3) + (F_4 - F_4) + ... + (F_{k-1} - F_{k-1}) + F_k + F_{k+1} \\ &= -F_2 + F_k + F_{k+1} \\ &= F_{k+2} - 1 \quad \text{as $F_2=1$ and using the recurrence relation $F_{k+2} = F_k + F_{k+1}$} \\ &= \text{ RHS} \end{align*}$

Of course, this approach is not allowed given the question explicitly stated to use induction, but it is worth noting.

Question 1(b)
Prove, without using induction, that

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

Qeru said:
The idea is to repeatedly use the definition of the fibonacci sequence on the RHS so:

$\text{RHS}=F_{2n+1}-1$

$\text{RHS}=F_{2n}+F_{2n-1}-1$

$\text{RHS}=F_{2n}+F_{2n-2}+F_{2n-3}-1$

...

$\text{RHS}=F_{2n}+F_{2n-2}+F_{2n-4}+F_{2n-6}+...+F_{2}+F_{1}-1$

$\text{RHS}=F_{2n}+F_{2n-2}+F_{2n-4}+F_{2n-6}+...+F_{2}+F_{0}\quad \text{since} \quad F_1-1=F_0$

This approach certainly works, though I was thinking of proving from the LHS using the difference form of the recurrence relation shown in (a), again producing a telescoping sequence:

$\begin{align*} \text{LHS } &= \sum_{k=0}^n{F_{2k}} \\ &= F_0 + F_2 + F_4 + ... + F_{2n} \\ &= F_0 + (F_3 - F_1) + (F_5 - F_3) + (F_7 - F_5) + ... + (F_{2n+1} - F_{2n-1}) \\ &= F_0 - F_1 + (F_3 - F_3) + (F_5 - F_5) + ... + (F_{2n-1} - F_{2n-1}) + F_{2n+1} \\ &= F_{2n+1} - 1 \quad \text{as $F_0 = 0$ and $F_1 = 1$} \\ &=\text{ RHS} \end{align*}$

Question 1(c)
Hence, simplify

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

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

$F_1 + F_2 + F_3 + ... + F_{2n}-(F_{0}+F_{2}+F_{4}+...+F_{2n})=F_{2n+2}-F_{2n+1}$

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

Qeru's approach uses the standard technique, to add into the series the missing terms and then subtract them:

$\begin{align*} F_1 + F_3 + F_5 + ... + F_{2n-1} &= F_0 + F_1 + F_2 + ... + F_{2n} - \left(F_0 + F_2 + F_4 + ... + F_{2n}\right) \\ &= \sum_{k=0}^{2n}{F_{k}} - \sum_{k=0}^{n}{F_{2k}} \\ &= F_{2n+2} - 1 - \left(F_{2n+1} - 1\right) \quad \text{using the results from (a) and (b)} \\ &= F_{2n+2} - F_{2n+1} \\ &= F_{2n+1} + F_{2n} - F_{2n+1} \quad \text{using the Fibonacci sequence recurrence relation} \\ &= F_{2n}\end{align*}$

A similar approach to Qeru's is to extending the result from (a) to $n = 2m$ (a dummy variable) and derive from there:

$\begin{align*} \sum_{k=0}^{2m}{F_{k}} &= F_{2m+2} - 1 \quad \text{using $n=2m$ in the result from (a)} \\ F_0 + F_1 + F_2 + ... + F_{2m} &= F_{2m+1} + F_{2m} - 1 \quad \text{using the Fibonacci sequence recurrence relation} \\ \left(F_0 + F_2 + F_4 + ... + F_{2m}\right) + \left(F_1 + F_3 + F_5 + ... + F_{2m-1}\right) &= F_{2m+1} + F_{2m} - 1 \\ F_{2m+1} - 1 + \left(F_1 + F_3 + F_5 + ... + F_{2m-1}\right) &= F_{2m+1} + F_{2m} - 1 \quad \text{using the result from (b)} \\ F_1 + F_3 + F_5 + ... + F_{2m-1} &= F_{2m} \\ \text{So,} \quad \sum_{k=1}^n{F_{2k-1}} &= F_{2n} \quad \text{after replacing the dummy variable} \end{align*}$

CM_Tutor · Jan 27, 2021

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

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

I disagree. These questions definitely fall into the 'proof' section of MX2.

CM_Tutor · Jan 27, 2021

Question 2(a)

List the values of $\color{blue} F_n$ for $\color{blue} 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.

Qeru said:
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: $F_{2n}=2F_{2n-2}+\sum_{k=0}^{n-2}({F_{2k})+1$ . To prove this we use the result in 1(b) replacing n with n-2 to get:

$\text{RHS}=2F_{2n-2}+(F_{2n-3}-1)+1$

$\text{RHS}=F_{2n-1}+F_{2n-2}$

$\text{RHS}=F_{2n}$

If this was an exam question, looking at Qeru's answer would lead me to two immediate thoughts: (1) There is an ambiguity in this question that I didn't notice, because this isn't at all what I was meaning. (2) Wow! and how I am going to handle the marking for this and the rest of question 2 because the parts are supposed to be related and they aren't.

Qeru has interpreted the phrase "pattern of even terms in this sequence" as referring to the terms with an even index, ie $F_k$ where $k$ is even. What I intended was the pattern where the terms themselves are even - that is, the values 0, 2, 8, 34, 144, ... - which are $F_0, F_3, F_6, F_9, F_{12}, ...$ . The theorem I sought was that $F_{3k}$ is even for all $k \in \mathbb{N}$ .

This is easily proven by induction, but I sought a non-induction proof. I'll leave this here for people to ponder.

Question 2(b)
Use induction to show that all terms of the form $\color{blue} F_{4k}$ are divisible by 3.

Qeru said:
k=0 is trivally true. Assume for k=r i.e. $F_{4r}=3B$ where B is an integer. For k=r+1:

$F_{4r+4}=F_{4r}+F_4$

$F_{4r+4}=3B+3=3(B+1)$ assumption and know that F_4=3

This proof is flawed. The statement that $F_{4r+4}=F_{4r}+F_4$ would need to be proved, but:

$\begin{align*} \text{Test $r=0$:} \quad \text{LHS } &= F_{4r+4} = F_4 = 3 \\ \text{RHS } &= F_{4r} + F_4 = F_0 + F_4 = 3 \\ &= \text{ LHS} \quad \color{blue} \text{Result is TRUE for $r=0$} \end{align*}$

$\begin{align*} \text{Test $r=1$:} \quad \text{LHS } &= F_{4r+4} = F_8 = 21 \\ \text{RHS } &= F_{4r} + F_4 = F_4 + F_4 = 6 \\ &\neq \text{ LHS} \quad \color{red} \text{Result is FALSE for $r=1$} \end{align*}$

$\begin{align*} \text{Test $r=2$:} \quad \text{LHS } &= F_{4r+4} = F_12 = 144 \\ \text{RHS } &= F_{4r} + F_4 = F_8 + F_4 = 24 \\ &\neq \text{ LHS} \quad \color{red} \text{Result is FALSE for $r=2$} \end{align*}$

In fact, this can only be true for $r=0$ as the difference $F_{4r+4}-F_{4r}$ increases with $r$ .

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

I am leaving the proofs of all of question 2 incomplete as there are some potential traps in the proofs here that are worth exploring for yourselves.

CM_Tutor · Jan 27, 2021

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

Qeru said:
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: $F_{k}<2^k$ and $F_{k+1}<2^{k+1}$ and these two to get:

$F_{k}+F_{k+1}<2^k+2^{k+1}$

$F_{k+2}<2^k(1+2)$

$F_{k+2}<2^{k+2} \quad \text{since} \quad 3<4=2^2$

Qeru's proof is an example of strong induction, which is the form of induction where an assumption stronger than "let $k$ be a value of $n$ for which the result is true is required. In this case, the induction hypothesis has an assumption for two consecutive values of $n$ , which is fine so long as in part A of the induction proof, you prove the result true for two initial values. Qeru has done this and so the proof is valid, but it is an easy mistake to make to skip the second initial value.

This result can be proved by a conventional induction, requiring only the assumption of truth for a single value of $n$ , but it is actually more difficult to do than is the strong induction approach that Qeru used. I leave it to people to ponder how to get to $F_{k+1}<2^{k+1}$ with only the assumption that $F_k<2^k$ .

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

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

In fact, anything but trial-and-error is likely to be very messy. The clue to this would be that it would be worth 1 mark only, and so there has to be an easy way.

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

Qeru said:
m=2 proven in b. m=3 is also easy to verify . Assume for n=k and n=k+1 $F_{k+3}\geq4F_k$ and $F_{k+4}\geq4F_{k+1}$ Adding these two:

$F_{k+3}+F_{k+4} \geq 4(F_k+F_{k+1})$

$F_{k+5}\geq4F_{k+2}$

As in part (b), Qeru's strong induction approach simplifies the proof, but again it can be done without strong induction.

Qeru · Jan 27, 2021

Yeah I don't know what I was thinking for 2, sometimes I'm dumb...
2b
$F_{4k+4}=F_{4k+3}+F_{4k+2}=2F_{4k+2}+F_{4k+1}=2F_{4k}+3F_{4k+1}=3(2B+F_{4k+1})$ both integers inside the brackets.

2c Ill use strong induction here:

$F_{12k+12}=8F_{12k+7}+5F_{12k+6}=8(F_{12k+6}+F_{12k+5})+5F_{12k+6}$

$F_{12k+12}=8F_{12k+5}+13F_{12k+6}$

$F_{12k+12}=8(F_{12k+4}+F_{12k+3})+13F_{12k+6}$

$F_{12k+12}=8F_{12k+4}+8(F_{12k+2}+F_{12k+1})+13(F_{12k+1}+F_{12k})$

$F_{12k+12}=8F_{12k+4}+8(2F_{12k+1}+F_{12k})+13(F_{12k+1}+F_{12k})$

$F_{12k+12}=8F_{12k+4}+29F_{12k+1}+21F_{12k}$

$F_{12k+12}=8F_{12k+4}+29F_{12k-1}+40F_{12k}$

The first term is divisble by 12 since $8F_{4(3k+1)}=24M$ where M is an integer, using part b. The second and third terms are also divisible by 12 by assumption and strong induction.

Theres probably a smarter way using a and b that im not seeing.

CM_Tutor · Jan 27, 2021

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

Qeru said:
base case trivial, assume n=k: $x^k=xF_k+F_{k-1}$ prove n=k+1,

$x^{k+1}=xF_{k+1}+F_{k}$

$\text{RHS}=xF_{k-1}+xF_k+F_{k}$ Fibonacci definition

$\text{RHS}=xF_{k-1}+x^2F_k$ using the given identity.

$\text{RHS}=x(F_{k-1}+xF_k)$

$\text{RHS}=x^{k+1}$ assumption

This is correct, but I suggest it can be made clearer with more specific terminology, such as:

$\begin{align*} \text{RHS } &= xF_{k+1} + F_k \\ &= x(F_k + F_{k-1}) + F_k \quad \text{using the Fibonacci sequence recurrence relation} \\ &= xF_{k-1} + (x+ 1)F_k \\ &= xF_{k-1} + x^2F_k \quad \text{as $x^2=x+1$ (given)} \\ &= x(xF_k + F_{k-1}) \\ &= x.x^k \quad \text{using the induction hypothesis (**)} \\ &= x^{k+1} \\ &= \text{ LHS} \end{align*}$

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

Qeru said:
Solving the initial quadratic gives solutions: $x=\frac{1+\sqrt{5}}{2}$ and $x=\frac{1-\sqrt{5}}{2}$ let these be $\phi$ and $\psi$ respectively. Therefore we have the simultaneous equations:

${\phi}^n=\phi F_n+F_{n-1}$

${\psi}^n=\psi F_n+F_{n-1}$

Subtracting the equations gives:

${\phi}^n-{\psi}^n=(\phi-\psi) F_n$

$\frac{{\phi}^n-{\psi}^n}{\phi-\psi}=F_n$

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

So: $F_n=\frac{{\phi}^n-{\psi}^n}{\sqrt{5}}$

Yes, good job!

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

$\color{blue} F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$

where $\color{blue} \phi = \frac{1+\sqrt{5}}{2}$ and $\color{blue} \psi = \frac{1-\sqrt{5}}{2}$ .

Note that $\color{blue} \phi$ is often called the "golden ratio."

Qeru said:
n=0,1 basic algebra. Assume true for n=k and n=k+1 and adding:

$F_k+F_{k+1}=\frac{{\phi}^k-{\psi}^k}{\sqrt{5}}+\frac{{\phi}^{k+1}-{\psi}^{k+1}}{\sqrt{5}}$

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

But we know $\phi^2=\phi+1$ and $\psi^2=\psi+1$ since these two constants satisfy the equation: $x^2=x+1$

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

I was thinking of this as a stand-alone question and thus without part (a) where $\phi^2 = \phi + 1$ and $\psi^2 = \psi + 1$ are established, but these are easily proven from the values and the method is certainly correct.

Question 4(d)
Show that

$\color{blue} F_n = \frac{\phi^n-(1-\phi)^n}{\sqrt{5}} = \frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}$

and hence show that $\color{blue} F_n \to \frac{\phi^n}{\sqrt{5}}$ as $\color{blue} n \to \infty$ .

Qeru said:
$1-\phi=1-\frac{1+\sqrt{5}}{2}=\frac{1-\sqrt{5}}{2}=\psi$ also: $-\phi^{-1}=-\frac{2}{1+\sqrt{5}}=\frac{1-\sqrt{5}}{2}=\psi$ .

As $n \to \infty$ $(-\phi)^{-n}\to 0$ since $0<(-\phi)^{-n}<1$ therefore: $F_n \to \frac{\phi^n}{\sqrt{5}}$

Yes, though more working would be appropriate for a "Show" question, especially for $-\phi^{-1}=\psi$ and the limit.

Question 4(e)
Use Binet's formula to prove that

$\color{blue} F_{2n+1} = {F_n}^2 + {F_{n+1}}^2$

and hence, or otherwise, show that

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

Qeru said:
$F_n^2+F_{n+1}^2$

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

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

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

$=\frac{1}{5}\left(\phi^{2n}(\phi^2-\phi\psi)+\psi^{2n}(\psi^2-\phi\psi)-2\phi^n \psi^n(1-1))\right)$ By product of roots: $\phi \psi=-1$

$=\frac{\phi-\psi}{5}\left(\phi^{2n}(\phi)-\psi^{2n}(\psi)\right)$

$=\frac{\sqrt{5}}{5}\left(\phi^{2n+1}-\psi^{2n+1}\right)$ it was proven eariler that $\phi-\psi=\sqrt{5}$

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

To prove the second identity we use the prev identity:

$F_{2n+1}=F_{n}^2+F_{n+1}^2$

and: Replacing n with n-1 gives:

$F_{2n-1}=F_{n-1}^2+F_{n}^2$

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

$F_{2n}+F_{2n-1}=F_{n}^2+F_{n+1}^2$

subbing in eqn 2:

$F_{2n}+F_{n-1}^2+F_{n}^2=F_{n}^2+F_{n+1}^2$

$F_{2n}=F_{n+1}^2-F_{n-1}^2$

$F_{2n}=(F_{n+1}-F_{n-1})(F_{n+1}+F_{n-1})$

$F_{2n}=(F_{n}+F_{n-1}-F_{n-1})(F_{n+1}+F_{n-1})$

$F_{2n}=F_{n}(F_{n+1}+F_{n-1})$

The first part of the proof is fine.

The second part was a little unclear, with references to equations 1 and 2 that aren't clearly defined. It can also be shortened.

Having established that $F_{2n+1} = {F_n}^2 + {F_{n+1}}^2 \quad \text{. . . . . . . . (1)}$

We can thus see that $F_{2n-1} = {F_{n-1}}^2 + {F_n}^2 \quad \text{. . . . . . . . (2)}$

And then (1) - (2) gives:

$\begin{align*} F_{2n+1} - F_{2n-1} &= {F_n}^2 + {F_{n+1}}^2 - \left({F_{n-1}}^2 + {F_n}^2\right) \\ &= {F_{n+1}}^2 - {F_{n-1}}^2 \\ F_{2n} &= \left(F_{n+1} + F_{n-1}\right)\left(F_{n+1} - F_{n-1}\right) \quad \text{using $F_k = F_{k+1} - F_{k-1}$ with $k=2n$ on LHS} \\ F_{2n} &= F_n\left(F_{n+1} - F_{n-1}\right) \quad \text{using $F_k = F_{k+1} - F_{k-1}$ with $k=n$ on RHS} \end{align*}$

CM_Tutor · Jan 27, 2021

Qeru said:
Yeah I don't know what I was thinking for 2, sometimes I'm dumb...
2b
$F_{4k+4}=F_{4k+3}+F_{4k+2}=2F_{4k+2}+F_{4k+1}=2F_{4k}+3F_{4k+1}=3(2B+F_{4k+1})$ both integers inside the brackets.

2c Ill use strong induction here:

$F_{12k+12}=8F_{12k+7}+5F_{12k+6}=8(F_{12k+6}+F_{12k+5})+5F_{12k+6}$

$F_{12k+12}=8F_{12k+5}+13F_{12k+6}$

$F_{12k+12}=8(F_{12k+4}+F_{12k+3})+13F_{12k+6}$

$F_{12k+12}=8F_{12k+4}+8(F_{12k+2}+F_{12k+1})+13(F_{12k+1}+F_{12k})$

$F_{12k+12}=8F_{12k+4}+8(2F_{12k+1}+F_{12k})+13(F_{12k+1}+F_{12k})$

$F_{12k+12}=8F_{12k+4}+29F_{12k+1}+21F_{12k}$

$F_{12k+12}=8F_{12k+4}+29F_{12k-1}+40F_{12k}$

The first term is divisble by 12 since $8F_{4(3k+1)}=24M$ where M is an integer, using part b. The second and third terms are also divisible by 12 by assumption and strong induction.

Ok, 2(b) is fine.

2(c) works and strong induction does cut it down (the approach of going from $F_{12k} = 12M$ to $F_{12k+12}=144F_{12k+1}+89F_{12k}$ is certainly much longer) but there is an easier way still. The result given is a hint, see if you can see how to use it.

As an extra hint, I note that the intended 2(a) is still there...

Qeru · Jan 27, 2021

CM_Tutor said:
Question 8 - Challenge
In question 2, I gave the formula $F_{6k}=8F_{6k-5}+5F_{6k-6}$ .

A few posts up, @Qeru's answer to 2(b) derived the $F_{4k+4}=2F_{4k}+3F_{4k+1}$ .

In replying to that answer and commenting on 2(c), I stated that $F_{12k+12}=144F_{12k+1}+89F_{12k}$ .

All of these are identities provide ways to write $F_{a+b}$ in terms of $F_a$ and $F_{a+1}$ .

See if you can find a generalisation, or even a formula for $F_{a+b}$ in terms of $F_a$ and $F_b$ and prove it is true.

I am marking this as a "Challenge" as it written too broadly to be an exam question, though it could be an exam question with some structure provided.

Isn't this just question 6c?

CM_Tutor · Jan 27, 2021

Qeru said:
Isn't this just question 6c?

Yes, though in a less structured form...

I've removed it. Using the 6(c) formula makes the direct approach to 2(c) much easier, though of course you couldn't use it in an exam without a proof.

CM_Tutor · Jan 28, 2021

Question 5

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

(a) Show that

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

Note: This result is only true if $\color{blue} |x|<\frac{1}{\phi}$ .

Qeru said:
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, I am really really really impressed with this answer. Recognising the way to use Binet's Formula and infinite series is beyond what most MX2 students can do. Seriously, I didn't expect that anyone would see this way to do the question. I was contemplating putting up a similar question on the Lucas numbers and providing the structure to get to the series interpretation and hence demonstrate the reason for the bounds, and you've jumped through the process backwards to get the forms of $s(x)$ . MX2 readers should be aware that the insight that Qeru has shown is not expected and the question was intended to approached in a different way. The advice on looking for clues in the form and structure of questions is excellent, too, and worth bearing in mind.

I'll let people ponder the answer that I was thinking of, but I will say that it starts with the given form of $s(x)$ and does not involved Binet's Formula.

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

Qeru said:
For an infinite GP $|r|<1$ so $|\phi x|<1 \implies |x|<\frac{1}{\phi}$ since $|\phi|=\phi$ . Therefore $x\neq \frac{1}{\phi}$ Also $\phi>1 \implies \frac{1}{\phi}<1$ so $x\neq 1$ . Another more intuitive explanation, $x=\frac{1}{\phi}$ satisfies the quadratic in the denominator for $s(x)$ so we are dividing by zero. As for x=1, the initial sum becomes the sum of the fibonacci sequence. As the fibanacci sequence increases without bound s(x) diverges.

In an exam, I would not accept an answer that amounts to

$\text{we are told that } s(x) =\frac{x}{1-x-x^2} \text{ is only true if } |x| < \frac{1}{\phi}. \\ \text{Since neither $x = 1$ nor $x = \frac{1}{\phi}$ satisfies this restriction then the result is invalid for these values.}$

What I would want was the "more intuitive" explanation that Qeru gave, something like:

$\begin{align*} \text{If $x = \frac{1}{\phi}$ then } s(x) &= \frac{x}{1-x-x^2} \\ &= \frac{\cfrac{1}{\phi}}{1-\cfrac{1}{\phi}-\left(\cfrac{1}{\phi}\right)^2} \quad \text{when $x=\frac{1}{\phi}$} \\ &= \frac{\phi}{\phi^2-\phi-1} \\ &= \frac{\phi}{0}, \text{which is undefined.} \\ \text{However, the series } s(x) &= \sum_{k=0}^\infty F_k x^k \\ &= F_0 + F_1 x + F_2 x^2 + ... \\ &= \frac{F_1}{\phi} + \frac{F_2}{\phi^2} + \frac{F_3}{\phi^3} + ... \text{ is defined for $x = \frac{1}{\phi}$} \\ \text{So, the result that } s(x) &= \frac{x}{1-x-x^2} \text{ is invalid in this case.} \end{align*}$

Similarly, the series form of $s(x)$ gives $s(1) = F_0 + F_1 + F_2 + ...$ , which is well-defined and positive (as every term is positive except for $F_0 = 0$ . However, the result requires

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

and so the result is not valid at $x=1$ .

However, I would award credit for an answer that uses the condition if that condition was independently proven in the answer given, which Qeru has (mostly) done. All that was missing was to note that there are two GPs and so the conditions require both $|x\phi| < 1$ and $|x\psi| < 1$ and since $|\psi|<|\phi|$ , it follows that the intersection of these inequalities (and hence the overall condition) is $|x| < \phi^{-1}$ .

Question 5(c)
Find the value of

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

Qeru said:
subbing in x=1/10 gives $s\left(\frac{1}{10}\right)=\frac{\frac{1}{10}}{1-\frac{1}{10}-\frac{1}{10^2}}=\frac{10}{89}$

And this substitution yields a valid result as the condition is satisfied ( $0.1 < \phi^{-1}$ ).

This is an excellent example of a really easy mark that can be sitting in a difficult question, which most student (at least) should be able to pick up. Just because you can't derive (a) doesn't mean you can't assume it and use it to do (b) and (c).

Qeru · Jan 28, 2021

CM_Tutor said:
Question 5

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

(a) Show that

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

Note: This result is only true if $\color{blue} |x|<\frac{1}{\phi}$ .

Qeru, I am really really really impressed with this answer. Recognising the way to use Binet's Formula and infinite series is beyond what most MX2 students can do. Seriously, I didn't expect that anyone would see this way to do the question. I was contemplating putting up a similar question on the Lucas numbers and providing the structure to get to the series interpretation and hence demonstrate the reason for the bounds, and you've jumped through the process backwards to get the forms of $s(x)$ . MX2 readers should be aware that the insight that Qeru has shown is not expected and the question was intended to approached in a different way. The advice on looking for clues in the form and structure of questions is excellent, too, and worth bearing in mind.

I'll let people ponder the answer that I was thinking of, but I will say that it starts with the given form of $s(x)$ and does not involved Binet's Formula.

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

In an exam, I would not accept an answer that amounts to

$\text{we are told that } s(x) =\frac{x}{1-x-x^2} \text{ is only true if } |x| < \frac{1}{\phi}. \\ \text{Since neither $x = 1$ nor $x = \frac{1}{\phi}$ satisfies this restriction then the result is invalid for these values.}$

What I would want was the "more intuitive" explanation that Qeru gave, something like:

$\begin{align*} \text{If $x = \frac{1}{\phi}$ then } s(x) &= \frac{x}{1-x-x^2} \\ &= \frac{\cfrac{1}{\phi}}{1-\cfrac{1}{\phi}-\left(\cfrac{1}{\phi}\right)^2} \quad \text{when $x=\frac{1}{\phi}$} \\ &= \frac{\phi}{\phi^2-\phi-1} \\ &= \frac{\phi}{0}, \text{which is undefined.} \\ \text{However, the series } s(x) &= \sum_{k=0}^\infty F_k x^k \\ &= F_0 + F_1 x + F_2 x^2 + ... \\ &= \frac{F_1}{\phi} + \frac{F_2}{\phi^2} + \frac{F_3}{\phi^3} + ... \text{ is defined for $x = \frac{1}{\phi}$} \\ \text{So, the result that } s(x) &= \frac{x}{1-x-x^2} \text{ is invalid in this case.} \end{align*}$

Similarly, the series form of $s(x)$ gives $s(1) = F_0 + F_1 + F_2 + ...$ , which is well-defined and positive (as every term is positive except for $F_0 = 0$ . However, the result requires

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

and so the result is not valid at $x=1$ .

However, I would award credit for an answer that uses the condition if that condition was independently proven in the answer given, which Qeru has (mostly) done. All that was missing was to note that there are two GPs and so the conditions require both $|x\phi| < 1$ and $|x\psi| < 1$ and since $|\psi|<|\phi|$ , it follows that the intersection of these inequalities (and hence the overall condition) is $|x| < \phi^{-1}$ .

Question 5(c)
Find the value of

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

And this substitution yields a valid result as the condition is satisfied ( $0.1 < \phi^{-1}$ ).

This is an excellent example of a really easy mark that can be sitting in a difficult question, which most student (at least) should be able to pick up. Just because you can't derive (a) doesn't mean you can't assume it and use it to do (b) and (c).

Not really a big fan of this method as we would have to prove the series is convergent first (which is much easier using the GP way).

$s(x)=F_1 x+F_2 x^2+F_3 x^3+F_4x^4+...$

$xs(x)=F_1 x^2+F_2 x^3+F_3 x^4+F_4x^5+...$ multiply both sides by x

$s(x)+xs(x)=F_1 x+(F_1+F_2) x^2+(F_2+F_3) x^3+(F_3+F_4)x^4...$ adding the two equations above

$s(x)+xs(x)=F_2 x+F_3 x^2+F_4 x^3+F_5x^4...$ Since $F_2=F_1$

$x(s(x)+xs(x))+F_1x=F_1x+F_2 x^2+F_3 x^3+F_4 x^4+F_5x^5...$ multiply both sides by x then add F_1x

$xs(x)+x^2s(x)+x=s(x)$

$s(x)(x+x^2-1)+x=0$

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

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

CM_Tutor · Jan 28, 2021

Qeru said:
Not really a big fan of this method as we would have to prove the series is convergent first (which is much easier using the GP way).

$s(x)=F_1 x+F_2 x^2+F_3 x^3+F_4x^4+...$

$xs(x)=F_1 x^2+F_2 x^3+F_3 x^4+F_4x^5+...$ multiply both sides by x

$s(x)+xs(x)=F_1 x+(F_1+F_2) x^2+(F_2+F_3) x^3+(F_3+F_4)x^4...$ adding the two equations above

$s(x)+xs(x)=F_2 x+F_3 x^2+F_4 x^3+F_5x^4...$ Since $F_2=F_1$

$x(s(x)+xs(x))+F_1x=F_1x+F_2 x^2+F_3 x^3+F_4 x^4+F_5x^5...$ multiply both sides by x then add F_1x

$xs(x)+x^2s(x)+x=s(x)$

$s(x)(x+x^2-1)+x=0$

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

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

Yes, though the notion of establishing the radius of convergence is beyond MX2 requirements except for GPs.

A faster approach would be to expand $(1-x-x^2)s(x)$ and show that you get $x$ .

Having said that, the approach Qeru uses above allows the result to be derived without actually knowing the result in advance.

idkkdi · Jan 29, 2021

CM_Tutor said:
Yes, though the notion of establishing the radius of convergence is beyond MX2 requirements except for GPs.

A faster approach would be to expand $(1-x-x^2)s(x)$ and show that you get $x$ .

Seriously are you going to write a textbook with qs? I would buy.

CM_Tutor · Jan 29, 2021

I want to preface this post with a reminder that @Qeru's first solution to the Fibonacci $s(x)$ question is exceptional. I commented that it was not the approach that I anticipated and Qeru gave an alternative approach, being the one I had been expecting, and I then said that:

CM_Tutor said:
A faster approach would be to expand $(1-x-x^2)s(x)$ and show that you get $x$ .

Having said that, the approach Qeru uses above allows the result to be derived without actually knowing the result in advance.

So, here is a structured question for the Lucas numbers that builds towards Qeru's first approach in a way that I think would be fair for an MX2 exam...

Question 8

The Lucas numbers are defined above as $L_0 = 2$ , $L_1 = 1$ , and $L_n = L_{n-1} + L_{n-2}$ for integers $n \geqslant 2$ . Let

$s(x) = \sum_{k=0}^n L_k x^k = L_0 + L_1 x + L_2 x^2 + ... + L_n x^n$

(a) By considering the series $s(x)$ and $xs(x)$ , express $s(x)$ in the form

$s(x) = \frac{f(x)}{g(x)}$

where $f(x)$ and $g(x)$ are polynomials and $g(x)$ has a higher degree than $f(x)$ .

If you can't get an answer, open the spoiler to see the $s(x)$ that you seek and then prove it is correct. That is, show that $g(x)\text{LHS} = g(x)\text{RHS}$ and then explain why it follows that LHS = RHS.

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

Only once you have got the closed form of $s(x)$ should you open the next spoiler for the rest of the question.

(b) Using the method of partial fractions, show that

$s(x) = \frac{1}{1-\phi x} + \frac{1}{1-\psi x}$

(c) Hence, using the formula for the limiting sum of a GP, find an expression for $L_n$ in terms of $\phi$ and $\psi$ .

(d) Find the condition that must be satisfied for the result you derived in part (a) to be a valid closed form for the original series $s(x)$ .

(e) Letting $k > \phi$ , find an expression for

$L_1+\frac{L_2}{k}+\frac{L_3}{k^2}+...$

(f) Hence, find the smallest positive integer $a$ for which

$L_1+\frac{L_2}{\psi+a}+\frac{L_3}{(\psi+a)^2}+...$

can be calculated and determine the sum in terms of $\phi$ .

(g) Find the set of all values $m>\phi^2$ where $m\in\mathbb{Q}$ but $\sqrt{m}\notin\mathbb{Q}$ such that

$L_1+\frac{L_2}{\sqrt{m}}+\frac{L_3}{m}+\frac{L_4}{m\sqrt{m}}+...$

is rational, or prove that no such values $m$ exist.

(h) Find

$\lim_{k\to\infty} \sum_{n=1}^{\infty}{\frac{L_n}{k^{n-1}}}$

CM_Tutor · Jan 29, 2021

Question 9

It was shown in question 6(f) that the Lucas and Fibonacci numbers are related by

$\phi^n = \frac{L_n+F_n\sqrt{5}}{2}=F_n\phi+F_{n-1}$

It was also proved that $\phi^n$ must be irrational for all integers $n\in\mathbb{Z}^+$ .

(a) Explain why $\phi^{-n}$ must be irrational for all non-zero integers $n$ .

(b) Suppose $M\in\mathbb{R}$ is a constant such $M+M^{-1}\in\mathbb{Z}$ . Without using mathematical induction, prove that $M^n+M^{-n}\in\mathbb{Z}$ .

(c) Hence, prove that $\phi^n+\phi^{-n}\in\mathbb{Q}$ for all even integers $n$ .

username_2 · Jan 29, 2021

lol. I feel like a dumb idiot even though im starting uni in a month.

CM_Tutor · Jan 29, 2021

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.

CM_Tutor · Jan 29, 2021

username_2 said:
lol. I feel like a dumb idiot even though im starting uni in a month.

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.

Qeru · Jan 29, 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) Assuming that the terms in $S_E$ are strictly increasing and those in $S_O$ are strictly decreasing, prove that both sequences approach the same limit and find it.

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

(a) As $n \to \infty$ implies $x^n \to 0$ and $x^{n+1} \to 0$ since both of absolute value less than 1. So $f(x) \to 1$

(b) $S_O=\frac{F_{2k}}{F_{2k-1}}=\frac{F_{2k-1}}{F_{2k-1}}+\frac{F_{2k-2}}{F_{2k-1}}=1+\frac{F_{2k-2}}{F_{2k-1}}$ where k is a positive integer. But since the fibonacci sequence is strictly increasing $\frac{F_{2k-2}}{F_{2k-1}}\leq1$ with equality at k=1.

Similarily: $S_E=\frac{F_{2k+1}}{F_{2k}}=1+\frac{F_{2k-1}}{F_{2k}}$ where k is a positive integer. Also $\frac{F_{2k-1}}{F_{2k}}<1$

So both sequences are bounded and finite.

(b) Aren't terms in S_E decreasing and S_O increasing (other way around), or am I misundestanding? i.e. $2>\frac{5}{3}>\frac{13}{8}...$ .

Now to find the limit we can use binet's formula:

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

Note that $|\phi|>1$ and $|\psi|<1$ So as $k \to \infty$ $S_O \to \frac{\phi^{2k}}{\phi^{2k-1}}=\phi$ . Exactly the same logic for $S_E$ to get $S_E \to\phi$

(d) Again I think it's the other way around?

2nd order recursion (2 Viewers)

Well-Known Member

Moderator

Moderator

Moderator

Moderator

Well-Known Member

Moderator

Moderator

Well-Known Member

Moderator

Moderator

Well-Known Member

Moderator

Well-Known Member

Moderator

Moderator

Active Member

Moderator

Moderator

Well-Known Member

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