Relación de recurrencia

Question

¿Cómo resuelves la siguiente relación de recurrencia?

ps

dónde

ps

Sé que la respuesta es$$x_{n} = \frac{x_{n-1}}{1 + x_{n-1}}$ $

Lo resolví por inducción. Pero no me gusta tanto ya que siempre siento que estoy haciendo trampa cuando resuelvo por inducción. Supongo que ya sé la respuesta.

¿Hay una mejor manera?

Gracias

Answer 1

Usando las sugerencias en los comentarios, dejamos$y_n = 1/x_n$ para que$y_0 = 1/1 = 1$ y: $$ \ frac {1} {y_n} = \ frac {\ frac {1} {y_ {n-1}} } {1 + \ frac {1} {y_ {n-1}}} = \ frac {1} {y_ {n-1} + 1} $$ Pero tomando reciprocals de ambos lados, obtenemos un lineal de fácil resolución relación de recurrencia: \begin{align*} y_n &= y_{n-1} + 1 \\ &= (y_{n-2} + 1) + 1 = y_{n-2} + 2 \\ &= (y_{n-3} + 1) + 2 = y_{n-3} + 3 \\ &= \cdots \\ &= y_0 + n = 1 + n &\text{using implicit induction} \end {align *} Por lo tanto, concluimos que$x_n = \frac{1}{1 + n}$.

Answer 2

Este es un Ricatti recurrencia, de la forma:

$\begin{align} x_{n + 1} = \frac{a x_n + b}{c x_n + d} \end{align}$

con $c \ne 0$$a d - b c \ne 0$.

Es una de las pocas recurrencias lineales con solución exacta. Sé de las tres técnicas.

Primero es debido a la Marca de "Una Secuencia Definida por una Ecuación en las diferencias", AMM 62(7), pp 489-492 (1955). Sustituyendo $y_n = c x_n + d$ da una ecuación de la forma:

$\begin{align} y_{n + 1} = \alpha + \frac{\beta}{y_n} \end{align}$

con $y_n = \frac{w_{n + 1}}{w_n}$ consigue el segundo fin de recurence:

$\begin{align} w_{n + 2} - \alpha w_{n + 1} + \beta w_n = 0 \end{align}$

La solución de este (puede arreglar $w_0, w_1$ arbitrariamente para obtener el da $x_0$), y la sustitución de espalda le da la solución.

Otra técnica es debido a Mitchell, "Una Analítica Riccati Solución para Dos Meta en Tiempo Discreto de Control", Revista de la Dinámica Económica y de Control de 24(4), pp 615-622 (2000), Definen el auxiliar de la secuencia:

$\begin{align} y_n = \frac{1}{1 + \eta x_n} \end{align}$

Escribir la recurrencia en términos de $y_n$ para obtener:

$\begin{align} y_{n + 1} = \frac{(d \eta - c) y_n + c} {(b \eta^2 - (a - d) \eta - c) y_n + a \eta + c} \end{align}$

Seleccione $\eta$ así que esta es una recurrencia lineal de primer orden, es decir, $b \eta^2 - (a - d) \eta - c = 0$ Ambos ceros va a hacer.

La tercera idea es tener en cuenta que la función de dar a $x_{n + 1}$ es una transformación de Möbius, y aquellos que forman parte de un grupo. En particular, si:

$\begin{align} \mathbf{A} = \pmatrix{a & b \\ c & d} \end{align}$

la composición de las transformaciones descritas por $\mathbf{A}$ $\mathbf{B}$ es descrito por $\mathbf{A} \cdot \mathbf{B}$. I. e., usted tiene que $x_n$ es la aplicación de $\mathbf{A}^n$$x_0$. Diagonalize $\mathbf{A}$, y el poder es trivial calcular.