Cómo resolver la relación de recurrencia a continuación

Question

Cómo resolver la relación de recurrencia a continuación

Matemáticas
Matemáticas discretas
relaciones de recurrencia

ArithEgo

Resuelva las siguientes relaciones de recurrencia para $a_{0}=1$ y $b_{0}=2$ :

{\begin{cases} a_{norte} = 3 a_{norte - 1} + 2 b_{norte - 1} \\ b_{norte} = a_{norte - 1} + 2 b_{norte - 1} \end{cases}

$\left\{\begin{array}{l} a_{n} = 3a_{n-1} + 2b_{n-1} \\ b_{n} =a_{n-1} + 2b_{n-1} \end{array}\right.$

Traté de resolver esto sumándolos, pero no pude llegar a ninguna parte. Agradecería si alguien pudiera responder esto.

elsilverdoe

¿Conoces las matrices?

pavel r

Trate de sustituir

a_{n - 1} = b_{n} - 2 b_{n - 1}

$a_{n-1}=b_n-2b_{n-1}$ y

a_{n} = b_{n + 1} - 2 b_{n}

$a_n=b_{n+1}-2b_n$ en la primera relación.

ArithEgo

@TheSilverDoe en absoluto sí; en este tema creo que no.

dxiv

" Traté de resolver esto sumándolos, pero... "

-

$\;-\;$ Eso realmente puede funcionar, con algo de preparación. Escribe las relaciones como:

{\begin{cases} a_{norte} - a_{norte - 1} = 2 (a_{norte - 1} + b_{norte - 1}) \\ b_{norte} - b_{norte - 1} = a_{norte - 1} + b_{norte - 1} \end{cases}

$\left\{\begin{array}{l} a_{n} -a_{n-1}= 2 \left(a_{n-1} + b_{n-1}\right) \\ b_{n} -b_{n-1}=a_{n-1} + b_{n-1} \end{array}\right.$ Resulta que

a_{n} - a_{n - 1} = 2 (b_{n} - b_{n - 1})

$\,a_{n} -a_{n-1}= 2 \left(b_n - b_{n-1}\right)\,$ , luego resumiendo y telescopando

a_{n} - a_{0} = 2 (b_{n} - b_{0})

$\, a_n - a_0 = 2(b_n-b_0)\,$ . Ahora puedes sustituir

a_{n}

$\,a_n\,$ volver a cualquiera de las relaciones y obtener una recurrencia lineal para

b_{n}

$\,b_n\,$ solo.

Respuestas (3)

Cómo resolver la relación de recurrencia a continuación

Trate de sustituir $a_{n-1}=b_n-2b_{n-1}$ y $a_n=b_{n+1}-2b_n$ en la primera relación.
" Traté de resolver esto sumándolos, pero... " $\;-\;$ Eso realmente puede funcionar, con algo de preparación. Escribe las relaciones como: ${\begin{cases} a_{norte} - a_{norte - 1} = 2 (a_{norte - 1} + b_{norte - 1}) \\ b_{norte} - b_{norte - 1} = a_{norte - 1} + b_{norte - 1} \end{cases}$ $\left\{\begin{array}{l} a_{n} -a_{n-1}= 2 \left(a_{n-1} + b_{n-1}\right) \\ b_{n} -b_{n-1}=a_{n-1} + b_{n-1} \end{array}\right.$ Resulta que $\,a_{n} -a_{n-1}= 2 \left(b_n - b_{n-1}\right)\,$ , luego resumiendo y telescopando $\, a_n - a_0 = 2(b_n-b_0)\,$ . Ahora puedes sustituir $\,a_n\,$ volver a cualquiera de las relaciones y obtener una recurrencia lineal para $\,b_n\,$ solo.

Wang Ye Fei · Answer 1

Podemos comenzar reescribiendo el sistema de ecuaciones en forma matricial: $X_n=\begin{pmatrix} a_n \\ b_n \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 1 & 2 \end{pmatrix}\begin{pmatrix} a_{n-1} \\ b_{n-1}\end{pmatrix} = AX_{n-1}$ . A continuación, desea diagonalizar $A$ encontrando sus e-valores y e-vectores. Esto da: $\text{det}\begin{pmatrix} 3 - \lambda & 2 \\ 1 & 2 - \lambda \end{pmatrix}=0 \implies (3 - \lambda)(2 - \lambda) - 2 = 0\implies \lambda^2-5\lambda+4 = 0\implies \lambda = 1, 4$ . Para $\lambda = 1$ el e-vector correspondiente es $\begin{pmatrix} -1 \\ 1\end{pmatrix}$ , y con $\lambda = 4$ , el vector e correspondiente es $\begin{pmatrix} 2 \\ 1\end{pmatrix}$ . para que puedas escribir $A = P\cdot D\cdot P^{-1}= \begin{pmatrix} -1 & 2 \\ 1 & 1\end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 4\end{pmatrix}\begin{pmatrix} -1 & 2 \\ 1 & 1 \end{pmatrix}^{-1} = \begin{pmatrix} -1 & 2 \\ 1 & 1\end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 4\end{pmatrix}\begin{pmatrix} -\frac{1}{3} & \frac{2}{3} \\ \frac{1}{3} & \frac{1}{3}\end{pmatrix}\implies \begin{pmatrix} a_n \\ b_n \end{pmatrix} = X_n = A^nX_0 = P\cdot D^n\cdot P^{-1}X_0 = \begin{pmatrix} -1 & 2 \\ 1 & 1\end{pmatrix}\begin{pmatrix} 1 & 0 \\ 0 & 4^n \end{pmatrix}\begin{pmatrix} -\frac{1}{3} & \frac{2}{3} \\ \frac{1}{3} & \frac{1}{3}\end{pmatrix}\begin{pmatrix} 1 \\ 2\end{pmatrix}= \begin{pmatrix} -1+2\cdot 4^n \\ 1 + 4^n \end{pmatrix}\implies a_n = -1+2\cdot 4^n, b_n = 1+4^n.$

Will Jagy · Answer 2

Cayley Hamilton para la matriz de coeficientes dice

a_{norte + 2} = 5 a_{norte + 1} - 4 a_{norte},

$a_{n+2} = 5 a_{n+1} - 4 a_n \; , \;$

b_{norte + 2} = 5 b_{norte + 1} - 4 b_{norte},

$b_{n+2} = 5 b_{n+1} - 4 b_n \; , \;$

o

X_{norte + 2} - 5 X_{norte + 1} + 4 X_{norte} = 0,

$x_{n+2} - 5 x_{n+1} + 4 x_n = 0 \; , \;$ dónde

x_{n}

$x_n$ es cualquier secuencia.

Esto también se puede hacer jugando con las relaciones....

λ^{2} - 5 λ + 4

$\lambda^2 - 5 \lambda +4$ tiene raíces

1, 4.

$1,4.$

Entonces $a_n = C + D \; 4^n \; , \; \;$ y $b_n = F + G \; 4^n \; . \; \;$

elsilverdoe · Answer 3

Pista :

La relación de recurrencia se puede reescribir como

(\begin{matrix} a_{norte} \\ b_{norte} \end{matrix}) = (\begin{matrix} 3 & 2 \\ 1 & 2 \end{matrix}) (\begin{matrix} a_{norte - 1} \\ b_{norte - 1} \end{matrix})

$\begin{pmatrix} a_n \\ b_n \end{pmatrix}=\begin{pmatrix} 3 & 2 \\ 1 & 2 \end{pmatrix}\begin{pmatrix} a_{n-1} \\ b_{n-1} \end{pmatrix}$

que se puede resolver en

(\begin{matrix} a_{norte} \\ b_{norte} \end{matrix}) = {(\begin{matrix} 3 & 2 \\ 1 & 2 \end{matrix})}^{norte} (\begin{matrix} a_{1} \\ b_{1} \end{matrix})

$\begin{pmatrix} a_n \\ b_n \end{pmatrix}=\begin{pmatrix} 3 & 2 \\ 1 & 2 \end{pmatrix}^n\begin{pmatrix} a_{1} \\ b_{1} \end{pmatrix}$

Lamento no estar familiarizado con esto, pero ¿pueden ayudarme o darme una referencia de por qué se resuelve así?

Cómo resolver la relación de recurrencia a continuación

ArithEgo

elsilverdoe

pavel r

ArithEgo

dxiv

Respuestas (3)

Wang Ye Fei

Will Jagy

elsilverdoe

ArithEgo

Prueba de inducción de una relación de recurrencia?

Demostrar el número de adiciones del algoritmo del número de Fibonacci

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

Relación de recurrencia an+2=3an+1−2anan+2=3an+1−2ana_{n+2}=3a_{n+1}-2a_n

Conjuntos "gruesos" de enteros y números de Fibonacci

Encontrar una relación de recurrencia sobre un diccionario dado

Recurrencia lineal no homogénea de primer orden para la suma

Prueba combinatoria de x(n)=∑nk=1L(n,k)(x)kx(n)=∑k=1nL(n,k)(x)kx^{(n)} = \sum_{k = 1}^n L(n,k)(x)_k

Pasar de una función generadora racional a una relación de recurrencia

Pregunta sobre la técnica de Graham, Knuth y Patashnik para convertir recurrencias de primer orden en sumatorias