Capítulo 10: RELACIONES DE RECURRENCIA

10.1 Introducción

En este capítulo se estudiarán los algoritmos recursivos y las relaciones de recurrencia que tienen una estrecha relación con la inducción matemática, porque en los tres casos se asumen conocidos los casos o valores anteriores (valores de arranque), que llamaremos “condiciones iniciales”. Por ejemplo, una relación de recurrencia utiliza valores anteriores de una sucesión para calcular el valor actual o valor deseado. En un algoritmo recursivo se utiliza instancias menores de la entrada actual para calcular ésta. 
En conclusión cualquiera de los temas en mención requieren de ciertas condiciones iniciales para lograr un valor o valores determinados u obtener una sucesión. 
Los conjuntos tienen otra representación en las computadoras, además de vectores, tomados como una sucesión; es decir, como una lista con un orden particular. Basta con buscar la regla que deben cumplir sus elementos y que se llamará “función característica”. 
Kurt Gödel fue un lógico, matemático y filósofo austriacoestadounidense. Nació un 28 de abril, 1906 AustriaHungría, ahora República Checa y murió el 14 de enero de 1978 Princeton, New Jersey. En la obra de Gödel pueden rastrearse los inicios de la teoría de modelos y la teoría de la recursividad. El más destacado de sus teoremas es el de la incompletitud que establece que todo artificio matemático basado en su propia definición autoconsistente lo suficientemente poderoso como para describir la aritmética de los números naturales (la aritmética de Peano), tiene proposiciones verdaderas sobre los naturales que no pueden demostrarse a partir de los axiomas. Para demostrar este teorema desarrolló una técnica denominada ahora como numeración de Gödel, el cual codifica expresiones formales como números naturales. 
En el transcurso del ese año 1933 desarrolló ideas sobre la computabilidad y la función recursiva y sobre el concepto de verdad. Posteriormente, este trabajo se desarrolló en la teoría de los números, empleando la numeración de Gödel. 
Las funciones recursivas son una clase de funciones de los números naturales en los números naturales que son computables en un sentido intuitivo. De hecho, en teoría de la computación se demuestra que las funciones recursivas son precisamente las funciones que pueden ser calculadas con el formalismo de cómputo más general conocido como lo son las máquinas de Turing.

10.2 Progresiones

Progresión es un término que procede del vocablo latino progressio. Intuitivamente se emplea para nombrar al avance o el desarrollo de algo. La noción puede vincularse al verbo proseguir, que consiste en mantener o prolongar aquello que ya se ha comenzado. Puede asociarse a progreso o secuencia. El concepto de progresión también se utiliza en las matemáticas para nombrar a la sucesión de términos o números vinculados por una cierta ley. En conclusión, se denomina progresión a una sucesión o serie de números o de términos algebraicos que pueden seguir un modelo determinado. Básicamente puede conocerse 2 tipos de progresiones: progresión aritmética y progresión geométrica

10.2.1 Progresión aritmética

Una progresión geométrica es la secuencia cuyos elementos pueden obtenerse a partir de la multiplicación (o división) que como resultado se obtiene un valor constante denominado “razón”.

Ejemplo 9.1: A) identifique cada una de las sucesiones como sucesión, progresión aritmética o progresión geométrica. Si son progresiones:

  1. 3, 7, 11, . . . Progresión aritmética

2) 1, 1, 2, 3, 5, . . . sucesión (conocida como la serie fibonacci)

3) 1, 4,16,64, . . . Progresión geométrica

4) -1, 3, -9, 27, . . . ¿cuál es?

B) encuentre el término genérico y la fórmula de la sumatoria de cada una de las siguientes sumatorias: 
1) Para la sucesión 5, 2, -1, -4, -7, -10, . . . d=2–5 = -4 — (-1) = -3 d = -3 La sucesión es aritmética El término genérico es: 8–3n. Veamos

9.2.3 Progresión cuadrática

Si una progresión no tiene las formas de la progresión aritmética ni de la geométrica, entonces podría tener la forma de la progresión cuadrática. Efectivamente, debe hacerse el siguiente análisis para determinar si es progresión cuadrática. Por consiguiente, proceda así:  calcule la diferencia “m” entre los términos de la sucesión que llamará m1, m3, m3,…  Si los valores mi son diferentes, calcule la diferencia qi entre los valores mi  Si las diferencias qi son iguales, entonces la progresión es cuadrática. 
En general se tiene: a1 a2 a3 a4 a5

Valores m: m1 m2 m3 m4 Valores q: q1 q2 q3 
donde m1= a2- a1; m2= a3- a2; m3= a4- a3; m4= a5- a4; 
 q1= m2- m1; q2= m3- m2; 
Dado que q1= q2= q3=… entonces, hagamos las qi=q.

10.3 Técnicas para calcular término genérico de progresión cuadrática

Para calcular el término genérico an, de progresión cuadrática se ofrecen 3 técnicas:

Técnica 10.1: por fórmula particular

Técnica 10.2: por ecuaciones

Para calcular los valores de los coeficientes A, B, C conforme un sistema de 3 ecuaciones lineales con 3 incógnitas, así:

(1) A+B+C=a1 (haciendo n=1 en la ecuación cuadrática)

(2) 4A+2B+C =a2 (haciendo n=2 en la ecuación cuadrática)

(3) 9A+3B+C =a3 (haciendo n=3 en la ecuación cuadrática) 
Resuelve el sistema calculando los coeficientes por cualquiera de las técnicas de solución de sistemas de ecuaciones lineales con 3 incógnitas (igualación reducción o sustitución).

Técnica 10.3: por regla práctica

Suma de los n términos

10.4 Principio de inducción matemática

Este método es de gran utilización en la teoría de números y consiste en probar la validez de una proposición, estableciendo en primer lugar que cumple para un caso determinado; posteriormente, asume que se cumple generalmente y se prueba su validez para el caso siguiente o para el caso inmediato anterior. 
Para algunos formalistas matemáticos, este principio tiene su inconveniente en que al final se tiene decir que: “así sucesivamente” o “continua indefinidamente” o algo parecido. Por lo tanto, no se ve claramente cuando termina la demostración o cuando se detiene el proceso. En efecto, se ve la necesidad de lograr un procedimiento lógico que pueda establecer la validez de una fórmula propuesta (si en verdad es cierta) sin depender de unas cuantas verificaciones. Los matemáticos han creado un teorema denominado “teorema inducción matemática” que fundamenta el proceso demostración de series en la teoría de números. 
La inducción matemática tiene sus aplicaciones en la computación, por ejemplo, entre otras en el análisis de complejidad de algoritmos, en el cálculo del total o un valor particular en series. Por ejemplo, la proposición, para todo n E N,

El término de esta sumatoria nos permite definir el número de registros en un árbol 
binario dado un determinado nivel.

Teorema de inducción matemática.

Para hacer una demostración de expresiones p(n) por inducción matemática se realizan los siguientes pasos: 
Primer paso (verificación): comprueba que la expresión cumple la igualdad para distintos casos particulares. En efecto, compruebe explícitamente que p(n) es cierta para p(1), p(2) y en otros valores particulares la proposición.

Segundo paso (hipótesis inductiva): Suponga que para n=k la expresión cumple, es decir, p(k) es cierta. 
Tercer paso (tesis inductiva): demuestre que la expresión cumple para n=k+1 o para n=k-1, esto es, p(k+1) o p(k-1) también es cierta. Aplique en adelante el método directo.

Paso 1 (Verificación): 
n=1: 1=1*2/2=1 
n=2: 1+2=2*3/2(3=3 
n=3: 1+2+3=3*4/2(6=6 
Paso 2 (hipótesis inductiva): 
Supongamos que para n=k, p(k) cumple, es decir, 1+2+3+ . . .+k=k(k+1)/2 es cierto

Paso 3 (tesis inductiva): demostremos por método directo que para n=k+1 también se cumple. En efecto, 
(1 + 2 + 3 + . . . + k )+ (k+1) =(k+1)(k+2)/2 
k(k+1)/2 + (k+1) =(k+1)(k+2)/2 Hipótesis inductiva y ley uniforme 
(k+1)(k/2+1) =(k+1)(k+2)/2 Ley distributiva 
(k+1)(k+2)/2 =(k+1)(k+2)/2 Propiedad de fraccionarios

TALLER 10.1

10.5 Recursividad

La recursividad o recursión es la técnica con la cual se especifica un proceso basado en su propia definición. Es una herramienta con amplia gama de utilidades que inicialmente fue utilizada por los matemáticos para solucionar problemas mediante definiciones recursivas. En efecto, utilizan la técnica “divide y vencerás” que consiste en descomponer un problema en subproblemas del mismo tipo que el original. A la vez cada subproblema se divide en otros subproblemas; este proceso se repite hasta que pueda resolver el problema de manera directa. De tal manera, las soluciones de los subproblemas permiten dar solución al problema original. A este proceso se denomina “recursividad”.

10.6 Subprogramas recursivos versus subprogramas iterativos

En el argot de la lógica de programación muchas veces se tienen que repetir ciertas acciones para lograr la solución de un problema; por consiguiente, se tienen varias tipos de algoritmo: algoritmos recursivos y algoritmos iterativos. 
Un subprograma recursivo es aquel que se llama a sí mismo. Son poco difundidos; tal vez por la sobrecarga en tiempo de ejecución. Los subprogramas iterativos son los más utilizados en el diseño de algoritmos. Estos subprogramas usan la estructura de programación repetitiva (denominada ciclos) que utiliza un contador o un centinela, para lograr así la solución a un problema.

Ejemplo 10.6: calcule n! (factorial de un número n) con la técnica iterativa y recursiva. 
Los algoritmos recursivos no utilizan ciclos; solamente utilizan condicionales; de ahí que basta con conseguir la condición que hace que allí finalice el algoritmo. 
El algoritmo iterativo correspondiente a la solución del problema es:

Esta última técnica es poco utilizada por los programadores en vista del consumo de memoria de estos programas. Sin embargo, se estudiará la conversión de un algoritmo iterativo en otro recursivo.

10.7 Conversión de un algoritmo iterativo en recursivo

Cualquier programa iterativo escrito con cualquier tipo de ciclo se puede transcribir a algoritmo recursivo. Una técnica sencilla está propuesta en [Flórez]7 página 110. Veámosla mediante un ejemplo. 
Ejemplo 10.7: transcriba a un programa recursivo, el siguiente programa iterativo con las siguientes líneas de un programa de referencia o principal

PASO 1: Reemplace las instrucciones propias del ciclo por sus instrucciones elementales, así:

1.1 Asigne un valor inicial a la variable de control del ciclo.

1.2 Escriba una instrucción IF que compare el valor de la variable controladora del ciclo con su valor final.

1.3 Ponga un rótulo o marca al IF escrito en el paso 1.2.

1.4 Escriba las instrucciones propias del ciclo.

1.5 Incremente la variable controladora del ciclo.

1.6 Escriba la instrucción de transferencia del control (GOTO) al rótulo definido en el paso 1.3.

1.7 Cierre o finalice la instrucción IF definido en el paso 1.2. En efecto,

PASO 2: El subprograma recursivo lo conformarán todas las instrucciones del ciclo y como parámetro ponga la variable controladora del ciclo. En nuestro ejemplo hay dos llamadas recursivas. Observe que por cada ciclo hay una llamada recursiva rotulada R1 y R2. En efecto, los subprogramas recursivos se llamarán PR1 y PR2, respectivamente:

PASO 3: Suprima todas las instrucciones del ciclo por una llamada al subprograma recursivo en el programa de referencia o llamador y reemplácelas por la instrucción de asignación del valor inicial a la variable controladora del ciclo. El valor del parámetro en esta llamada será el valor inicial de la variable controladora del ciclo

Pero observe además que PR1 hace una llamada recursiva a PR2. Por consiguiente, determinemos a PR1: subprograma PR1(I)

PASO 4: En el subprograma recursivo, reemplace las instrucciones de incremento de la variable controladora del ciclo del ciclo y GOTO por una llamada recursiva, cuyo parámetro de llamada es la variable controladora del ciclo incrementada según el incremento que tenga el ciclo. Desde luego que

En síntesis, el algoritmo recursivo quedará como sigue:

TALLER 10.2

  1. Haga un programa recursivo que calcule la serie 2+4+6+. . . 2n

2. Haga un programa recursivo que muestre los términos de la sucesión de Fibonacci.

3. Haga un programa recursivo que calcule la potencia xn.

4. Haga un programa recursivo que convierta un número en base 10 a otro de base cualquiera.

5. Los siguientes trozos a-c de un programa iterativo, conviértalos a subprogramas recursivos:

10.8 Sucesiones

Una sucesión es un conjunto ordenado de datos u objetos (diferentes o no) que conservan su forma respecto a una regla determinada. Una sucesión es una función que tiene como elemento genérico o variable dependiente un número n E N. Las sucesiones se pueden clasificar en sucesiones finitas y en sucesiones infinitas.

10.8.1 Sucesión finita

Es aquella en la que sus datos se pueden determinar en n pasos (n E N). En este caso los elementos de la sucesión están dispuestos en un orden, así: el primero, el segundo, el tercero, el cuarto y así sucesivamente.

La sucesión 2, 1, 1, 2, 1, 1, 1, 2 es finita con elementos repetidos. El primero, el cuarto y el octavo elemento de la sucesión es 2; el segundo, el tercero, el quinto, el sexto y el séptimo de la sucesión es 1. En este caso no se tiene un modelo.

10.8.2 Sucesión infinita

Es aquella en la que sus datos no se pueden determinar en n pasos (n E N), ya que se tiene que continuar indefinidamente. La manera de simbolizar la expresión “y así sucesivamente” es escribiendo al final de los término conocidos tres puntos sucesivos “. . .”, que indica que continua el modelo establecido para los primeros términos.

10.9 Modelado de fórmulas de sucesiones

Se llama fórmula de una sucesión a aquella expresión con una o más variables que permite modelar el término genérico de una sucesión. Tiene su importancia en la computación cuando se quiere analizar la complejidad de un algoritmo. 
Para modelar una sucesión se utilizan ciertos patrones que se denominan fórmulas también conocidas como término genérico; se pueden dividir en “fórmulas recurrentes o recursivas y las fórmulas explícitas”1. Las primeras se diseñan teniendo en cuenta un índice que se refiere a la posición de un término; de tal manera se construyen todos los términos, haciendo referencia al término anterior de la sucesión. Las segundas se diseñan indicando el valor exacto según la posición del término específico.

10.9.1 Fórmula explícita

Una fórmula explícita es aquella que permite determinar el valor exacto de un término de una sucesión en particular con solo tener el valor de su posición. En síntesis, una fórmula explícita es la solución de una relación de recurrencia.

10.9.2 Fórmula recurrente

Es aquella que define cualquier término de una sucesión a partir de unas condiciones iniciales o valores explícitos que corresponderán al punto de partida, teniendo en cuenta que para lograrla utiliza subíndices que indican la posición de un término en la sucesión.

Ejemplo 10.12: dada la sucesión –5, 4, 13, 22, . . . determine su fórmula recursiva

Ejemplo 10.13: dada la sucesión 45, 39, 33, 27, 21, . . . determine su fórmula recursiva

10.10 Relaciones de recurrencia

Las relaciones de recurrencia tienen su gran utilización en la solución de problemas de conteo y en problemas de análisis de algoritmos, para medir su complejidad o tiempo de ejecución de éstos. 
Una relación de recurrencia es una fórmula recursiva que se obtiene a partir de una sucesión definida por recurrencia. Permiten hallar una fórmula explícita a una sucesión definida por recurrencia a partir de unas condiciones iniciales o valores dados de manera explícita. 
Se denomina relación de recurrencia de una sucesión

a una ecuación que relaciona an (n-ésimo término) con algunos de sus términos predecesores de la sucesión (condiciones iniciales)

Los valores dados en forma explícita con un número finito de términos de la sucesión, corresponden a información acerca del comienzo de la sucesión y, por lo tanto, permiten definir la sucesión de manera recursiva.

10.10.1 Formas de relaciones de recurrencia

Las relaciones de recurrencia tienen formas muy singulares y se pueden distinguir así:

Relaciones de recurrencia con coeficientes constantes. Se subdividen a la vez en

.Relaciones de recurrencia con coeficientes constantes con formas particulares.

.Relaciones de recurrencia lineales homogéneas de orden k (orden 2 y 3).

.Relaciones de recurrencia lineales no homogéneas de orden k (no se tratarán en este libro, su estudio se puede hacer en [JOHNSONBAUGH]).

.Relaciones de recurrencia que utilizan funciones generatrices8 (no serán estudiados en este libro, pero puede ser consultado en [BRUALDI]).

10.10.2 Solución de relaciones de recurrencia

10.10.2 Solución de relaciones de recurrencia 
La solución de una relación de recurrencia correspondiente a una sucesión consiste en hallar la fórmula explícita. Se conocen varias técnicas para solucionar estas relaciones: 
. Solución con la técnica “análisis hacia atrás” o “análisis de regreso”.

. Solución utilizando algunas formas particulares (ver tabla 2).

. Solución a relaciones de recurrencia lineales homogéneas de grado 2 y 3.

10.10.3 Técnica de análisis hacia atrás o análisis de regreso

Es un método iterativo que permite dar solución a una relación de recurrencia con coeficientes constantes, la cual tiene grandes aplicaciones en análisis financiero.

Ejemplo 10.15: utilizando la técnica de análisis hacia atrás determine la fórmula explícita a partir de la relación de recurrencia.

Verifiquemos si con la fórmula explicita y la relación de recurrencia se logra la misma sucesión:

En efecto, se verifican los mismos valores para lo términos de la sucesión.

10.10.4 Solución de relaciones de recurrencia con formas particulares

Algunas relaciones de recurrencia con coeficientes constantes tienen formas especiales que producen soluciones muy particulares para la determinación de la fórmula explícita (como las planteadas en la tabla 10.3). 
Dado que k, r son enteros constantes y a1 es condición inicial de cada relación de recurrencia, el siguiente resumen podría servirle al lector como referencia para la determinación de la fórmula explícita:

Si el lector quiere realizar las demostraciones para verificar la validez del resumen anterior, puede recurrir a la técnica de análisis hacia atrás, a algunas series conocidas o a inducción matemática, para llevarlas a cabo:

Ejemplo 10.19: determine la fórmula explícita y la sucesión correspondiente a cada una de las siguientes relaciones de recurrencia:

Solución: 1. La relación de recurrencia tiene la forma 1 dada en la tabla 7.2; por lo tanto, la fórmula explícita correspondiente a:

La respectiva sucesión es: 
9, 7, 5, 3, 1, . . .

2. La relación de recurrencia tiene la forma 2 dada en la tabla 7.2; por lo tanto, la fórmula explícita correspondiente a:

an= — 4–3n(n+1)/2+3

La respectiva sucesión es: 
-4, -10, -19, -31, . . .

3. La relación de recurrencia tiene la forma 3 dada en la tabla 7.2; por lo tanto, la fórmula explícita correspondiente a:

an=10*6n-1

La respectiva sucesión es: 10, 60, 360, 2160, . . .

4. La relación de recurrencia tiene la forma 3 dada en la tabla 7.2; por consiguiente, la fórmula explícita corresponde a:

La respectiva sucesión es: 
6, 16, 46, 136, . . .

10.10.5 Solución a relaciones de recurrencia lineales homogéneas de grado k

que definen una sucesión única

El siguiente teorema es una buena técnica para solucionar este tipo de relación con coeficientes constantes.

Teorema 10.1

Dada una relación de recurrencia

con coeficientes constantes c1, c2 y sus condiciones iniciales con valores para a1 y a2 tiene como ecuación característica de grado 2

Esta ecuación tiene dos raíces r1 y r2, que pueden ser o iguales o distintas.

Teorema 10.2

Dada una relación de recurrencia

Caso 1: las raíces son diferentes

Ejemplo 9.22: calcule la solución de la relación de recurrencia definida por

Caso 2: las raíces son iguales Queda de ejercicio o consulta.

10.11 Relaciones de recurrencia lineal no homogéneas con coeficientes constantes

Una relación de recurrencia lineal no homogénea con coeficientes constantes, es una relación de la forma:

es llamada la relación de recurrencia homogénea asociada.

Teorema 10.3

Solución:

10.12 Aplicaciones de la recurrencia en el análisis de algoritmos

Las relaciones de recurrencia tienen además de las aplicaciones mencionadas en anteriores secciones otras aplicaciones, entre ellas: al análisis de algoritmos, que permite medir el tiempo de ejecución de un algoritmo.

10.12.1 Evaluación de algoritmos

La evaluación de un algoritmo consiste en medir su eficiencia respecto al consumo de memoria y del tiempo de ejecución. 
Las técnicas matemáticas permiten el análisis de algoritmos, independientemente de la configuración específica del computador o de los datos que maneje. El tiempo de ejecución de un algoritmo se determina en función de su tamaño. Generalmente, dicho tamaño se identifica de acuerdo con el número de elementos definidos para ser entrados.

10.12.2 Evaluación de memoria

En años anteriores (hasta la década de los setenta) era muy importante considerar la cantidad de memoria con la que se contaba, en vista de las limitaciones de memoria en las diferentes máquinas; de ahí la importancia de evaluar dicho consumo, para lo cual existían técnicas y una gran exigencia y esfuerzo en la programación. 
En la actualidad, debido a los enormes avances tecnológicos en la construcción de componentes del hardware (chips microprocesadores, chips de memoria, discos duros, etc.), el consumo de memoria ya no es un factor relevante de los programadores, pues son componentes de alta capacidad; tal vez, por esta razón, se abusa de la eficiencia en la programación.

10.12.3 Evaluación de tiempo de ejecución

La evaluación de tiempo de ejecución es una medida básica de la eficiencia de un algoritmo, que predice cuánto tiempo se requerirá para ejecutar un programa o algoritmo que solucione un problema determinado. 
Dicha evaluación es el factor más importante en lo que tiene que ver con el control de procesos en tiempo real, lo cual, a pesar de las altas velocidades que poseen los microprocesadores actuales, a veces se quedan cortos para procesar grandes cantidades de información. Son las razones anteriores las que indican la necesidad de que los programadores hagan ingentes esfuerzos de programación, utilizando técnicas que ayuden a aliviar el concepto de velocidad de procesamiento.

10.12.4 Medida de eficiencia de algoritmos

Para medir el tiempo de ejecución de un algoritmo se tienen dos formas: medición a posteriori y medición a priori. 
Medición a posteriori. Esta forma determina el proceso de elaboración de un algoritmo desde su análisis y diseño hasta las fases de codificación, compilación y ejecución del programa. Pero si se tiene en cuenta que al ejecutar el programa el sistema operativo tiene las herramientas suficientes para informar el tiempo de ejecución, se puede además asegurar que esta forma tiene sus inconvenientes: sólo evalúa la calidad o capacidad del compilador y de la máquina mas no del algoritmo, lo cual debiese ser su propósito, independiente de la máquina y del compilador en que se hizo el programa. 
Medición a priori. Esta forma de medir la eficiencia de un algoritmo es la que se requiere para los propósitos de lo que se va a estudiar. Pero para los efectos del caso se necesita conocer los conceptos de contador de frecuencias y orden de magnitud.

10.13 Contador de frecuencia.

Corresponde a una expresión algebraica que indica el número de veces que se ejecutan las instrucciones de un algoritmo. Para lograr esto basta con hacer una prueba de escritorio exhaustiva, para observar el comportamiento de las instrucciones. En efecto, es importante recordar o identificar algunas series que ayudarán a determinar dicho contador, tales como:

Las instrucciones que utilicen sólo la estructura secuencial o selectiva tienen como contador de frecuencia 1. En lo que respecta a ciclos, se tienen en cuenta sus límites, y a partir de ellos se consideran las series antes anotadas. Su contador de frecuencia será el límite superior menos el inferior más uno. 
Si los ciclos están anidados y las variables de control son independientes, el contador de frecuencia será el producto de los límites superiores. Si las variables de control de dos ciclos son dependientes, entonces su contador será la sumatoria de los n términos n(n+1)/2. Si son más de dos, este corresponderá a la sumatoria de los n(n+1)/2 y así sucesivamente. 
Si la variable de control de un ciclo se divide o multiplica por un número b, su contador de frecuencia será de tipo logarítmico teniendo en cuenta que el número será el dado como superior del límite del ciclo y como base el número divisor (b), de la forma Logbn. 
Cuando un ciclo logarítmico se halla anidado en otro ciclo de límite superior n sus instrucciones tendrán contador de frecuencia semilogarítmico de la forma nLogbn. 
Para las frecuencias logarítmicas o semilogarítmicas, recuerde el concepto de logaritmo: el exponente al cual hay que elevar la base para ser igual al número, esto es,

PROBLEMAS RESUELTOS

Determine el contador de frecuencia a cada uno de los siguientes algoritmos

10.14 Análisis del orden de magnitud

El orden de magnitud corresponde a la expresión algebraica que se obtiene a partir del contador de frecuencias resultante, luego de eliminar los coeficientes, las constantes y los términos negativos. Se denota por O(magnitud). En caso de que los términos sean dependientes, se toma el mayor de ellos. En otro caso, el orden de magnitud corresponderá a la suma de los términos que quedaron. Si el contador es una constante el orden de magnitud será 1.

AUTOEVALUACION 10

SELECCIÓN MÚLTIPLE DE MÚLTIPLE RESPUESTA

2. Seleccione la respuesta correcta

2.1 Un grupo de inversionistas promueve ante sus clientes que su capital invertido se triplicará al cabo de 28 meses. El interés compuesto mensual aproximado que ellos están prometiendo a sus clientes es:

A) 3%

B) 4%

C) 4.5%

D) 5% 
 
2.2 Según el interés mensual del problema 10.1, el capital invertido se duplicará

A) Entre los 14 y los 15 meses

B) Entre los 16 y los 17 meses

C) Entre los 18 y los 19 meses

D) Entre los 20 y los 21 meses 
 
2.3 Un grupo de biólogos investigadores concluyeron que esa población de bacterias se triplica cada 28 segundos. ¿la rata de crecimiento de esas bactérias para triplicarse es

A) 5%

B) 4.5%

C) 4%

D) 3% 
 
2.4 Según la rata de crecimiento por segundo correspondiente al problema 10.3, las bacterias se duplicarán

A) Entre los 14 y los 15 segundos

B) Entre los 15 y los 16 segundos

C) Entre los 16 y los 17 segundos

D) Entre los 17 y los 18 segundos

TALLER 10.3

3. Utilizando la técnica análisis hacia atrás determine la fórmula explícita para cada una de las siguientes sucesiones:

4. Determine la fórmula explicita y la correspondiente sucesión de cada una de las siguientes relaciones de recurrencia con su respectiva condición inicial:

5. Determine la fórmula explicita, la relación de recurrencia y las condiciones iniciales de cada una de las siguientes sucesiones:

6. Una cooperativa le promete a sus socios que por cada peso invertido les darán 18 centavos, como interés compuesto. Un socio quiere invertir $1´000.000 determine:

6.1 ¿Cuánto dinero recibirá de intereses en los meses 1, 2 y 3?

6.2 ¿Cuál sería la formula explícita para calcular lo que gana en cierto mes?

6.3 Según la fórmula explícita, ¿cuánto dinero recibe de interés en el mes 10?

6.4 ¿Cuánto tiempo deberá transcurrir para duplicar la cantidad invertida?

6.5 ¿Cuál es la fórmula de recurrencia? Verifique que produzca los mismos valores obtenidos por la fórmula explícita.

7. Resuelva las relaciones de recurrencia de los literales a-e que son relaciones de recurrencia lineales homogéneas con coeficientes constantes. Determine la fórmula explícita

8. Análisis de relación

En los numerales 8.1 hasta 8.6, seleccione la opción correcta, así:

A) Si la afirmación y la razón son VERDADERAS y la razón es una explicación CORRECTA de la afirmación

B) Si la afirmación y la razón son VERDADERAS, pero la razón NO es una explicación CORRECTA de la afirmación

C) Si la afirmación es VERDADERA, pero la razón es una proposición FALSA

D) Si la afirmación es FALSA, pero la razón es una proposición VERDADERA

E) Si tanto la afirmación como la razón son proposiciones FALSAS

Like what you read? Give Matematicas Discretas a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.