Sequences and Roots!

Rearranging the given recursive formula:

$\displaystyle a_k=r_ka_{k-1} + \frac{1}{\prod_{j=k}^nr_j}$

In general:

$\displaystyle a_k=B_ka_{k-1} + M_k$

$\displaystyle = B_kB_{k-1}a_{k-2} + M_{k-1}B_k +M_k$

$\displaystyle = B_kB_{k-1}B_{k-2}a_{k-3} + M_{k-2}B_kB_{k-1} + M_{k-1}B_k +M_k$

$= \dots$

Recognizing the pattern, we will Propose then show by induction (at the end of the solution) that:

$\displaystyle a_k = \Bigg(\prod_{p=1}^k B_p \Bigg) \Bigg( a_0 +\sum_{i=1}^k \frac{M_i}{\prod_{t=1}^i B_t} \Bigg)$

Substitute: $a_0=1 , B_k = r_k$ and $M_k = \frac{1}{\prod_{j=k}^nr_j}$ :

$\displaystyle a_k = \Bigg(\prod_{p=1}^k (r_p) \Bigg) \Bigg( 1 +\sum_{i=1}^k \frac{\frac{1}{\prod_{j=i}^nr_j}}{\prod_{t=1}^i (r_t)} \Bigg)$

$\displaystyle = \Bigg(\prod_{p=1}^k r_p \Bigg) \Bigg( 1 +\sum_{i=1}^k \frac{1}{r_i\prod_{j=1}^n r_j} \Bigg)$

Let $k=n$ :

$\displaystyle a_n= \Bigg(\prod_{p=1}^n r_p \Bigg) \Bigg( 1 +\sum_{i=1}^n \frac{1}{r_i\prod_{j=1}^n r_j} \Bigg)$

Note that $\{r_1,r_2,\dots,r_n \}$ are the roots of $P(x) = \sum_{m=0}^n F_mx^m$ . Hence by Vieta's formula :

$\displaystyle \prod_{j=1}^n r_j = (-1)^n\frac{F_0}{F_n} = - \frac{1}{F_n} \;\;\;\; ( n \textrm{ is odd})$

$\displaystyle => a_n = -\frac{1-F_n \sum_{i=1}^n \frac{1}{r_i} }{F_n}$

Now working on the sum :

$\displaystyle \sum_{i=1}^n \frac{1}{r_i}$

$\displaystyle = \frac{\sum_{i=1}^n \frac{\prod_{j=1}^n r_j}{r_i}}{\prod_{j=1}^n r_j}$

$\displaystyle = \frac{\sum_{cyc} r_1r_2\dots r_{n-1} }{\prod_{j=1}^n r_j}$

Using Vieta again :

$\displaystyle \sum_{cyc} r_1r_2\dots r_{n-1} = (-1)^{n-1}\frac{F_1}{F_n} = \frac{1}{F_n}$

$\displaystyle => \sum_{i=1}^n \frac{1}{r_i} = \frac{\frac{1}{F_n} }{-\frac{1}{F_n} } = -1$

Substitute back in $a_n$ :

$\displaystyle \boxed{ a_n = -\frac{1+F_n}{F_n} }$

Now perform the recommended limit:

$\displaystyle \lim_{n\to \infty} (a_n+1)F_{n+1}$

$\displaystyle = - \lim_{n\to \infty} \frac{F_{n+1}}{F_n}$

$\displaystyle =\boxed{ -\phi}$

Where $\phi$ is the Golden Ratio .(The limit is proved below)

$....................................$

$$

$\bullet \mathbf{ \;The \; Induction \; proof \; :}$

For $a_k=B_ka_{k-1} + M_k$ , we have:

$\displaystyle a_k= \Bigg(\prod_{p=1}^k B_p \Bigg) \Bigg( a_0 +\sum_{i=1}^k \frac{M_i}{\prod_{t=1}^i B_t} \Bigg)$

$\ast$ Test for $k=1$ :

$\displaystyle a_1= \Bigg(\prod_{p=1}^1 B_p \Bigg) \Bigg( a_0 +\sum_{i=1}^1 \frac{M_i}{\prod_{t=1}^i B_t} \Bigg)$

$\displaystyle a_1 =( B_1 )( a_0 +\frac{M_1}{B_1} )= B_1a_0 + M_1$

Which is true by setting $k=1$ in the recursive formula.

$\ast$ Suppose that it is true for $k$ , Test for $k+1$ :

$\displaystyle a_{k+1} = \Bigg(\prod_{p=1}^{k+1} B_p \Bigg) \Bigg( a_0 +\sum_{i=1}^{k+1} \frac{M_i}{\prod_{t=1}^i B_t} \Bigg)$

$\displaystyle = B_{k+1} \Bigg(\prod_{p=1}^k B_p \Bigg) \Bigg( a_0 + \sum_{i=1}^k \frac{M_i}{\prod_{t=1}^i B_t} +\frac{M_{k+1}}{\prod_{t=1}^{k+1} B_t} \Bigg)$

$\displaystyle = B_{k+1} \Bigg(\prod_{p=1}^k B_p \Bigg) \Bigg( a_0 + \sum_{i=1}^k \frac{M_i}{\prod_{t=1}^i B_t} \Bigg) + M_{k+1}$

$\displaystyle = B_{k+1}a_k + M_{k+1}$

Which is true by the recursive formula, Therefore our preposition is validated.

$$

$$

$\bullet \mathbf{ \; Proof \; of \; The \; Limit \; : }$

$\displaystyle L= \lim_{n\to \infty} \frac{F_{n+1}}{F_n}$

Use the recursive formula of the Fibonacci sequence:

$\displaystyle F_{n+1} = F_{n} +F_{n-1}$

$\displaystyle => L = \lim_{n\to \infty} \frac{F_{n} +F_{n-1}}{F_n} = 1+ \frac{1}{ \lim_{n\to \infty} \frac{F_n}{F_{n-1}} } = 1+\frac{1}{L}$

Solving for $L$ yields the Golden Ratio .