Matemáticas discretas - Relación de recurrencia

En este capítulo, discutiremos cómo las técnicas recursivas pueden derivar secuencias y usarse para resolver problemas de conteo. El procedimiento para encontrar los términos de una secuencia de manera recursiva se llamarecurrence relation. Estudiamos la teoría de las relaciones de recurrencia lineal y sus soluciones. Finalmente, presentamos funciones generadoras para resolver relaciones de recurrencia.

Definición

Una relación de recurrencia es una ecuación que define de forma recursiva una secuencia donde el siguiente término es una función de los términos anteriores (Expresando $ F_n $ como una combinación de $ F_i $ con $ i <n $).

Example - Serie de Fibonacci - $ F_n = F_ {n-1} + F_ {n-2} $, Torre de Hanoi - $ F_n = 2F_ {n-1} + 1 $

Relaciones de recurrencia lineal

Una ecuación de recurrencia lineal de grado k u orden k es una ecuación de recurrencia que tiene el formato $ x_n = A_1 x_ {n-1} + A_2 x_ {n-1} + A_3 x_ {n-1} + \ dots A_k x_ {nk} $ ($ A_n $ es una constante y $ A_k \ neq 0 $) en una secuencia de números como polinomio de primer grado.

Estos son algunos ejemplos de ecuaciones de recurrencia lineal:

Relaciones de recurrencia	Valores iniciales	Soluciones
F norte = F norte-1 + F norte-2	a 1 = a 2 = 1	Número de Fibonacci
F norte = F norte-1 + F norte-2	una 1 = 1, una 2 = 3	Número de Lucas
F norte = F norte-2 + F norte-3	una 1 = una 2 = una 3 = 1	Secuencia de Padovan
F n = 2F n-1 + F n-2	una 1 = 0, una 2 = 1	Número de Pell

Cómo resolver la relación de recurrencia lineal

Supongamos que una relación de recurrencia lineal ordenada es - $ F_n = AF_ {n-1} + BF_ {n-2} $ donde A y B son números reales.

La ecuación característica para la relación de recurrencia anterior es:

$$ x ^ 2 - Hacha - B = 0 $$

Pueden ocurrir tres casos al encontrar las raíces:

Case 1- Si esta ecuación se factoriza como $ (x- x_1) (x- x_1) = 0 $ y produce dos raíces reales distintas $ x_1 $ y $ x_2 $, entonces $ F_n = ax_1 ^ n + bx_2 ^ n $ es la solución. [Aquí, ayb son constantes]

Case 2 - Si esta ecuación se factoriza como $ (x- x_1) ^ 2 = 0 $ y produce una raíz real única $ x_1 $, entonces $ F_n = a x_1 ^ n + bn x_1 ^ n $ es la solución.

Case 3 - Si la ecuación produce dos raíces complejas distintas, $ x_1 $ y $ x_2 $ en forma polar $ x_1 = r \ angle \ theta $ y $ x_2 = r \ angle (- \ theta) $, entonces $ F_n = r ^ n (a cos (n \ theta) + b sin (n \ theta)) $ es la solución.

Problem 1

Resuelva la relación de recurrencia $ F_n = 5F_ {n-1} - 6F_ {n-2} $ donde $ F_0 = 1 $ y $ F_1 = 4 $

Solution

La ecuación característica de la relación de recurrencia es:

$$ x ^ 2 - 5x + 6 = 0, $$

Entonces, $ (x - 3) (x - 2) = 0 $

Por lo tanto, las raíces son:

$ x_1 = 3 $ y $ x_2 = 2 $

Las raíces son reales y distintas. Entonces, esto es en forma de caso 1

Por lo tanto, la solución es:

$$ F_n = ax_1 ^ n + bx_2 ^ n $$

Aquí, $ F_n = a3 ^ n + b2 ^ n \ (Como \ x_1 = 3 \ y \ x_2 = 2) $

Por lo tanto,

$ 1 = F_0 = a3 ^ 0 + b2 ^ 0 = a + b $

$ 4 = F_1 = a3 ^ 1 + b2 ^ 1 = 3a + 2b $

Resolviendo estas dos ecuaciones, obtenemos $ a = 2 $ y $ b = -1 $

Por lo tanto, la solución final es:

$$ F_n = 2,3 ^ n + (-1). 2 ^ n = 2,3 ^ n - 2 ^ n $$

Problem 2

Resuelva la relación de recurrencia - $ F_n = 10F_ {n-1} - 25F_ {n-2} $ donde $ F_0 = 3 $ y $ F_1 = 17 $

Solution

La ecuación característica de la relación de recurrencia es:

$$ x ^ 2 - 10x -25 = 0 $$

Entonces $ (x - 5) ^ 2 = 0 $

Por lo tanto, hay una única raíz real $ x_1 = 5 $

Como hay una única raíz de valor real, esto tiene la forma del caso 2

Por lo tanto, la solución es:

$ F_n = ax_1 ^ n + bnx_1 ^ n $

$ 3 = F_0 = a.5 ^ 0 + (b) (0.5) ^ 0 = a $

$ 17 = F_1 = a.5 ^ 1 + b.1.5 ^ 1 = 5a + 5b $

Resolviendo estas dos ecuaciones, obtenemos $ a = 3 $ y $ b = 2/5 $

Por lo tanto, la solución final es - $ F_n = 3.5 ^ n + (2/5) .n.2 ^ n $

Problem 3

Resuelva la relación de recurrencia $ F_n = 2F_ {n-1} - 2F_ {n-2} $ donde $ F_0 = 1 $ y $ F_1 = 3 $

Solution

La ecuación característica de la relación de recurrencia es:

$$ x ^ 2 -2x -2 = 0 $$

Por lo tanto, las raíces son:

$ x_1 = 1 + i $ y $ x_2 = 1 - i $

En forma polar,

$ x_1 = r \ angle \ theta $ y $ x_2 = r \ angle (- \ theta), $ donde $ r = \ sqrt 2 $ y $ \ theta = \ frac {\ pi} {4} $

Las raíces son imaginarias. Entonces, esto tiene la forma del caso 3.

Por lo tanto, la solución es:

$ F_n = (\ sqrt 2) ^ n (a cos (n. \ Sqcap / 4) + b sin (n. \ Sqcap / 4)) $

$ 1 = F_0 = (\ sqrt 2) ^ 0 (a cos (0. \ Sqcap / 4) + b sin (0. \ Sqcap / 4)) = a $

$ 3 = F_1 = (\ sqrt 2) ^ 1 (a cos (1. \ Sqcap / 4) + b sin (1. \ Sqcap / 4)) = \ sqrt 2 (a / \ sqrt 2 + b / \ sqrt 2 PS

Resolviendo estas dos ecuaciones obtenemos $ a = 1 $ y $ b = 2 $

Por lo tanto, la solución final es:

$ F_n = (\ sqrt 2) ^ n (cos (n. \ Pi / 4) + 2 sin (n. \ Pi / 4)) $

Relación de recurrencia no homogénea y soluciones particulares

Una relación de recurrencia se llama no homogénea si tiene la forma

$ F_n = AF_ {n-1} + BF_ {n-2} + f (n) $ donde $ f (n) \ ne 0 $

Su relación de recurrencia homogénea asociada es $ F_n = AF_ {n – 1} + BF_ {n-2} $

La solución $ (a_n) $ de una relación de recurrencia no homogénea tiene dos partes.

La primera parte es la solución $ (a_h) $ de la relación de recurrencia homogénea asociada y la segunda parte es la solución particular $ (a_t) $.

$$ a_n = a_h + a_t $$

La solución a la primera parte se realiza mediante los procedimientos descritos en la sección anterior.

Para encontrar la solución particular, encontramos una solución de prueba adecuada.

Sea $ f (n) = cx ^ n $; sea ​​$ x ^ 2 = Ax + B $ la ecuación característica de la relación de recurrencia homogénea asociada y sean $ x_1 $ y $ x_2 $ sus raíces.

• Si $ x \ ne x_1 $ y $ x \ ne x_2 $, entonces $ a_t = Ax ^ n $

• Si $ x = x_1 $, $ x \ ne x_2 $, entonces $ a_t = Anx ^ n $

• Si $ x = x_1 = x_2 $, entonces $ a_t = An ^ 2x ^ n $

Ejemplo

Sea una relación de recurrencia no homogénea $ F_n = AF_ {n – 1} + BF_ {n-2} + f (n) $ con raíces características $ x_1 = 2 $ y $ x_2 = 5 $. Las soluciones de prueba para diferentes valores posibles de $ f (n) $ son las siguientes:

f (n)	Soluciones de prueba
4	UN
5,2 n	An2 n
8,5 n	An5 n
4 n	A4 n
2n 2 + 3n + 1	Un 2 + Bn + C

Problem

Resuelva la relación de recurrencia $ F_n = 3F_ {n-1} + 10F_ {n-2} + 7.5 ^ n $ donde $ F_0 = 4 $ y $ F_1 = 3 $

Solution

Esta es una relación lineal no homogénea, donde la ecuación homogénea asociada es $ F_n = 3F_ {n-1} + 10F_ {n-2} $ y $ f (n) = 7.5 ^ n $

La ecuación característica de su relación homogénea asociada es:

$$ x ^ 2 - 3x -10 = 0 $$

O $ (x - 5) (x + 2) = 0 $

O $ x_1 = 5 $ y $ x_2 = -2 $

Por tanto, $ a_h = a.5 ^ n + b. (- 2) ^ n $, donde ayb son constantes.

Como $ f (n) = 7.5 ^ n $, es decir, de la forma $ cx ^ n $, una solución de prueba razonable de at será $ Anx ^ n $

$ a_t = Anx ^ n = An5 ^ n $

Después de poner la solución en la relación de recurrencia, obtenemos:

$ An5 ^ n = 3A (n - 1) 5 ^ {n-1} + 10A (n - 2) 5 ^ {n-2} + 7.5 ^ n $

Dividiendo ambos lados por $ 5 ^ {n-2} $, obtenemos

$ An5 ^ 2 = 3A (n - 1) 5 + 10A (n - 2) 5 ^ 0 + 7.5 ^ 2 $

O $ 25An = 15An - 15A + 10An - 20A + 175 $

O $ 35A = 175 $

O $ A = 5 $

Entonces, $ F_n = An5 ^ n = 5n5 ^ n = n5 ^ {n + 1} $

La solución de la relación de recurrencia se puede escribir como:

$ F_n = a_h + a_t $

$ = a.5 ^ n + b. (- 2) ^ n + n5 ^ {n + 1} $

Poniendo valores de $ F_0 = 4 $ y $ F_1 = 3 $, en la ecuación anterior, obtenemos $ a = -2 $ y $ b = 6 $

Por lo tanto, la solución es:

$ F_n = n5 ^ {n + 1} + 6. (- 2) ^ n -2.5 ^ n $

Funciones de generación

Generating Functions representa secuencias donde cada término de una secuencia se expresa como un coeficiente de una variable x en una serie de potencias formales.

Matemáticamente, para una secuencia infinita, digamos $ a_0, a_1, a_2, \ dots, a_k, \ dots, $ la función generadora será -

$$ G_x = a_0 + a_1x + a_2x ^ 2 + \ dots + a_kx ^ k + \ dots = \ sum_ {k = 0} ^ {\ infty} a_kx ^ k $$

Algunas áreas de aplicación

Las funciones de generación se pueden utilizar para los siguientes propósitos:

• Para resolver una variedad de problemas de conteo. Por ejemplo, la cantidad de formas de realizar cambios para una Rs. Billete de 100 con los billetes de denominaciones Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 y Rs.50

• Para resolver relaciones de recurrencia

• Por probar algunas de las identidades combinatorias

• Para encontrar fórmulas asintóticas para términos de sucesiones

Problem 1

¿Cuáles son las funciones generadoras para las secuencias $ \ lbrace {a_k} \ rbrace $ con $ a_k = 2 $ y $ a_k = 3k $?

Solution

Cuando $ a_k = 2 $, función generadora, $ G (x) = \ sum_ {k = 0} ^ {\ infty} 2x ^ {k} = 2 + 2x + 2x ^ {2} + 2x ^ {3} + \ dots $

Cuando $ a_ {k} = 3k, G (x) = \ sum_ {k = 0} ^ {\ infty} 3kx ^ {k} = 0 + 3x + 6x ^ {2} + 9x ^ {3} + \ dots \ dots $

Problem 2

Cuál es la función generadora de la serie infinita; $ 1, 1, 1, 1, \ dots $?

Solution

Aquí, $ a_k = 1 $, por $ 0 \ le k \ le \ infty $

Por lo tanto, $ G (x) = 1 + x + x ^ {2} + x ^ {3} + \ dots \ dots = \ frac {1} {(1 - x)} $

Algunas funciones generadoras útiles

• Para $ a_k = a ^ {k}, G (x) = \ sum_ {k = 0} ^ {\ infty} a ^ {k} x ^ {k} = 1 + ax + a ^ {2} x ^ { 2} + \ puntos \ puntos \ puntos = 1 / (1 - ax) $

• Para $ a_ {k} = (k + 1), G (x) = \ sum_ {k = 0} ^ {\ infty} (k + 1) x ^ {k} = 1 + 2x + 3x ^ {2} \ puntos \ puntos \ puntos = \ frac {1} {(1 - x) ^ {2}} $

• Para $ a_ {k} = c_ {k} ^ {n}, G (x) = \ sum_ {k = 0} ^ {\ infty} c_ {k} ^ {n} x ^ {k} = 1 + c_ {1} ^ {n} x + c_ {2} ^ {n} x ^ {2} + \ puntos \ puntos \ puntos + x ^ {2} = (1 + x) ^ {n} $

• Para $ a_ {k} = \ frac {1} {k!}, G (x) = \ sum_ {k = 0} ^ {\ infty} \ frac {x ^ {k}} {k!} = 1 + x + \ frac {x ^ {2}} {2!} + \ frac {x ^ {3}} {3!} \ dots \ dots \ dots = e ^ {x} $