Módulo 4: Inducción matemática

Tema 1: Principio de inducción matemática

La inducción matemática se utiliza para demostrar afirmaciones sobre números naturales. Como los
estudiantes recordarán, podemos escribir dicha afirmación como un predicado P(n), donde el
universo del discurso para n es el conjunto de números naturales N = {1,2,...}.
Ejemplo 1: A continuación se muestran algunos ejemplos de lo que queremos decir con P(n\.
n(n+1)
P{n) 1+2——n = En € N,
2
,22 9 n(n+l)(2n+l)
Pasador) = 12—22—Hn2 = —------------9--------VneN,
6
n[n+1)12
P{n) 13423—4n3= 2 En € N,

norte
hormiga -1
P{n)
£ a' un — 1
En € N,

F(n) = n!>2"- para n > 4,

P{n) 111 1 1,
2+4+g++2n
donde = significa “lógicamente equivalente”.
Las tres primeras expresiones anteriores proporcionan fórmulas de forma cerrada para la suma
de n números enteros positivos consecutivos, la suma de los cuadrados de n números enteros
positivos consecutivos y la suma de los cubos de n números enteros positivos consecutivos,
respectivamente. La cuarta expresión es la suma de los primeros n términos de la serie geométrica y
ya la estudiamos en el Módulo 2. Las dos últimas expresiones son desigualdades útiles para el
factorial y la suma de potencias negativas de 2.
Cada afirmación P{n) anterior se refiere a números naturales o a un subconjunto de números
naturales (por ejemplo, para n > 4). ¿Cómo podemos probar tales afirmaciones? Consideremos el
primer ejemplo anterior sobre la suma de los primeros n números enteros positivos consecutivos.
Podemos verificar fácilmente que P{n) es verdadero para algunos n seleccionados. En efecto,

P(1)es verdaddesde 1=12

2’
P(2)es verdaddesde
1+2=2
P(3)es verdaddesde
1+243=34

1
Pero ¿cómo podemos demostrar que P[n) es verdadero para todo n € N?
El principio de inducción matemática (PMI) se puede utilizar para demostrar afirmaciones sobre
números naturales.

Principio de inducción matemática: Sea A un conjunto de números naturales tales que se

cumplen las dos propiedades siguientes:

(1) 1 y A;
(2) para cada número natural n

si ne th entonces n+1€A. (1)

Entonces
A = N = {1,2,...},

es decir, A contiene todos los números naturales.

¿Cómo se relaciona esto con la demostración de afirmaciones como P{n) mencionadas

anteriormente? Definamos

A={n: P(n) es verdadero para n},

es decir, A es el conjunto de números naturales para los cuales P es verdadero. El objetivo es

demostrar que A es lo mismo que el conjunto de todos los números naturales, es decir, A = N.
Imaginemos que uno verifica que P(1) es verdadero. Luego podemos establecer A = {1}.
Supongamos ahora que se puede probar el paso (2) de PMI (que llamaremos el paso inductivo). Así
pues, como sabemos que 1 € A, y sabemos que el paso inductivo es válido, digamos para n = 1,
concluimos que 2 € A. Por lo tanto, A = {1,2}, es decir, P(1) y P(2) son verdaderas. Pero utilizando
de nuevo el paso inductivo, concluimos que 3€A. Etc. En realidad, PMI nos permite reemplazar el
impreciso “etc.” por A = N, es decir, ¡P{n) es verdadero para todos los números naturales!
Pero ¿por qué es cierto, en primer lugar, el PMI? Demostramos su verdad mediante la prueba
por contradicción. Supongamos que (1) y (2) de PMI se cumplen pero A no es igual a N. Por lo
tanto, debe omitirse al menos un número natural de N. Sea no el primer número (el más pequeño)
entre 1,2,... omitido de N. Sabemos que no no puede ser 1 ya que asumimos que 1 € A por (1) de
PMI. Pero según nuestra construcción, no: IgA. Luego por el paso (2) del PMI debemos concluir
que no hay € A., lo cual es la contradicción buscada. Por lo tanto, A = N.
Introduzcamos alguna notación adicional. El primer paso (1) del PMI se denomina paso base,
mientras que el segundo paso se conoce como paso inductivo. Generalmente es trivial verificar el
paso base, y la mayor parte del trabajo debe realizarse para probar el paso inductivo. Lo
ilustraremos con el siguiente ejemplo.

Ejemplo 2: Demuestre la primera identidad anterior sobre la suma de n números naturales

nor consecutivos, es decir,
te
2
2
• n(n+l)
• =------2----' n 2 1.

3
En este caso, la propiedad P[n) es un predicado que dice que lo anterior es verdadero para n, y

A = {n: la identidad anterior es verdadera para n€N}.

Demostramos que P[n) es verdadero para todo n (es decir, A = N) usando PMI. Necesitamos pasar
por el paso básico y el paso inductivo.
Paso básico: Debemos demostrar que P(1) es verdadero, pero esto ya se estableció antes.
Paso inductivo: ahora suponemos que P(n) es verdadero para un n fijo pero arbitrario. La
suposición anterior se llama hipótesis inductiva y en nuestro caso toma la siguiente forma

K—.n(n+1)
Sni25 -------2- -

para n arbitrario. (En el símbolo anterior := significa igual por definición.) El lector debe entender
que la afirmación inmediatamente anterior y la afirmación que queremos demostrar no son la
misma, incluso si parecen similares. En la afirmación anterior suponemos que la identidad a
demostrar (sobre todas las sumas de los primeros n números naturales consecutivos) es verdadera
para un valor de n (pero arbitrario).
Ahora realizamos el paso inductivo. Debemos establecer el paso inductivo, es decir, demostrar
que la fórmula para Sn anterior implica que (n + 1)(n + 2)
n+1
2
S,+1= >ii=i
Es cierto también. Observe que arriba
reemplazamos n por n + 1 (tanto en el lado
izquierdo de la ecuación como en el lado derecho). De hecho, tenemos
norte
Sn+ 1++2++n+(n+1)=> i=i yo + (n + 1)
1

n
(,1-(+1
(1+1 (2+1)
(n+1)(n+2)
2 ’
donde en la segunda línea anterior invocamos la hipótesis de inducción, en la tercera línea
factorizamos el término (n + 1), y luego agregamos lo que queda. Esto es exactamente lo que
necesitamos para demostrar el paso inductivo.

Pero en realidad hay otra prueba directa, propuesta originalmente por el matemático del siglo
XVIII Carl Friedrich Gauss. Sea, como antes, Sn = 271 i. Escribimos la suma Sn dos veces, una
comenzando la suma desde 1 hasta n, y la segunda vez comenzando desde n hasta 1. Luego
agregamos los elementos individuales verticalmente. Esto es lo que sale:

4
 Sn = 1 + 2 ++(n- 1) + norte
Sn = norte + a — 1++ 2 + 1
2Sn = (n+1) + (n+1) + ... + (n+1) + (n+1)
Como hay n términos (n + 1) en la línea inferior, demostramos que

2Sn = n(n+1).

Nuevamente recuperamos la misma identidad.

Ejercicio 4A: Utilizando la inducción matemática, demuestre que
norte
n[n+1)(2n+1)
2,
yo=1
norte

2=
Ejercicio 4B: Utilizando inducción matemática demuestre que
n(n+1)12
2

Inducción sobre un subconjunto de números naturales

En el PMI discutido anteriormente, en el primer paso asumimos que 1€A, sin embargo, si
comenzamos la inducción desde otro número natural, digamos k, entonces se cumple para todo n>
k. Esto se muestra en el siguiente ejemplo.

Ejemplo 3: Demuestre que

n! > 2" para n > 4.

Recordamos que n!=12-3n=(n- 1)!n. Se nos pide que probemos la desigualdad anterior sólo para
n>4. Así que dejemos que
F(n) = {n! > 2n es verdadero para n > 4}.

Primero comprobamos que 4! = 24 > 24 = 16, por lo tanto P(4) es verdadera. (Observe que P(3) no es
verdadera.) Ahora supongamos que esta afirmación es verdadera para un número arbitrario de n > 4.
Debemos demostrar que

(n+1)! > 2n+1

para n > 4. Esto es fácil ya que

(n+1)! = n!(n+1)
> 2”(n+l)
2n+1.

5
La primera desigualdad se deriva de la hipótesis de inducción n! > 2", mientras que la segunda
identidad es una consecuencia de (n + 1) > 2 para n > 4. Esto demuestra la desigualdad deseada para
todos los n>4.

6
 Los siguientes dos ejemplos requieren un poco de trabajo antes de poder aplicar la inducción.

Ejemplo 4: Desigualdad de Bernoulli. Probaremos el siguiente resultado.

Teorema 1 Si n es un número natural y 1 + x > 0, entonces

(1 + x)n > 1 + nx. (2)

Prueba. La prueba es por inducción. En el paso base, asumimos n y verificamos que (1+x)n > 1+nx
es verdadero para 1 + x > 0. Ahora, suponemos (hipótesis inductiva) que (1 + x)n > 1 + nx es
verdadero para un n arbitrario, y debemos demostrar que

(1—x)n*1 >1+(n+1)x

para 1 + x > 0. Para demostrarlo procedemos de la siguiente manera:

(1+x)2t1 = (1+x)"(1+x)
por inducción
> (1 + nx)(1 + x) ya que 1 + x > 0
= 1 + (n + 1)x + nx2
> 1 + (n + 1),

donde la primera desigualdad es una consecuencia del supuesto de inducción (es decir, sabemos que
(1+x)n > 1 + nx por lo que podemos reemplazar (1 + x)" por 1 + nx porque 1+x>0; observe que si 1
+ x < 0, entonces teníamos que invertir el signo de 1 la desigualdad). El siguiente paso es álgebra
simple, mientras que el último paso se deduce del hecho de que nx2 no es negativo; no importa cuál
sea el valor de x, porque a + nx2 > a para cualquier a. Esto demuestra el teorema.

Ejemplo 5: Demostremos que

(3)

para n > 1. Lo demostramos por inducción. El primer paso para n = 1 es fácil de comprobar, por lo
que nos concentramos en el paso inductivo. Adoptamos la hipótesis inductiva, que en este caso es
111 1
1,
2+4+g++2n
y debe demostrar
que [Link].L < 1.
248 t2n 2n+1
Un enfoque natural falla. Si invocamos la hipótesis de inducción a los primeros n términos de lo
obtendr anterior, tenemos
á :
2n++

1Piense en 3 < 5 que después de multiplicarlo por —3 se convierte en —9 > —15.

7
1lo cual no implica que sea menor o igual a 1 ya que 1/2nt- > 0. Así es como procedemos
1.1(1.111)2n)
242\24784
248 en 2+1 11
por
inducción 22
1,
donde en la primera línea del lado derecho factorizamos 1/2 y observamos que lo que queda entre -
paréntesis debe ser menor que 1 por la hipótesis inductiva. El resto es álgebra simple. Esto
demuestra la desigualdad.
En algunos casos, debemos utilizar una inducción matemática generalizada que formulamos de
una forma ligeramente diferente a la anterior.
Si una afirmación P[n) es verdadera para n y si para cada n > 1, la verdad de P[n) para
todos los números naturales < n implica la verdad de P[n) para n, entonces P[n) es
verdadera para todos los números naturales.
La única diferencia entre el PMI básico y el anterior es que en el paso inductivo de la inducción
matemática generalizada asumimos que la verdad de P(1), P(2), P(n — 1) implica la verdad de P(n).
En otras palabras, el segundo paso del PMI generalizado se puede escribir como
{1,2,.,n—1}CA entonces nE A
donde A es el conjunto definido en el PMI original.

Recurrencias2
Ahora aplicamos la inducción matemática para establecer algunos hechos sobre las recurrencias.
Volvemos a las recurrencias en el Tema 3.
Comenzamos con un ejemplo que ilustra una aplicación de la inducción matemática
generalizada.

Ejemplo 6: Definamos T(0) = 1 y luego

2 71-1 T(n) = 1 + - n
n > 1. (4)
Éste es un ejemplo de recurrencia que
estudiaremos con más detalle más adelante en
este módulo. Observe que podemos calcular valores consecutivos T(1), T(2) y así sucesivamente a
partir de la recurrencia misma. Por ejemplo,

T(1)
2.......................
T(2) + l + -(T(0)+T(l)) = 5,
T(3) = 7.

2Esta subsección puede omitirse en la primera lectura.

8
Pero ¿podemos adivinar cómo crece T(n) para un valor n arbitrario? En la siguiente tabla
calculamos algunos valores numéricos de T(n) y los comparamos con el crecimiento de n y n2.

no Tennes número
2
rte se)
1 3 1
3 7 9
6 13 36
9 19 81
12 25 144
15 31 225
18 37 324

De esta tabla debemos observar que T(n) crece más rápido que n y mucho más lento que n2.
Conjeturemos entonces que3 4
T(n) < 4nlog2n, n > 2. (5)
Ahora utilizamos la inducción matemática para demostrar esta suposición. Observe que T(2) = 5 < 8
022 = 8 (ya que log2 2 = 1), pero T(1) = 3 > 4 log2 1 = 0, por lo tanto, debemos comenzar la
inducción desde n = 2.
Para llevar a cabo el paso inductivo asumiremos que para todo J < n — 1 la suposición anterior
es verdadera.
Ahora demostramos que esta suposición también es cierta para n. En efecto,
n— 1
, 2 6 2
Tennesse) 14-------1- - -1— >T()
norte nortej=2
inducció n—
148-
n m 4j log2j
registro
i
n(,1-(+1..............................................................................5
(1+1 (2+1).....................................................................................................................5
2,.................................................................................................................................7
2=.....................................................................................................................................7
>T().........................................................................................................................13
mi...............................................................................................................................13
", 6):= Hl(n-1)1 = R......................................................................................15

3Recordemos que y = log x es un logaritmo en base b de x, es decir, es el exponente al que se debe elevar b para
obtener x.
4como se muestra aquí bv = x.
9
MI(.........................................................................................................................................16
CE......................................................................................................................................16
5 C)-...................................................................................................................................16
>2’,..........................................................................................................................21
Li....................................................................................................................................23
2..................................................................................................................................25

ya que — < — log2 n, n

nn donde (i) en el primer paso usamos la recurrencia y extraemos los dos primeros
términos de la suma; (ii) en la segunda línea usamos el supuesto de inducción en su forma general y
acotamos cada T(j) por 4j log2j para 2 Kj
88,
- < - log2 n
nn
para n > 2 y por lo tanto cancelan los términos 8/n; finalmente la última desigualdad se sigue del
hecho de que 1 — 4 log2 n < 0 para n > 2. (Como dijimos al principio de esta subsección, si esta
derivación es demasiado compleja en la primera lectura, el estudiante puede avanzar a la siguiente
sección ya que no se utilizará en la próxima discusión).

1
0
Tema 2: Fórmula de suma de Newton
Desde la secundaria sabemos que

(a+1)2 GP+2ab+b2,
a3
(a+6)3 + 3a2b + 3ab2 + b3, a + 4a3 b +
(a+b)' 6a2b2 + 4ab3 + b4.

Pero ¿qué tal una fórmula para

(a+b)n

para n arbitrario Lo derivaremos aquí y se llama fórmula de suma de Newton.

Antes de abordar el caso general de (a+b)n, debemos introducir alguna notación nueva. En
particular, los coeficientes binomiales también conocidos como coeficientes de Newton. Definimos
para k natural y n > k
n! n(n — 1) • • • (n — k +
", 6):= Hl(n-1)1 =----R------
donde recordamos que n!=12-3(n—1).n. Por definición 0! = 1. En la literatura los coeficientes de
Newton C (n, k) también se denotan como

•-(:)
De la definición encontramos inmediatamente

C(n,0) = 1
C(n,1) = n
C[n^n—k) = C[n^n—k).

Pero también necesitaremos el siguiente lema.

Lema 1 para k y n naturales

C(n, k) = C(n — 1, k) + C(n — 1, k — 1). (6)

Prueba. Damos una prueba directa. Observar que

(n — 1)! (n — 1)!
C[n — 1, k — 1) + C[n — 1, k —
kl(nk-1)! + (k-1)!(nk)!
1)
(n — si f — k) (n—lfi.k
k\(n — k — l)!(n — k) {k — l)\k(n — k)\
(n, ,
s(n-*)! (nsk**
¡norte!
kyn-kfi
C(n, k)

1
1
 donde en la segunda línea multiplicamos y
dividimos el primer término por n—k y el segundo
término por k.
Luego factorizamos kn y después de un poco de álgebra simple obtenemos el resultado deseado.
Ahora, estamos listos para formular y probar la fórmula de suma de Newton.
Teorema 2 Para cualquier n
natural
[a+b)n
MI akbn-k (7)

(
Prueba.4 La prueba es por inducción con respecto a n. El paso base para n = 1 es fácil de
comprobar ya que (7(1,0) = C(1, 1) = 1.
Ahora comenzamos el paso inductivo y postulamos que si (7) es verdadero para un número
arbitrario de n, entonces
n+1
(a+b)n+l ^2C(n+l,k)akbn+1-kk=0
Debe ser verdad. Procedemos de la siguiente manera

(a+b)nt1 (a+b)n(a+b) ^C{n,k)ak+1bn-kk=0 ^C{n,k)akbn+1-kk=0

C(n + 1, O)bn*1 + abn [C(n, 0) + C(n, 1)]

+ a2b"--[C(n,1)+C(n,2)]+
+ akbn~k+1 [C(n, k - 1) + C(n, k)]+...

+ yb [C(n, n) + C(nz n — 1)] + C(n + 1, n + \)a" + i n+l

^2C(n+l,k)akbn+1-k.
Lema k=0

En la primera línea anterior utilizamos la inducción matemática y luego multiplicamos. En las

siguientes líneas agrupamos términos con la misma potencia, es decir a'bnti' para todo i.
Finalmente, aplicamos el Lema 1 (es decir, C(n, k)+C(n,k-1)=C(n+1, k)) para terminar la
derivación.

Ejercicio 4C: Aplicar la fórmula de Newton a la siguiente

2 1
(1++ ) .

La fórmula anterior puede conducir a identidades sorprendentemente interesantes.

Aquí hay dos de ellos.
n/.N

CE
2n (8)

0 (9)

4La prueba puede omitirse en la primera

5 C)-
lectura.
1
2
La primera identidad se desprende inmediatamente de la fórmula de Newton aplicada a

(121)"
mientras que el segundo se desprende de
(1-1)".

Volveremos a derivar estas identidades utilizando argumentos combinatorios en uno de los

próximos módulos.

1
3
Tema 3: Recursión y recurrencias

A veces es difícil definir un objeto explícitamente. En tales casos, es mejor definir este objeto en
términos de sí mismo, pero de un tamaño más pequeño. (De hecho, hemos visto este principio en
funcionamiento en la inducción matemática). Este proceso se llama recursión y a menudo se
describe matemáticamente mediante una recurrencia.

Ejemplo 7: Definir a0=1 y para n > 0

un+1 — 2an.

Veamos qué obtenemos. Primero calculamos algunos valores de muestra:

ax = 2, a2 = 2a1 = 4,
a3 = 2a2 = 2(2a1) = 8 = 23,
a = 2a3 = 2(2a2) = 2(2(2ai)) = 24.

Basándonos en esta evidencia numérica, conjeturamos que an = 2n. Podemos demostrarlo usando
inducción matemática. Pero en esto es más fácil dar una prueba directa, que se llama telescopía.
Procedemos de la siguiente manera:

an+1 — 2an — 2 • 2an-1 — 2 • 2an—2 — ■ ■ ■ 2 + — • • • — 2 años — 2 .

En lo anterior utilizamos sucesivamente la recurrencia a; = 2a—1 hasta que llegamos al valor inicial
ao y sabemos que a0=1. Observemos que sin conocer ao no podemos ni iniciar la recurrencia ni
finalizarla.

Ejercicio 4D: Derive una fórmula explícita para la siguiente recurrencia para n > 1

un — 3an-1

con ao = 1.

Podemos definir algunas otras funciones recursivamente. Por ejemplo, F[n) = n! se puede
definir recursivamente de la siguiente manera

F(0) = 1,
F(n + 1) = (n+1)F(n), n > 0.

1
4
Además,
dejemos que n
S o
n

1
5
donde {ak}_o es una secuencia dada. Para que una computadora entienda dicha suma, debemos
definirla recursivamente. Por ejemplo, podemos hacerlo de esta manera

Así que = hazlo,

Sn+1 — Sn + an-1, n > 0.
Pero consideremos recurrencias más generales. Subrayamos que para iniciar una recurrencia
debemos definir algunos valores iniciales y proporcionar un “método” para calcular el siguiente
valor. Considere la siguiente recurrencia

IR = 1,
un — un +2, n > 1.
Esta recurrencia comienza con
1,3,7,15,...

pero ¿cuál es una fórmula general para un? Traslademos el término an—1 al otro lado de la
recurrencia y escribamos todos los valores de la siguiente manera

a1 — ao = 2 a—a = 22 a — a = 23

ai ~ Cj-1 2’

_ en-1
n(,1-(+1.........................................................................................................................5
(1+1 (2+1)....................................................................................................................5
2,.................................................................................................................................7
2=.....................................................................................................................................7
>T().........................................................................................................................13
mi...............................................................................................................................13
", 6):= Hl(n-1)1 = R......................................................................................15
MI(.........................................................................................................................................16
CE......................................................................................................................................16
5 C)-...................................................................................................................................16
>2’,..........................................................................................................................21
Li....................................................................................................................................23
2.................................................................................................................................25

1
6
Ahora, cuando sumamos todas estas ecuaciones, la mayoría de ellas se cancelarán (decimos que la
suma se extiende) excepto a y ao, lo que nos da

En C0 — >2’,
yo=1

que es lo mismo que decir

un=>2. (10)
yo=0
¿Es esto mejor que la recurrencia original? Todavía no, porque debemos calcular la suma. En
realidad, en el Módulo 2 definimos la progresión geométrica de la siguiente manera

bn=rn, n = 0,1,...

1
7
y nosotros norte 1 _ rn+l
derivamos S,=>'= r7 1. (11)
yo=0 1—r

En realidad, volveremos a demostrar esta fórmula usando inducción matemática. Es fácil

comprobar su veracidad para n (el paso base). Pasemos al paso inductivo. Primero asumimos que la
afirmación anterior es verdadera para un número arbitrario de n, y tratamos de demostrar que esto
implicaría que n+1
Sn+1=>,'=
1 - rn+2
yo=0 1—r

Procedemos de la
siguiente manera
n+l

Sn-+1 = 2
yo=0
norte
> rl + yn + 1
yo=0
inducción 1 — rn-+1 ,4
= —--------------- +TT
1—r
1 rn+1 + rn+1 rn+2
1—r
donde en la segunda línea extraemos el último término de la suma y lo escribimos por separado
como rTti, luego en la siguiente línea aplicamos a la primera suma la hipótesis inductiva, y
finalmente después de algo de álgebra demostramos la fórmula deseada.
Ahora, podemos volver a (10) para concluir que
norte
En = > = > -1.
yo=0
Resolvamos algunas recurrencias más. Ésta es la única manera de aprender a manejarlos. Deja
bo y
bn = bn_i + n, n > 1.

Realizamos el siguiente
telescopiado
bn = bn-i + n
= (bn_2 + n - 1) + n
= bn-z + (n - 2) + (n - 1) + n

bi + (i + 1) + {i + 2) + • • • + n

1
8
 bo+1+23H(n-1)+n
norte
Li
yo=1
n(n+1)
2
donde en la segunda línea sustituimos bn—1 = & — n — 2 + (n — 1), en la tercera línea
comenzamos a observar un patrón en el que bi es seguido por la suma de los primeros i— números
naturales. Luego aplicamos la suma de n números naturales consecutivos derivados en el Ejemplo 2.
En cada paso de la derivación anterior utilizamos la propia recurrencia para reducirla hasta llegar al
valor que conocemos, es decir, bo. Podemos hacerlo ya que en el paso i sabemos que bi = b—1 + i.
Consideremos ahora una recurrencia más complicada:5

co= 0,
Cn — 2cn_1 + fi-

Comencemos el proceso telescópico y tratemos de encontrar un patrón general. Tenemos

Cn-2Cn1+n
= 2(2cn-2 + n - 1) + n = 22cn-2 + 2(n - 1) + n
= 22 (2c,-3 + n — 2) + 2(n — 1) + n
= 23c,-3 + 22(n — 2) + 2(n — 1) + n
= 23(2c,=4 + n — 3) + 22(n — 2) + 2(n — 1) + n
= 24c,_4 + 23(n - 3) + 22(n - 2) + 2(n - 1) + n

— 2^cn—i + 2(n — t) + 21 cn_1 + • • • + 22(n — 2) + 2(n — 1) + n

= 2nc0 + 2n--[n -{n- 1)] + 2n~2[n - (n - 2)] + • • • + 22(n - 2) + 2(n - 1) + nn—1

= >2*(nk).k=0

En la segunda línea anterior, sustituimos Cn—1 por 2cn-2 +n—1 y observamos que el “término
aditivo” ahora es n + 2(n — 1) (el término aditivo es el que no involucra a Ci). Después de otra
sustitución, el término aditivo se amplía a 22(n-2)+2(n—1)- n. Ahora deberías poder ver el patrón
que se convierte en 2'(n — i) + 2'l~lcn-i+i H- -22(n-2)+2(n—1)-n. Después de la última
sustitución el término aditivo es finalmente 2"-I[n — (n — 1)] + 2"-2[n -(n-2)]- 22
(n-2) +
2(n-1) + n.

5Los dos ejemplos siguientes pueden omitirse en la primera lectura.

1
9
 Ahora para terminar la recurrencia debemos encontrar una fórmula para la
siguiente suma n— n—1 n—1
en = ^2k(nk) =n^2k -^k2k.
k=ok=ok=o
Observe que en la primera suma podríamos factorizar n ya que la suma es sobre k, por lo tanto n es
fijo. Después de esta observación, la primera suma es fácil de estimar. Acabamos de descubrir
arriba que es igual a 2" — 1. Pero el segundo es más difícil. Para estimarlo primero observamos que

2^+1 - 2k = 2k(2 - 1) = 2k.

Ento
nces norte
k2k
norte
>*2*=)
norte
)k(2kt1-2k)
k=1
>k2*t1
k=1 2 k2k
k=1
norte n—
(A) >k2**t1 Ar| l)
k=1

norte n— 1 norte
>k2641 ->k261 ->26+1
(B n— 1
) > k2*+1 + n2n+1 -
k=o
k=o k=o k=o
n—
>k2*th- >2**1
k=ok=o
• n21+1 - 0 - (211+1 - 2) = (n - 1)2nt1 + 2.

En la linea (A) cambiamos el índice de la sumatoria de a a k + 1, en la linea (B) desarrollamos la

primera suma y observamos que cancela la segunda suma, finalmente en la linea (C) aplicamos la
suma geométrica que ya discutimos anteriormente.
Volviendo a la recurrencia, juntando todo lo que tenemos

cn = 2n+1 - n - 2

Cuál es nuestra respuesta final. Uffff... no fue tan difícil.

Finalmente, resolvemos una recurrencia no lineal. Considere lo siguiente 6

6El próximo análisis puede omitirse por completo y regresar solo si un estudiante está interesado en una mejor -
comprensión de las recurrencias no lineales.

2
0
 an = a, n > 1
donde ao = 1. Es una recurrencia no lineal ya que an -1 se eleva al cuadrado. La telescopia puede
resultar difícil en este caso de recurrencia. Así que primero lo simplificamos. Definir bn = log2 an.
Entonces tenemos

&o = 1
bn = ^bn—l + log2 3

ya que log(xy) = log x + log y. Ahora estamos en terreno familiar. Usando el telescopio
encontramos

bn _(2" - l)log23,

Lo que implica
an = 2(2"-1)log23 = 32"-1

Por último, debemos decir que siempre es una buena idea verificar numéricamente nuestra solución
comparando sus valores iniciales con los valores calculados a partir de la recurrencia misma.

2
1