A solution “pulled out of a hat”. An explanation of the trick // Uma solução "tirada da cartola". Uma explicação do truque

 In the last issue of the Exercise Supplement of the Mathematics Gazette, most of the problems seemed trivial. Maybe this S:L 25. 411 is too, but look at the solution I found.

  "S:L25.411.  Consider the sequence  $(x_n)_{n\in\mathbb{N}}$, defined by  $x_{n+1}=\frac{4x_n+1}{2x_n+3}$, for any 

           $n\in\mathbb{N}$  and  $x_0=0$. Show that  $$\lim_{n \to \infty}x_n=1.$$

[Author] Ludovica LAZĂR, Năsăud"

ANSWER  CiP

$x_n=\frac{5^n-2^n}{5^n+2^{n+1}}=\frac{1-\left (\frac{2}{5}\right )^n}{1+2\cdot \left (\frac{2}{5}\right )^n}\;\underset{n \to \infty}{\to} \;1$

   

                           Solution CiP

               Let's consider the sequence

$y_n=\frac{x_n-1}{2\cdot x_n+1}. \tag{1}$

The reverse connection is

$x_n=\frac{1+y_n}{1-2\cdot y_n}. \tag{2}$

The initial conditions are

$x_0=0,\;\;\;y_0=-1. \tag{3}$

          Let's calculate now

$y_{n+1}\;\overset{(1)}{\underset{n\to n+1}{=}}\;\frac{x_{n+1}-1}{2\cdot x_{n+1}+1}\overset{def}{=}\frac{\frac{4x_n+1}{2x_n+3}-1}{2\cdot \frac{4x_n+1}{2x_n+3}+1}=\frac{4x_n+1-2x_n-3}{8x_n+2+2x_n+3}=\frac{2x_n-2}{10x_n+5}=\frac{2}{5}\cdot \frac{x_n-1}{2x_n+1}\overset{(1)}{=}\frac{2}{5}\cdot y_n.$

The equality of the extreme terms tells us that the sequence  $(y_n)_{n\in\mathbb{N}}$  is a geometric progression. So

$y_n=y_0\cdot \left (\frac{2}{5}\right )^n\overset{(3)}{=}-\left (\frac{2}{5}\right )^n,\;\;n\in\mathbb{N} \tag{4}$

          Substituting the value from  (4)  into  (2)  we obtain the formula for  $x_n$  mentioned in the Answer, as well as the value of the limit.

$\blacksquare$

........................................................................................................................................

               Recurrence relations of the form 

$x_{n+1}=\frac{a\cdot x_n+b}{c\cdot x_n+d}\;,\;\;a\cdot d-b\cdot c\neq 0 \tag{H}$

have an unquantified prevalence in Problem Collection books. 

In the book BĂTINEȚU D.M. "Şiruri..." (ALBATROS Publishing House, Bucharest, 1979 - click on the link to download) I came across problem 1.184, page 174-176, together with the solution. With the mention "Bacalaureat, France, 1975".

THAT'S WHERE I TAKEN THE IDEA OF SOLUTION

Luckily, the statement suggested the solution method. In translation

"1.184.  Consider the sequences  $(u_n)_{n\in \mathbb{N}},\;(v_n)_{n\in \mathbb{N}}$  where  $u_0=1$  and

$u_n=\frac{2\cdot u_{n-1}-1}{2\cdot u_{n-1}+5}\;,(\forall)n\in\mathbb{N}^*\;\;;\;\;v_n=\frac{2\cdot u_n+1}{u_n+1}\;,(\forall) n\in\mathbb{N}. \tag{5}$

  $a^{\circ}$)  Show that the sequence  $(v_n)_{n\in\mathbb{N}}$  is a geometric progression,

                         calculate its ratio and  $\lim_{n\to \infty}v_n$.

                                  $b^{\circ}$)  Express  $u_n$  in terms of  $n$  and establish its nature.

(Bacalaureat, Franța, 1975)"

       [The answers are :  $v_n=\frac{3}{2}\cdot \left (\frac{3}{4} \right )^n,\;u_n=\frac{1-v_n}{v_n-2}=\frac{2\cdot 4^n-3^{n+1}}{3^{n+1}-4^{n+1}}\underset{n\to \infty}{\to} -\frac{1}{2}$]

               Fortunately for Romanian-speaking readers, there is the book (I think I'm missing the electronic version) AVADANEI C., AVADANEI N., BORȘ C., CIUREA C.  "De la matematica elementară spre matematica superioară" (Ed. ACADEMIEI [R.S.] România, București, 1987)". Here, Chapter I is dedicated to a systematic study of sequences defined by homographic recurrence relations, pages 7 - 68.

See also here  !!

[In this book I found Problem 1.184 above, with the mention that it appeared under number 15 896 in GMB no. 9, 1978. Unfortunately the citation is erroneous, it is probably a number from 1976, I have not identified it exactly yet.]

Magic Trick (1) Explanation

For 

$x_{n+1}=\frac{4\cdot x_n+1}{2\cdot x_n+3} \tag{6}$

let's look for a transformation of type 

$y_n=\frac{a\cdot x_n+b}{c\cdot x_n+d} \tag{7}$

such that the latter is a geometric progression. 

A simple calculation gives us  $y_{n+1}\underset{(7)}{=}\frac{a\cdot x_{n+1}+b}{c\cdot x_{n+1}+d}\overset{(6)}{=}\frac{a\cdot \frac{4x_n+1}{2x_n+3}+b}{c\cdot \frac{4x_n+1}{2x_n+3}+d}=\frac{(4a+2b)\cdot x_n+a+3b}{(4c+2d)\cdot x_n+c+3d}.$

          Let's try to find two numbers  $\lambda\;and\;\mu$  such that the previous result is equal to  $\left (\frac{\lambda}{\mu}\right )\cdot y_n$.  We want to have the equality

$\frac{(4a+2b)x_n+a+3b}{(4c+2d)x_n+c+3d}=\frac{\lambda}{\mu}\cdot \frac{ax_n+b}{cx_n+d} \tag{8}$

Then, let's try, maybe we have a chance to succeed, to fulfill the equations

$(4a+2b)\cdot x_n+a+3b=\lambda \cdot (a\cdot x_n+b) \tag {9'}$

$(4c+2d)\cdot x_n+c+3d=\mu \cdot (c\cdot x_n+d) \tag {9"}$

Oh, and if we're not asking too much, it wouldn't hurt to have the equations

$\begin{cases}4a+2b=\lambda \cdot a\\\;a+3b=\lambda \cdot b\\4c+2d=\mu\cdot c\\\;c+3d=\mu\cdot d\end{cases} \tag{10}$

     Let's choose from (10) the first two equations :

$\begin{cases}(4-\lambda)\cdot a+\;\;\;\;\;\;\;\;\;\;\;2b=0\\\;\;\;\;\;\;\;\;\;\;\;\;\;a+(3-\lambda)\cdot b=0.\end{cases} \tag{11}$

For the system of equations with unknowns  $a\; and \;b$  to admit non-trivial solutions, it is necessary and sufficient that its matrix be singular, that is

$\left |\begin{matrix}4-\lambda&2\\1&3-\lambda\end{matrix}\right |=0 \tag{12}$

$\Leftrightarrow \lambda^2-7\cdot\lambda +10=0 \tag{13}$

Equation (13) has the roots  $\lambda_1=2,\;\;\lambda_2=5$. 

Choosing  $\lambda_1=5$ the system (11) is written  $\begin{cases}2\cdot a+2\cdot b=0\\a+b=0\end{cases}$  hence  $b=-a$.

          The last two equations in (10) lead to the same system (11) (of course with different notations), and we have the same equation (12)2. Now we choose  $\mu=5$  and we have the system  $\begin{cases}-c+2\cdot d=0\\c-2\cdot d=0\end{cases}$  hence  $c=2\cdot d$.

          So the possible transformations in (7) are  $y_{n+1}=\frac{a\cdot x_n-a}{2d\cdot x_n+d}=\frac{a}{d}\cdot \frac{x_n-1}{2\cdot x_n+1}$. With  $a=1,\;d=1$  we find what we chose in (1). 

                    REMARK  CiP

                   We see in  (H)  a homographic (or fractionally-linear) transformation

$x\mapsto \frac{a\cdot x+b}{c\cdot x+d},\;\;ad-bc \neq 0$

This can be represented by a matrix

$A=\left (\begin{matrix}a&b\\c&d\end{matrix}\right )$

The connection is not just a convention: there is a deep structural correspondence.

          These constitute Möbius transformation. They form a group, often noted  $\mathbb{PSL}(2)$.

            The composition of transformations corresponds to the multiplication of matrices.

             Since matrices obtained from a particular one and multiplied by an arbitrary nonzero scalar give us the same homographic transformation, it is natural that they act on a projective vector  $\textbf{x}=\left (\begin{matrix}x\\1\end{matrix} \right )$.

             It is also not difficult to see that  (12) is the characteristic equation associated with the matrix  $\left (\begin{matrix}4&2\\1&3\end{matrix}\right )$. Why it is not exactly the matrix associated with the transformation (6), i.e.  $\left( \begin{matrix}4&1\\2&3\end{matrix}\right)$  but its transpose, I leave to your discretion.