Bilinear Recursion - 2

Define sequence of vectors $\mathbf{r}_n$ by the formulae $\mathbf{r}_{n+1} \; = \; A\mathbf{r}_n \; = \; \left(\begin{array}{cc} 6 & 35 \\ 4 & 10 \end{array}\right)\mathbf{r}_n \hspace{1cm} n \ge 0 \hspace{2cm} \mathbf{r}_0 \; = \; \binom{10}{1}$ Now the matrix $A$ has eigensystem $A\binom{5}{2} \; = \; 20\binom{5}{2} \hspace{2cm} A\binom{7}{-2} \; = \; -4\binom{7}{-2}$ Since $\binom{10}{1} \; = \; \frac18\left[9\binom{5}{2} + 5\binom{7}{-2}\right]$ we deduce that $\mathbf{r}_n \; = \; \frac18\left[9\binom{5}{2}20^n + 5\binom{7}{-2}(-4)^n\right] \hspace{2cm} n \ge 0$ and $x_n$ is then the ratio of the first and second coefficients of $\mathbf{r}_n$ , so that $x_n \; = \; \frac{45 \times 20^n + 35 \times (-4)^n}{18 \times 20^n - 10 \times (-4)^n} \; = \; \frac{45(-5)^n + 35}{18(-5)^n - 10} \hspace{2cm} n \ge 0$ so that $a + b + c + d + |\lambda| = 45 + 35 +18 + 10 + |-5| = \boxed{113}$ .

If we just want to find the values of $a$ , $b$ , $c$ , $d$ , and $\lambda$ , without deriving them, we can use the actual values of $x_n$ and solve the simultaneous equations.

From $\displaystyle x_n = \frac {a+b\lambda^n}{c\lambda^n - d} \implies \lim_{n \to \infty} x_n = \lim_{n \to \infty} \frac {a+b\lambda^n}{c\lambda^n - d} = \lim_{n \to \infty} \frac {\frac a{\lambda^n}+b}{c - \frac d{\lambda^n}} = \frac bc$ for $|\lambda| > 1$ . This implies that $x_n$ converges and let its limit be $L$ . Then

$\begin{aligned} x_{n+1} & = \frac {6x_n+35}{4x_n+10} & \small \blue{\text{when }n \to \infty} \\ \implies L & = \frac {6L+35}{4L+10} \\ 4L^2 + 10L & = 6L + 35 \\ 4L^2 + 4L - 35 & = 0 \\ (2L - 5)(2L + 7) & = 0 & \small \blue{\text{Since }x_n > 0\ \forall n \ge 0 \implies L > 0} \\ \implies L & = \frac 52 \\ \frac bc & = \frac 52 \implies c = \frac 25 b \end{aligned}$

Now we have:

$\begin{cases} x_0 = 10 = \dfrac {a+b}{c-d} & \implies a + b = 10c - 10 d & ...(1) \\ x_1 = \dfrac {19}{10} = \dfrac {a+b\lambda}{c\lambda-d} & \implies 10a + 10b\lambda = 19c\lambda - 19 d & ...(2) \\ x_2 = \dfrac {29}{11} = \dfrac {a+b\lambda^2}{c\lambda^2-d} & \implies 11a + 11b\lambda^2 = 29c\lambda^2 - 29 d & ...(3) \end{cases}$

$\begin{cases} (2) - 10(1): & 10b(\lambda - 1) = c(19\lambda - 100) + 81d & ...(4) \\ (3) - 11(1): & 11b(\lambda^2 - 1) = c(29\lambda^2 - 110) + 81d & ...(5) \end{cases}$

$\begin{aligned} \implies (5)-(4): \quad b(11\lambda^2 - 10 \lambda -1) & = c(29\lambda^2 - 19\lambda - 10) & \small \blue{\text{Since }c = \frac 25 b} \\ 55 \lambda^2 - 50 \lambda - 5 & = 58 \lambda^2 - 38 \lambda - 20 \\ 3 \lambda^2 + 12 \lambda - 15 & = 0 \\ \lambda^2 + 4 \lambda - 5 & = 0 \\ (\lambda + 5)(\lambda - 1) & = 0 & \small \blue{\text{Since }\lambda < 0} \\ \implies \lambda & = - 5 \end{aligned}$

From $(4): \quad -60 b = \dfrac 25 b (-195) + 81 d \implies d = \dfrac 29 b$ . From $(1): \quad a + b = 4 b - \dfrac {20}9 \implies a = \dfrac 79 b$ . Then we have:

$x_n = \frac {\frac 79 + \lambda^n}{\frac 25\lambda^n - \frac 29} = \frac {35+45\lambda^n}{18\lambda^n - 10}$

Therefore $a+b+c+d+|\lambda| = 35+45+18+10+5 = \boxed{113}$ .

Let's consider the general bilinear recursion,

$x_{n+1} = \dfrac{a x_n + b} { c x_n + d }$

Pulling the $a$ and $c$ out, this becomes,

$x_{n+1} = \dfrac{a}{c} \dfrac{( x_n + (b/a) ) } {( x_n + (d/c)) }$

which, after dividing the numerator by the denominator, becomes,

$x_{n+1} = \dfrac{a}{c} ( 1 + \dfrac{(b/a - d/c)} { x_n + (d/c) } )$

Adding $(d/c)$ to both sides,

$x_{n+1} + (d/c) = \dfrac{a + d}{c} + \dfrac{a}{c} \dfrac{(b/a - d/c)}{ x_n +(d/c) }$

Let $y_n = x_n + (d/c)$ , then

$y_{n+1} = \dfrac{a + d}{c} + \dfrac{a}{c} \dfrac{ (b/a - d/c) } { y_n }$

Now we'll make the magic substitution (Source: Introduction to Difference Equations, by Samuel Goldberg, 1958), for this problem, namely, we'll let $y_n = \dfrac{z_{n+1} }{z_n}$ then, we have,

$\dfrac{z_{n+2}}{z_{n+1}} = \dfrac{a + d}{c} + \dfrac{a}{c} (b/a - d/c) \dfrac{ z_n }{z_{n+1}}$

multiply through by $z_{n+1}$ , to get,

$z_{n+2} = \dfrac{a + d}{c} z_{n+1} + \dfrac{a}{c} (b/a - d/c) z_n$

which is a standard second order linear difference equation, whose solution is readily available.

Let's substitute the given parameters of the original recursive equation, then,

$z_{n+2} = \dfrac{6 + 10}{4} z_{n+1} + \dfrac{6}{4} (35/6 - 10/4) z_n$

which after simplifying becomes,

$z_{n+2} = 4 z_{n+1} + 5 z_n$

or

$z_{n+2} - 4 z_{n+1} - 5 z_n = 0$

The characteristic equation of this difference equation is,

$m^2 - 4 m - 5 = 0$

and this factors into $(m - 5)(m + 1) = 0$ . Thus, the solution of the difference equation is of the form,

$z_n = A (-1)^n + B (5)^n$

Since $x_0 = 10$ , then $y_0 = 10 + \dfrac{5}{2} = \dfrac{25}{2}$ , therefore, we can choose $z_0 = 1$ , then it follows that $z_1 = \dfrac{25}{2}$

Now, we can construct two linear equations in the unknown coefficients $A$ and $B$ , namely,

$1 = A + B$ , and

$\dfrac{25}{2} = - A + 5 B$

Adding, gives us, $6 B = \dfrac{27}{2}$ , so that $B = \dfrac{27}{12}$ , and therefore, $A = 1 - \dfrac{27}{12} = -\dfrac{5}{4}$

Hence, $z_n = -\dfrac{5}{4} (-1)^n + \dfrac{27}{12} (5)^n$ , and it follows that $y_n$ is given by,

$y_n = \dfrac{ - 15 (-1)^{n+1} + 27 (5)^{n+1} }{ - 15 (-1)^n + 27 (5)^n } = \dfrac{ 15 (-1)^n + 135 (5)^n }{ - 15 (-1)^n + 27 (5)^n } = \dfrac{ 5 + 45 (-5)^n}{ -5 + 9 (-5)^n }$

Therefore,

$x_n = y_n - \dfrac{5}{2} = \dfrac{ 10 + 90 (-5)^n + 25 - 45 (-5)^n }{ -10 + 18 (-5)^n } = \dfrac{ 35 + 45 (-5)^n }{18 (-5)^n - 10 }$

which is in the form specified by the problem, hence $\lambda = -5$ and $a, b, c, d = 35, 45, 18, 10$ .

Therefore, the answer is $35 + 45 + 18 + 10 + 5 = \boxed{113}$