2nd order recursion (1 Viewer)

tito981 · Dec 31, 2020

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 · Dec 31, 2020

tito981 said:
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?

Ice-Cream-Man · Dec 31, 2020

thought so as well

idkkdi said:
isnt recursion 3u?

tito981 · Jan 1, 2021

Ice-Cream-Man said:
thought so as well

idkkdi said:
isnt recursion 3u?

nah, not 2nd order recursive ones.

idkkdi · Jan 1, 2021

tito981 said:
nah, not 2nd order recursive ones.

are these in chapter 2?

tito981 · Jan 1, 2021

idkkdi said:
are these in chapter 2?

ye

idkkdi · Jan 1, 2021

tito981 said:
ye

where

tito981 · Jan 1, 2021

idkkdi said:
where

enrichment 2E, q22

CM_Tutor · Jan 8, 2021

Are you after examples of proving the formula for $u_n$ given a recursion relationship and initial conditions, or more challenging material that uses second order recursions?

tito981 · Jan 8, 2021

CM_Tutor said:
Are you after examples of proving the formula for $u_n$ 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 · Jan 9, 2021

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

CM_Tutor · Jan 9, 2021

Question 7
In question 2(a), you found that the the $\{F_n, n \in \mathbb{N}\} = \{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...\}$ , and thus established that $F_{10}=55$ .

In question 4(e), the formulae $F_{2n+1}={F_n}^2+{F_{n+1}}^2$ and $F_{2n}=F_n\left(F_{n+1}+F_{n-1}\right)$ were established.

(a) Using only the values in the Fibonacci sequence shown above and the formulae from question 4(e), establish that $F_{19}=4181$ .

(b) Using Binet's formula and the binomial theorem, and without using a calculator, establish the value of $F_{18}$ . 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

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

and use this result to confirm that $F_{11} = 89$ .

(d) Find the value of $F_{21}$ and use your result to find the value of $F_{20}$ . Check your results using the recurrence relation and your results from (a) and (b).

(e) Show that the prime factorisation of $F_{39} = 2 \times 233 \times 135721$ and find the prime factorisation of $F_{40}$ .

(f) Determine the percentage error in the estimate

$\frac{F_{80}}{F_{79}}\approx \phi$

(g) In question 6(c), a general calculating formula $F_{m+n}=F_{m-1}F_n+F_mF_{n+1}$ was proved. Use it to show that, in scientific notation,

$F_{119} = 3.311648... \times 10^k$

and determine the value of the integer $k$ .

idkkdi · Jan 18, 2021

CM_Tutor said:
Question 7
In question 2(a), you found that the the $\{F_n, n \in \mathbb{N}\} = \{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...\}$ , and thus established that $F_{10}=55$ .

In question 4(e), the formulae $F_{2n+1}={F_n}^2+{F_{n+1}}^2$ and $F_{2n}=F_n\left(F_{n+1}+F_{n-1}\right)$ were established.

(a) Using only the values in the Fibonacci sequence shown above and the formulae from question 4(e), establish that $F_{19}=4181$ .

(b) Using Binet's formula and the binomial theorem, and without using a calculator, establish the value of $F_{18}$ . 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

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

and use this result to confirm that $F_{11} = 89$ .

(d) Find the value of $F_{21}$ and use your result to find the value of $F_{20}$ . Check your results using the recurrence relation and your results from (a) and (b).

(e) Show that the prime factorisation of $F_{39} = 2 \times 233 \times 135721$ and find the prime factorisation of $F_{40}$ .

(f) Determine the percentage error in the estimate

$\frac{F_{80}}{F_{79}}\approx \phi$

(g) In question 6(c), a general calculating formula $F_{m+n}=F_{m-1}F_n+F_mF_{n+1}$ was proved. Use it to show that, in scientific notation,

$F_{119} = 3.311648... \times 10^k$

and determine the value of the integer $k$ .

u might as well just write and publish a question book lol.

Qeru · Jan 24, 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}^+$ .

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

(b)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$

(c) 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}$

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

(b) 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

(c) We use a similar method to (b) knowing that $F_{12}=144=12^2$ 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: $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$

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

4.

(a) 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

(b) 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}}$

(c) 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)$

(d) $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}}$

(e)
$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 rest coming soon......

Drdusk · Jan 24, 2021

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

(b)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$

(c) 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}$

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

(b) 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

(c) We use a similar method to (b) knowing that $F_{12}=144=12^2$ 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: $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$

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

4.

(a) 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

(b) 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}}$

(c) 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)$

(d) $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}}$

(e)
$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 rest coming soon......

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

Qeru · Jan 24, 2021

Drdusk said:
Nice job! You should attend the BOS trials this year because you seem to really like Maths.

We will see haha

idkkdi · Jan 24, 2021

Drdusk said:
Nice job! You should attend the BOS trials this year because you seem to really like Maths.

he's too scared of me to attend.

Qeru said:
We will see haha

Etho_x · Jan 24, 2021

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

(b)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$

(c) 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}$

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

(b) 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

(c) We use a similar method to (b) knowing that $F_{12}=144=12^2$ 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: $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$

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

4.

(a) 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

(b) 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}}$

(c) 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)$

(d) $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}}$

(e)
$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 rest coming soon......

Are you aiming for over a 99.95?

Etho_x · Jan 24, 2021

Drdusk said:
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 · 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

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

2nd order recursion (1 Viewer)

Well-Known Member

Well-Known Member

Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Moderator

Well-Known Member

Moderator

Moderator

Well-Known Member

Well-Known Member

Moderator

Well-Known Member

Well-Known Member

ツ

ツ

Well-Known Member

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