Skip to content

Chapter 10 — Induction, Recursion and Sums

10.2 — Definiciones por Recurrencia

This content is not available in your language yet.

Dar el primer paso y la regla para dar cada paso siguiente parece suficiente para describir un camino infinito; que efectivamente lo sea es un teorema.


El libro definió muchos objetos dando un comienzo y una regla. La potencia ana^n del §1.2 era ”aa multiplicado por sí mismo nn veces”, es decir, a1=aa^1=a y an+1=an⋅aa^{n+1}=a^n\cdot a. Los polígonos del capítulo 5 duplicaban sus lados en cada paso, y las aproximaciones de ee del capítulo 4 se obtenían término a término. En todos los casos se daba por sentado que la regla determina un único objeto. No es evidente. Una regla del tipo ”an+1a_{n+1} se obtiene de ana_n” describe cómo avanzar un paso, pero la sucesión completa es un objeto infinito, y hay que probar que existe una sola función definida en todo N\mathbb{N} que respete la regla. Esta sección lo prueba, y después usa el resultado para definir con precisión los símbolos ∑\sum y ∏\prod, que el resto del capítulo usa constantemente.

Definición. Una sucesión de números reales es una función a:N→Ra:\mathbb{N}\to\mathbb{R}, en el sentido del §2.1. Su valor en nn se escribe ana_n y se llama término nn-ésimo; la sucesión entera se denota (an)(a_n) o (an)n∈N(a_n)_{n\in\mathbb{N}}.

La definición también admite sucesiones indexadas en N0\mathbb{N}_0 o en los enteros n≥n0n\geq n_0, con los cambios obvios. Que una sucesión sea una función, y no una “lista infinita”, tiene una consecuencia inmediata: dos sucesiones son iguales si y solo si tienen los mismos términos en cada índice, y una sucesión está bien definida cuando se sabe, para cada nn, cuál es su término. Una fórmula como an=1na_n=\tfrac{1}{n} lo dice directamente. Una regla de recurrencia no lo dice, y el teorema siguiente suple esa falta.

Se recuerda que, como en el capítulo 4, una sucesión (an)(a_n) converge a un número LL, y se escribe lim⁡n→∞an=L\lim_{n\to\infty}a_n=L, si para todo ε>0\varepsilon>0 existe NN tal que ∣an−L∣<ε|a_n-L|<\varepsilon para todo n>Nn>N. Es el formalismo ε\varepsilon–NN del §2.4 aplicado a funciones de dominio N\mathbb{N}.

Teorema (de recursión). Sean c∈Rc\in\mathbb{R} y g:N×R→Rg:\mathbb{N}\times\mathbb{R}\to\mathbb{R} una función. Existe una única sucesión (an)(a_n) tal que

a1=c,an+1=g(n,an)  para todo n∈N.a_1=c,\qquad a_{n+1}=g(n,a_n)\ \text{ para todo } n\in\mathbb{N}.

Demostración. La unicidad es una inducción directa. Si (an)(a_n) y (bn)(b_n) cumplen ambas condiciones, entonces a1=c=b1a_1=c=b_1, y si an=bna_n=b_n, entonces an+1=g(n,an)=g(n,bn)=bn+1a_{n+1}=g(n,a_n)=g(n,b_n)=b_{n+1}. Por el principio de inducción, an=bna_n=b_n para todo nn.

La existencia exige más cuidado, porque no se puede “definir ana_n para todo nn” sin tener ya el objeto cuya existencia se quiere probar. El camino es construir primero aproximaciones finitas y probar que encajan. Como en el §10.1 §4, sea In={k∈N:k≤n}I_n=\{k\in\mathbb{N} : k\leq n\}. Por el §10.1 §2, In+1=In∪{n+1}I_{n+1}=I_n\cup\{n+1\}. Se dirá que una función f:In→Rf:I_n\to\mathbb{R} es admisible si f(1)=cf(1)=c y f(k+1)=g(k,f(k))f(k+1)=g(k,f(k)) para todo kk con k+1≤nk+1\leq n.

Primero se prueba por inducción que, para cada nn, existe una única función admisible fn:In→Rf_n:I_n\to\mathbb{R}. Para n=1n=1, I1={1}I_1=\{1\} y la única función admisible es f1(1)=cf_1(1)=c. Supóngase que existe una única fnf_n admisible sobre InI_n. Se define fn+1f_{n+1} sobre In+1I_{n+1} igual a fnf_n en InI_n y con fn+1(n+1)=g(n,fn(n))f_{n+1}(n+1)=g(n,f_n(n)). Es admisible, porque las condiciones con k+1≤nk+1\leq n las cumple fnf_n y la condición con k=nk=n se cumple por construcción. Es la única, porque si hh es admisible sobre In+1I_{n+1}, su restricción a InI_n es admisible sobre InI_n y, por la hipótesis inductiva, coincide con fnf_n. Entonces h(n+1)=g(n,h(n))=g(n,fn(n))=fn+1(n+1)h(n+1)=g(n,h(n))=g(n,f_n(n))=f_{n+1}(n+1).

Se define ahora an=fn(n)a_n=f_n(n) para cada n∈Nn\in\mathbb{N}. Por la unicidad recién probada, la restricción de fn+1f_{n+1} a InI_n, que es admisible, coincide con fnf_n. En particular fn+1(n)=fn(n)=anf_{n+1}(n)=f_n(n)=a_n, y por lo tanto

an+1=fn+1(n+1)=g(n,fn+1(n))=g(n,an).a_{n+1}=f_{n+1}(n+1)=g\big(n,f_{n+1}(n)\big)=g(n,a_n).

Además a1=f1(1)=ca_1=f_1(1)=c. La sucesión cumple ambas condiciones. ■\blacksquare

La demostración no usó ninguna propiedad de R\mathbb{R}, solo que es un conjunto. El teorema vale, con la misma prueba, si R\mathbb{R} se reemplaza por cualquier conjunto XX, y esa generalidad se aprovecha en el §5. También vale para sucesiones que empiezan en 00 o en cualquier entero n0n_0, por el mismo corrimiento de índices del §10.1 §3.

§3. Potencias, factoriales, sumas y productos

Sección titulada «§3. Potencias, factoriales, sumas y productos»

Con el teorema de recursión, cada definición “por repetición” del libro se convierte en una definición precisa. Para a∈Ra\in\mathbb{R}, la sucesión de potencias es la única que cumple a1=aa^1=a y an+1=an⋅aa^{n+1}=a^n\cdot a; se completa con a0=1a^0=1. El factorial es la única sucesión indexada en N0\mathbb{N}_0 con

0!=1,(n+1)!=(n+1)⋅n!.0!=1,\qquad (n+1)!=(n+1)\cdot n!.

Así, 1!=11!=1, 2!=22!=2, 3!=63!=6, 4!=244!=24, y en general n!n! es el producto de los naturales desde 11 hasta nn. La convención 0!=10!=1 no es arbitraria: es la única que hace valer la regla (n+1)!=(n+1) n!(n+1)!=(n+1)\,n! también para n=0n=0.

Dada una sucesión (ak)(a_k), su suma parcial hasta nn se define como la única sucesión (Sn)(S_n) con S1=a1S_1=a_1 y Sn+1=Sn+an+1S_{n+1}=S_n+a_{n+1}, y se escribe

∑k=1nak=Sn.\sum_{k=1}^{n}a_k=S_n.

La letra kk es una variable muda. No tiene significado fuera del símbolo, y puede reemplazarse por cualquier otra que no esté en uso. Del mismo modo se define ∑k=mnak\sum_{k=m}^{n}a_k para enteros m≤nm\leq n, empezando por ama_m, y se conviene en que una suma sin términos, con n=m−1n=m-1, vale 00. El producto ∏k=1nak\prod_{k=1}^{n}a_k se define igual, con P1=a1P_1=a_1 y Pn+1=Pn⋅an+1P_{n+1}=P_n\cdot a_{n+1}, y un producto sin factores vale 11. Con esta notación, n!=∏k=1nkn!=\prod_{k=1}^{n}k y an=∏k=1naa^n=\prod_{k=1}^{n}a.

Las propiedades de las sumas que se usan en todo cálculo son consecuencias de estas definiciones, y cada una se prueba por inducción en nn.

Proposición. Para sucesiones (ak)(a_k) y (bk)(b_k), números reales α\alpha y β\beta, y naturales m<nm<n, se cumplen:

∑k=1n(αak+βbk)=α∑k=1nak+β∑k=1nbk(linealidad),\sum_{k=1}^{n}(\alpha a_k+\beta b_k)=\alpha\sum_{k=1}^{n}a_k+\beta\sum_{k=1}^{n}b_k\qquad\text{(linealidad)}, ∑k=1nak=∑k=1mak+∑k=m+1nak(particioˊn),\sum_{k=1}^{n}a_k=\sum_{k=1}^{m}a_k+\sum_{k=m+1}^{n}a_k\qquad\text{(partición)}, ∑k=1n(bk+1−bk)=bn+1−b1(suma telescoˊpica),\sum_{k=1}^{n}(b_{k+1}-b_k)=b_{n+1}-b_1\qquad\text{(suma telescópica)}, ∑k=1nak=∑k=1nan+1−k(inversioˊn del orden).\sum_{k=1}^{n}a_k=\sum_{k=1}^{n}a_{n+1-k}\qquad\text{(inversión del orden)}.

Demostración. Para la linealidad, el caso n=1n=1 es αa1+βb1\alpha a_1+\beta b_1 en ambos miembros, y el paso inductivo consiste en sumar αan+1+βbn+1\alpha a_{n+1}+\beta b_{n+1} a los dos lados de la hipótesis y reagrupar con las propiedades de la suma del §1.1. La partición se prueba con mm fijo, por inducción en n≥m+1n\geq m+1, sumando an+1a_{n+1} a ambos miembros. Para la suma telescópica, con n=1n=1 ambos miembros valen b2−b1b_2-b_1, y si vale para nn, entonces

∑k=1n+1(bk+1−bk)=(bn+1−b1)+(bn+2−bn+1)=bn+2−b1.\sum_{k=1}^{n+1}(b_{k+1}-b_k)=(b_{n+1}-b_1)+(b_{n+2}-b_{n+1})=b_{n+2}-b_1.

Para la inversión, se prueba por inducción en nn la afirmación “la igualdad vale para toda sucesión”. Con n=1n=1, ambos miembros son a1a_1. Supóngase que vale para nn y para toda sucesión. Separando el primer término de la suma invertida y renombrando el índice con j=k−1j=k-1,

∑k=1n+1an+2−k=an+1+∑j=1nan+1−j=an+1+∑j=1naj=∑k=1n+1ak,\sum_{k=1}^{n+1}a_{n+2-k}=a_{n+1}+\sum_{j=1}^{n}a_{n+1-j}=a_{n+1}+\sum_{j=1}^{n}a_j=\sum_{k=1}^{n+1}a_k,

donde la segunda igualdad es la hipótesis inductiva. ■\blacksquare

La suma telescópica merece atención especial, porque es el recurso más potente para calcular sumas en forma cerrada. Si el término general de una suma puede escribirse como diferencia bk+1−bkb_{k+1}-b_k de términos consecutivos de otra sucesión, todos los términos intermedios se cancelan y solo quedan el último y el primero. El §10.3 y el §10.4 la usan para calcular las sumas geométricas y para descubrir, no solo verificar, las fórmulas de las sumas de potencias.

Las leyes de los exponentes naturales del §1.2 también quedan probadas. Por ejemplo, am+n=amana^{m+n}=a^m a^n se demuestra fijando mm e induciendo en nn: para n=1n=1 es la definición de am+1a^{m+1}, y si vale para nn, entonces am+n+1=am+n⋅a=aman⋅a=aman+1a^{m+n+1}=a^{m+n}\cdot a=a^ma^n\cdot a=a^ma^{n+1}. Las leyes (am)n=amn(a^m)^n=a^{mn} y (ab)n=anbn(ab)^n=a^nb^n se prueban del mismo modo, e inducción mediante, quedan justificados los exponentes enteros y racionales que el capítulo 1 construyó sobre ellas.

Algunas sucesiones se definen por una regla que usa los dos términos anteriores. La más famosa es la de Fibonacci:

F1=1,F2=1,Fn+2=Fn+1+Fn,F_1=1,\qquad F_2=1,\qquad F_{n+2}=F_{n+1}+F_n,

cuyos primeros términos son 1,1,2,3,5,8,13,21,341,1,2,3,5,8,13,21,34. El teorema de recursión, tal como se enunció, solo permite mirar un término hacia atrás, pero su versión para un conjunto cualquiera XX resuelve el problema. Se toma X=R2X=\mathbb{R}^2 y se define la sucesión de pares vn=(Fn,Fn+1)v_n=(F_n,F_{n+1}) por v1=(1,1)v_1=(1,1) y vn+1=g(vn)v_{n+1}=g(v_n), con g(x,y)=(y,x+y)g(x,y)=(y,x+y). El teorema da una única sucesión de pares, y su primera coordenada es la sucesión de Fibonacci. El mismo recurso vale para cualquier recurrencia que use un número fijo de términos anteriores.

Las propiedades de estas sucesiones se prueban naturalmente por inducción fuerte, porque cada término depende de dos anteriores. La más sorprendente es una fórmula cerrada.

Proposición (fórmula de Binet). Sean φ=1+52\varphi=\tfrac{1+\sqrt5}{2} y ψ=1−52\psi=\tfrac{1-\sqrt5}{2}. Para todo n∈Nn\in\mathbb{N},

Fn=φn−ψn5.F_n=\frac{\varphi^n-\psi^n}{\sqrt5}.

Demostración. Los números φ\varphi y ψ\psi son las dos raíces de t2=t+1t^2=t+1, por la fórmula cuadrática del §1.5, así que φ2=φ+1\varphi^2=\varphi+1 y ψ2=ψ+1\psi^2=\psi+1; además φ−ψ=5\varphi-\psi=\sqrt5. Sea P(n)P(n) la igualdad del enunciado. Para n=1n=1, el segundo miembro es φ−ψ5=1=F1\tfrac{\varphi-\psi}{\sqrt5}=1=F_1. Para n=2n=2, es φ2−ψ25=(φ+1)−(ψ+1)5=1=F2\tfrac{\varphi^2-\psi^2}{\sqrt5}=\tfrac{(\varphi+1)-(\psi+1)}{\sqrt5}=1=F_2. Sea n≥3n\geq 3 y supóngase P(k)P(k) para todo k<nk<n. Entonces, usando P(n−1)P(n-1) y P(n−2)P(n-2),

Fn=Fn−1+Fn−2=φn−2(φ+1)−ψn−2(ψ+1)5=φn−2φ2−ψn−2ψ25=φn−ψn5.F_n=F_{n-1}+F_{n-2}=\frac{\varphi^{n-2}(\varphi+1)-\psi^{n-2}(\psi+1)}{\sqrt5}=\frac{\varphi^{n-2}\varphi^2-\psi^{n-2}\psi^2}{\sqrt5}=\frac{\varphi^n-\psi^n}{\sqrt5}.

Por inducción fuerte, P(n)P(n) vale para todo nn. ■\blacksquare

La prueba necesitó dos casos iniciales, no uno, porque el paso inductivo usa los dos términos anteriores y no puede aplicarse a n=2n=2. Omitir el segundo caso base es un error frecuente, y no es inocuo: la sucesión G1=1G_1=1, G2=5G_2=5, Gn+2=Gn+1+GnG_{n+2}=G_{n+1}+G_n cumple la misma recurrencia, y la fórmula de Binet es falsa para ella. La fórmula tiene, además, algo de paradójico: un número irracional, 5\sqrt5, aparece en todas partes, y sin embargo el resultado es siempre un número natural. Como ∣ψ∣<1|\psi|<1, el término ψn5\tfrac{\psi^n}{\sqrt5} es muy pequeño, y FnF_n es el natural más próximo a φn5\tfrac{\varphi^n}{\sqrt5}. El número φ\varphi es la razón áurea, y la fórmula muestra que la sucesión de Fibonacci crece como una progresión geométrica de razón φ\varphi, el tema de la sección siguiente.


Con las sumas definidas y sus propiedades probadas, pueden calcularse en forma cerrada las sumas de las dos familias de sucesiones más simples: las que avanzan sumando una cantidad fija y las que avanzan multiplicando por un factor fijo.