Relación de recurrencia

Una relación de recurrencia para una secuencia es una fórmula para el siguiente término de la secuencia en función de los términos anteriores. Un ejemplo famoso del que quizá hayas oído hablar es la relación de recurrencia de la sucesión de Fibonacci, en la que cada término es la suma de los dos términos anteriores. Aquí tienes los primeros términos de la sucesión de Fibonacci: \(0,1,1,2,3,5,8,\dots\)

Pruéablo tú mismo Regístrate gratis
Tarjetas de estudio
Índice de temas

    El significado de las relaciones de recurrencia

    Las relaciones de recurrencia dan una fórmula para la regla común que rige una determinada secuencia de números. Son recursivas, lo que significa que la fórmula de la relación de recurrencia para el siguiente término de la secuencia se da en función de sus términos anteriores. Nos permiten simplificar las secuencias, facilitando el análisis de sus características y patrones.

    Unarelación de recurrencia es una fórmula para el término siguiente de una secuencia en función de sus términos anteriores.

    Un ejemplo de relación de recurrencia es \(u_{n+1}=4u_n+5\). Donde \(u_n\) es el \(n^ésimo}) término de una secuencia y la relación de recurrencia nos da una fórmula para calcular el siguiente término, \(u_{n+1}\).

    Fórmula de relación de recurrencia

    Las fórmulas de relación de recurrencia pueden adoptar muchas formas diferentes. La notación más común utiliza \(u_{n}\) para designar el \(n^{ésimo}\) término de una secuencia y \(u_{n+1}\) para designar el siguiente (o siguiente) término de una secuencia. La fórmula de una relación de recurrencia depende del orden, también denominado grado, de la relación de recurrencia.

    Orden/Grado de una relación de recurrencia

    Una relación de recurrencia de orden \(k\) es una fórmula para el \(n^{ésimo}+1\) término de la secuencia en función de los \(k\) términos anteriores de la secuencia. Otra forma de decirlo es que el orden \(k\) es la diferencia entre los subíndices mayor y menor de la relación de recurrencia.

    Una relación de recurrencia de orden/grado \(k\) es una ecuación que tiene la forma

    $$u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+a_{3}u_{n-3}+...+a_{k}u_{n-k} + f(n).$$

    Donde \(a_1,...,a_k\) son constantes y \(f(n)\) es una función en términos de \(n\).

    Una relación de recurrencia es no homog énea si \(f(n)\) es un polinomio o de la forma \(a\ veces b^{n}\).

    Si \(f(n)=0\) entonces la relación de recurrencia es homogénea.

    ¿Cuál es el orden de la relación de recurrencia \(u_{n+1}=u_{n}+5n\). ¿Es homogénea o no homogénea?

    Respuesta:

    La fórmula de las relaciones de recurrencia es \(u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+a_{3}u_{n-3}+...+a_{k}u_{n-k} + f(n)\N).

    Comparando esto con \(u_{n+1}=u_{n}+5n\) se obtiene

    • \(k=1\), ya que la diferencia entre \(n+1\), el subíndice mayor, y \(n\), el subíndice menor, es \(1\),
    • \(a_1=1\) el coeficiente de \(u_n\),
    • \(f(n)=5n\).

    Por tanto, se trata de una relación de recurrencia de primer orden no homogénea.

    ¿Cuál es el orden de la relación de recurrencia \(u_{n+1}=2u_{n}+3u_{n-1}\)? ¿Es homogénea o no homogénea?

    Responde:

    La fórmula de las relaciones de recurrencia es \(u_{n}=a_{1}u_{n-1}+a_{2}u_{n-2}+a_{3}u_{n-3}+...+a_{k}u_{n-k} + f(n)\N).

    Si comparamos esto con \(u_{n+1}=2u_{n}+3u_{n-1}}, obtenemos

    • \(k=2\), ya que la diferencia entre \(n+1\), el subíndice mayor, y \(n-1\), el subíndice menor, es \(2\),
    • \(u_1=2\) y \(u_2=3\) los coeficientes de \(u_n\) y \(u_{n-1}\) respectivamente,
    • \(f(n)=0\).

    Por tanto, se trata de una relación de recurrencia homogénea de segundo orden.

    Dada una relación de recurrencia, para calcular los términos de una secuencia necesitarás condiciones iniciales, a veces llamadas condiciones de contorno. Necesitarás el mismo número de condiciones iniciales que el orden de una relación de recurrencia para poder hallar los términos de la secuencia, es decir, para una relación de recurrencia de orden \(k^ésimo) necesitarás \(k\) condiciones iniciales para hallar los términos de la secuencia. Estas condiciones iniciales se darán normalmente como los primeros \(k\) términos de la sucesión.

    La fórmula de la sucesión de Fibonacci es una relación de recurrencia de segundo orden dada por:

    $$F_{n}=F_{n-1}+F_{n-2}$$

    Supongamos que nos dan dos condiciones iniciales \(F_0=0\) y \(F_1=1\).

    Ahora podemos calcular los términos de la sucesión.

    Aquí tienes los primeros términos escritos con la fórmula:

    \[\begin{align} F_0&=0\\F_1&=1\\F_2&=F_1+F_0=1+0=1\\F_3&=F_2+F_1=1+1=2\\F_4&=F_3+F_2=2+1=3\\F_5&=F_4+F_3=3+2=5\\F_6&=F_5+F_4=5+3=8. \end{align}\]

    Relaciones de recurrencia: Ejemplos

    Veamos algunos ejemplos de secuencias y hallemos sus fórmulas de relaciones de recurrencia.

    ¿Podemos encontrar una relación de recurrencia para la siguiente secuencia de números?

    $$3, 9, 21, 45, 93... $$

    Solución:

    La notación común utilizada para las secuencias es la siguiente

    \[\begin{align} u_1&=3\\u_2&=9\\u_3&=21\\u_4&=45\\u_5&=93. \end{align}\]

    es decir, \(u_{n}) es el \(n^{ésimo}) término de la secuencia.

    Ten en cuenta que algunos libros de texto y preguntas empiezan las secuencias con \(n=0\), así que asegúrate de comprobarlo antes de intentar una pregunta.

    Ahora podemos encontrar una fórmula para calcular un término concreto de la secuencia. Primero observa las diferencias entre términos consecutivos:

    \[\begin{align} u_2-u_1 &=9-3=6\\u_3-u_2&=21-9=12\\u_4-u_3&=45-21=24\\u_5-u_4&=93-45=48. \end{align}\]

    Esta secuencia crece en un factor 2 cada vez. Teniendo esto en cuenta, mira de nuevo la secuencia original:

    \[\begin{align} u_1&=3\\u_2&=9=2\cdot3+3\\u_3&=21=2\cdot9+3\\u_4&=45=2\cdot21+3\\u_5&=93=2\cdot45+3. \end{align}\]

    Por tanto, con valor inicial \(u_{1}=3\) la relación de recurrencia de esta secuencia es \(u_{n+1}=2u_{n}+3\).

    Supongamos que tienes una secuencia \(u_1,u_2,u_3, ...\) definida por la relación de recurrencia \(u_{n+1}=u_n+2n+1\) con valor inicial \(u_1=1\).

    Demuestra que \(u_4=16\) y, por tanto, halla una expresión para \(u_n\) en términos \(n\).

    Solución:

    La mejor forma de abordar esta cuestión es escribir los cuatro primeros términos de la secuencia.

    \[\begin{align} u_1&=1\\u_2&=u_1+2\cdot1+1=1+2+1=4\\u_3&=u_2+2\cdot2+1=4+4+1=9\\u_4&=u_3+2\cdot3+1=9+6+1=16. \end{align}\]

    Por tanto, \(u_4=16\).

    A partir de estos valores, también podemos ver que se trata de una secuencia de números cuadrados. Por tanto, una expresión para \(u_n\) en términos \(n\) es \(u_n=n^{2}\).

    Forma cerrada de las relaciones de recurrencia

    Forma cerrada, o posición a término, es el término que utilizamos para describir la fórmula del término \(n^ésimo) en términos de \(n\). En los libros de texto se puede utilizar tanto la forma cerrada como la posición a término; cualquiera de las dos formas se considera correcta. Estas ecuaciones de forma cerrada son útiles si queremos encontrar un término concreto aunque \(n\) sea grande.

    La forma cerrada es una fórmula para el término \(n^ésimo) de la sucesión en términos de \(n\).

    Un ejemplo de forma cerrada para una secuencia es \(u_{n}=4n-12\).

    Supongamos que quieres hallar el término \(1000^{th}\) de esta secuencia, entonces puedes sustituir simplemente \(n=1000\) en la ecuación y obtener:

    $$u_{1000}=4(1000)-12=3988.$$

    La forma cerrada de la sucesión de Fibonacci es

    $$F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2} \right)^{n}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n}.$$

    Encuentra la relación de recurrencia y la forma cerrada para la secuencia \(27, 9, 3, 1, \frac{1}{3},\dots\}). Supongamos que el valor inicial se denota como \(u_0=27\).

    Solución:

    En primer lugar, podemos ver que los términos de la secuencia disminuyen en un factor de 3 cada vez. Puedes comprobarlo dividiendo cada término por su término anterior, lo que nos da 3 cada vez:

    \[\frac{0}]. \frac{u_0}{u_1}&=\frac{27}{9}=3\\ \frac{u_1}{u_2}&=\frac{9}{3}=3 \\ \frac{u_2}{u_3}&=\frac{3}{1}=3\\ \frac{u_3}{u_4}&=\frac{1}{\frac{1}{3}}=3. \end{align}\]

    Suponiendo que este factor es constante a lo largo de la secuencia, la relación de recurrencia de la secuencia viene dada por:

    $$u_{n+1}=3u_n$$

    con valor inicial \(u_{0}=27\).

    Para la forma cerrada de la sucesión

    $$u_n=27\cdot \left(\frac{1}{3}\right)^{n}.$$

    Esta sucesión también se llama sucesión geométrica de razón común 3.

    Demostración de formas cerradas de relaciones de recurrencia

    La técnica utilizada para demostrar la forma cerrada de las relaciones de recurrencia es la demostración por inducción. Es posible que ya te hayas encontrado con esta técnica, pero la prueba se estructura de la siguiente manera:

    Sea \(P(n)\) un enunciado matemático tal que \(n\) es un número natural. Entonces \(P(n)\) es cierta para valores de \(n\) si se cumple lo siguiente:

    Paso 1. \(n=1\) es verdadera, es decir, se cumple \(P(1)\).

    Paso 2. Dado/Asumiendo que \(n=k\) es cierto, entonces \(n=k+1\), es decir, si \(P(k)\) se cumple entonces \(P(k+1)\) se cumple.

    Paso 3: Conclusión: Puesto que la afirmación era cierta para \(n=1\) y suponiendo que sea cierta para \(n=k\), la afirmación es cierta para \(n=k+1\). Por tanto, por el principio de inducción matemática, la afirmación es cierta para todos los números naturales \(n=1,2,3,...\).

    Para más información sobre el uso de la prueba por inducción "ver Prueba por Inducción".

    Demuestra por inducción que \(u_{n}=5^{n-1}+1\) es la forma cerrada de la sucesión definida por \(u_{n+1}=5u_{n}-4\) con valor inicial \(u_{1}=2\), para todos los números naturales n.

    Solución:

    Para este ejemplo concreto \(P(n)=u_n=5^{n-1}+1\).

    Paso 1: Sea \(n=1\),

    $$u_{1}=5^{0}+1=1.$$

    Por tanto, la afirmación se cumple para \(n=1\).

    Paso 2: Supongamos que la afirmación es cierta para \(n=k\), es decir, supongamos que \(u_{k}=5^{k-1}+1\).

    Demuestra que \(u_{n}=5^{n-1}+1\) es cierta para \(n=k+1\):

    \[\begin{align} u_{k+1}&=5u_{k}-4\\i&=5(5^{k-1}+1)-4\i&=5^{1+k-1}+5-4\i&=5^{k}+1.\end{align}]

    Por tanto, la afirmación se cumple para \(n=k+1\).

    Paso 3: Conclusión: Puesto que la afirmación era cierta para \(n=1\) y suponiendo que sea cierta para \(n=k\), la afirmación es cierta para \(n=k+1\). Por tanto, por el principio de inducción matemática, la afirmación es cierta para todos los números naturales \(n=1,2,3,...\).

    Resolución de relaciones de recurrencia

    Resolver relaciones de recurrencia consiste en encontrar la forma cerrada de una relación de recurrencia dados ciertos valores iniciales o condiciones de contorno. Existen distintos métodos para resolver relaciones de recurrencia. A veces son lo suficientemente sencillas como para resolverlas por inspección (como hemos visto antes), pero para las relaciones de recurrencia de primer y segundo orden más complejas, los mejores métodos a utilizar son la iteración o la Técnica de la Raíz Característica. Si quieres profundizar en estas técnicas, echa un vistazo a los siguientes artículos sobre Resolución de relaciones de recurrencia de primer orden y Resolución de relaciones de recurrencia de segundo orden.

    Relaciones de recurrencia - Puntos clave

    • Una relación de recurrencia da una fórmula para el siguiente término de una secuencia en función de sus términos anteriores.
    • La forma cerrada de una relación de recurrencia es una fórmula para el término \(n^ésimo) de la secuencia en función de \(n\).
    • Una relación de recurrencia de orden \(k\) es una fórmula para el \(n^ésimo+1\) término de la sucesión en función de los \(k\) términos anteriores de la sucesión.
    • Se puede utilizar la inducción matemática para demostrar resultados relativos a las relaciones de recurrencia.
    Preguntas frecuentes sobre Relación de recurrencia
    ¿Qué es una relación de recurrencia?
    Una relación de recurrencia es una ecuación que define una secuencia en función de valores anteriores de la misma secuencia.
    ¿Para qué se utilizan las relaciones de recurrencia?
    Se utilizan para describir y resolver problemas que involucran procesos iterativos o repetitivos, como crecer poblaciones o cálculos en algoritmos.
    ¿Cuáles son ejemplos comunes de relaciones de recurrencia?
    Ejemplos comunes incluyen la secuencia de Fibonacci y la relación de recurrencia en la búsqueda binaria.
    ¿Cómo se resuelve una relación de recurrencia?
    Para resolverla, se pueden usar métodos como la iteración, las técnicas de suma telescópica o el uso de transformaciones de Z.

    Descubre materiales de aprendizaje con la aplicación gratuita StudySmarter

    Regístrate gratis
    1
    Acerca de StudySmarter

    StudySmarter es una compañía de tecnología educativa reconocida a nivel mundial, que ofrece una plataforma de aprendizaje integral diseñada para estudiantes de todas las edades y niveles educativos. Nuestra plataforma proporciona apoyo en el aprendizaje para una amplia gama de asignaturas, incluidas las STEM, Ciencias Sociales e Idiomas, y también ayuda a los estudiantes a dominar con éxito diversos exámenes y pruebas en todo el mundo, como GCSE, A Level, SAT, ACT, Abitur y más. Ofrecemos una extensa biblioteca de materiales de aprendizaje, incluidas tarjetas didácticas interactivas, soluciones completas de libros de texto y explicaciones detalladas. La tecnología avanzada y las herramientas que proporcionamos ayudan a los estudiantes a crear sus propios materiales de aprendizaje. El contenido de StudySmarter no solo es verificado por expertos, sino que también se actualiza regularmente para garantizar su precisión y relevancia.

    Aprende más
    Equipo editorial StudySmarter

    Equipo de profesores de Matemáticas

    • Tiempo de lectura de 12 minutos
    • Revisado por el equipo editorial de StudySmarter
    Guardar explicación Guardar explicación

    Guardar explicación

    Sign-up for free

    Regístrate para poder subrayar y tomar apuntes. Es 100% gratis.

    Únete a más de 22 millones de estudiantes que aprenden con nuestra app StudySmarter.

    La primera app de aprendizaje que realmente tiene todo lo que necesitas para superar tus exámenes en un solo lugar.

    • Tarjetas y cuestionarios
    • Asistente de Estudio con IA
    • Planificador de estudio
    • Exámenes simulados
    • Toma de notas inteligente
    Únete a más de 22 millones de estudiantes que aprenden con nuestra app StudySmarter.

    Consigue acceso ilimitado con una cuenta gratuita de StudySmarter.

    • Acceso instantáneo a millones de materiales de aprendizaje.
    • Tarjetas de estudio, notas, exámenes de simulacro, herramientas de AI y más.
    • Todo lo que necesitas para sobresalir en tus exámenes.
    Second Popup Banner