Matemáticas discretas | Tipos de relaciones de recurrencia – Conjunto 2

Requisito previo: resolución de recurrencias , diferentes tipos de relaciones de recurrencia y sus soluciones , conjunto de prácticas para relaciones de recurrencia
La secuencia que se define al indicar una relación que conecta su término general an con un _{n -1} , un _n-2 , etc. se llama recurrencia relación de la sucesión.

Tipos de relaciones de recurrencia

• Relación de recurrencia de primer orden: una relación de recurrencia de la forma: a _n = ca _n-1 + f(n) para n>=1
  donde c es una constante y f(n) es una función conocida se llama relación de recurrencia lineal de primer orden con coeficiente constante. Si f(n) = 0, la relación es homogénea, de lo contrario no homogénea.

  Ejemplo:- x _n = 2x _n-1 – 1, a _n = na _n-1 + 1, etc.

  Pregunta: Resuelva la relación de recurrencia T(2 ^k ) = 3T(2 ^k-1 ) + 1, T(1) = 1.
  Sea T(2 ^k ) = a _k . Por lo tanto, a _k = 3a _k-1 + 1
  Multiplicando por x ^k y luego sumando,
  Σa _k x ^k = 3Σa _k-1 x ^k + Σx ^k ——> (1)
  Σa _k-1 x ^k = [a ₀ x + a ₁ x ² + ……]
  = x[a ₀ + a ₁ x + ……] = x[G(x)]
  (1) se convierte en
  G(x) – 3xG(x) – x/(1-x) = 0
  G(x)(1-3x) – x/(1-x) = 0
  G(x) = x/[(1-x) )(1-3x)] = A/(1-x) + B/(1-3x)
  –> A = -1/2 y B = 3/2
  G(x) = (3/2)Σ(3x ) ^k – (1/2)Σ(x) ^k
  El coeficiente de x ^k es, a _k = (3/2)3 ^k – (1/2)1 ^k
  Entonces, a _k = [3 ^k+1 – 1] /2.

• Relación de recurrencia homogénea lineal de segundo orden:- Una relación de recurrencia de la forma
  c _n a _n + c _n-1 a _n-1 + c _n-2 a _n-2 = 0 ——> (1)
  para n>=2 donde c _n , c _n-1 y c _n-2 son constantes reales con c _n != 0 se denomina relación de recurrencia homogénea lineal de segundo orden con coeficientes constantes.
  La solución a esto está en la forma a _n = ck ⁿ donde c, k!=0
  Poniendo esto en (1)
  c _n ck ⁿ + c _n-1 ck^n-1 + c _n-2 ck ^n-2 = 0
  c _n k ² + c _n-1 k + c _n-2 = 0 —–> (2)
  Así, a _n = ck ⁿ es solución de (1) si k satisface la ecuación cuadrática (2). Esta ecuación se llama ecuación característica para la relación (1).
  Ahora surgen tres casos,
  Caso 1: Si las dos raíces k ₁ , k ₂ de la ecuación son reales y distintas entonces, tomamos
  a _n = A(k ₁ ) ⁿ + B(k ₂ ) ⁿcomo solución general de (1) donde A y B son constantes reales arbitrarias.

  Caso 2: Si las dos raíces k ₁ , k ₂ de la ecuación son reales e iguales, con k como valor común entonces, tomamos
  a _n = (A + Bn)k ⁿ como solución general de (1) donde A y B son constantes reales arbitrarias.

  Caso 3: si las dos raíces k ₁ y k ₂ de la ecuación son complejas, entonces, k ₁ y k ₂ son complejos conjugados entre sí, es decir, k ₁ = p + iq y k ₂ = p – iq y tomamos
  un _n = r ⁿ (Acosnθ + Bsinnθ) como solución general de (1) donde A y B son constantes complejas arbitrarias, r = |k ₁ | = |k ₂ | = √ y θ = tan ^-1 (q/p).

Pregunta:- Resuelve la relación de recurrencia a _n + a _n-1 – 6a _n-2 = 0 para n>=2 dado que a ₀ = -1 y a ₁ = 8.
Aquí los coeficientes de a _n , a _n-1 y a _n-2 son c _n = 1, c _n-1 = 1 y c _n-2 = -6 respectivamente. Por lo tanto, la ecuación característica es
k ² + k – 6 o (k + 3)(k – 2) = 0 ——> (1)
Las raíces de (1) son k ₁ = -3 y k ₂ = 2 que son reales y distinto. Por lo tanto, la solución general es
a _n = A(-3) ⁿ+ B(2) ⁿ
donde A y B son constantes arbitrarias. De arriba obtenemos, a ₀ = A + B y a ₁ = -3A + 2B
A + B = -1
-3A + 2B = 8
Resolviendo estos obtenemos A = -2 y B = 1
Por lo tanto, a _n = -2 (-3) ^norte + (2) ^norte