Capítulo 10 — Inducción, Recurrencia y Sumas¶
10.2 — Definiciones por Recurrencia¶
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 \(a^n\) del §1.2 era "\(a\) multiplicado por sí mismo \(n\) veces", es decir, \(a^1=a\) y \(a^{n+1}=a^n\cdot a\). Los polígonos del capítulo 5 duplicaban sus lados en cada paso, y las aproximaciones de \(e\) 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 "\(a_{n+1}\) se obtiene de \(a_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 \(\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.
§1. Sucesiones¶
Definición. Una sucesión de números reales es una función \(a:\mathbb{N}\to\mathbb{R}\), en el sentido del §2.1. Su valor en \(n\) se escribe \(a_n\) y se llama término \(n\)-ésimo; la sucesión entera se denota \((a_n)\) o \((a_n)_{n\in\mathbb{N}}\).
La definición también admite sucesiones indexadas en \(\mathbb{N}_0\) o en los enteros \(n\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 \(n\), cuál es su término. Una fórmula como \(a_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 \((a_n)\) converge a un número \(L\), y se escribe \(\lim_{n\to\infty}a_n=L\), si para todo \(\varepsilon>0\) existe \(N\) tal que \(|a_n-L|<\varepsilon\) para todo \(n>N\). Es el formalismo \(\varepsilon\)–\(N\) del §2.4 aplicado a funciones de dominio \(\mathbb{N}\).
§2. El teorema de recursión¶
Teorema (de recursión). Sean \(c\in\mathbb{R}\) y \(g:\mathbb{N}\times\mathbb{R}\to\mathbb{R}\) una función. Existe una única sucesión \((a_n)\) tal que
Demostración. La unicidad es una inducción directa. Si \((a_n)\) y \((b_n)\) cumplen ambas condiciones, entonces \(a_1=c=b_1\), y si \(a_n=b_n\), entonces \(a_{n+1}=g(n,a_n)=g(n,b_n)=b_{n+1}\). Por el principio de inducción, \(a_n=b_n\) para todo \(n\).
La existencia exige más cuidado, porque no se puede "definir \(a_n\) para todo \(n\)" 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 \(I_n=\{k\in\mathbb{N} : k\leq n\}\). Por el §10.1 §2, \(I_{n+1}=I_n\cup\{n+1\}\). Se dirá que una función \(f:I_n\to\mathbb{R}\) es admisible si \(f(1)=c\) y \(f(k+1)=g(k,f(k))\) para todo \(k\) con \(k+1\leq n\).
Primero se prueba por inducción que, para cada \(n\), existe una única función admisible \(f_n:I_n\to\mathbb{R}\). Para \(n=1\), \(I_1=\{1\}\) y la única función admisible es \(f_1(1)=c\). Supóngase que existe una única \(f_n\) admisible sobre \(I_n\). Se define \(f_{n+1}\) sobre \(I_{n+1}\) igual a \(f_n\) en \(I_n\) y con \(f_{n+1}(n+1)=g(n,f_n(n))\). Es admisible, porque las condiciones con \(k+1\leq n\) las cumple \(f_n\) y la condición con \(k=n\) se cumple por construcción. Es la única, porque si \(h\) es admisible sobre \(I_{n+1}\), su restricción a \(I_n\) es admisible sobre \(I_n\) y, por la hipótesis inductiva, coincide con \(f_n\). Entonces \(h(n+1)=g(n,h(n))=g(n,f_n(n))=f_{n+1}(n+1)\).
Se define ahora \(a_n=f_n(n)\) para cada \(n\in\mathbb{N}\). Por la unicidad recién probada, la restricción de \(f_{n+1}\) a \(I_n\), que es admisible, coincide con \(f_n\). En particular \(f_{n+1}(n)=f_n(n)=a_n\), y por lo tanto
Además \(a_1=f_1(1)=c\). La sucesión cumple ambas condiciones. \(\blacksquare\)
La demostración no usó ninguna propiedad de \(\mathbb{R}\), solo que es un conjunto. El teorema vale, con la misma prueba, si \(\mathbb{R}\) se reemplaza por cualquier conjunto \(X\), y esa generalidad se aprovecha en el §5. También vale para sucesiones que empiezan en \(0\) o en cualquier entero \(n_0\), por el mismo corrimiento de índices del §10.1 §3.
§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\in\mathbb{R}\), la sucesión de potencias es la única que cumple \(a^1=a\) y \(a^{n+1}=a^n\cdot a\); se completa con \(a^0=1\). El factorial es la única sucesión indexada en \(\mathbb{N}_0\) con
Así, \(1!=1\), \(2!=2\), \(3!=6\), \(4!=24\), y en general \(n!\) es el producto de los naturales desde \(1\) hasta \(n\). La convención \(0!=1\) no es arbitraria: es la única que hace valer la regla \((n+1)!=(n+1)\,n!\) también para \(n=0\).
Dada una sucesión \((a_k)\), su suma parcial hasta \(n\) se define como la única sucesión \((S_n)\) con \(S_1=a_1\) y \(S_{n+1}=S_n+a_{n+1}\), y se escribe
La letra \(k\) 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 \(\sum_{k=m}^{n}a_k\) para enteros \(m\leq n\), empezando por \(a_m\), y se conviene en que una suma sin términos, con \(n=m-1\), vale \(0\). El producto \(\prod_{k=1}^{n}a_k\) se define igual, con \(P_1=a_1\) y \(P_{n+1}=P_n\cdot a_{n+1}\), y un producto sin factores vale \(1\). Con esta notación, \(n!=\prod_{k=1}^{n}k\) y \(a^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 \(n\).
Proposición. Para sucesiones \((a_k)\) y \((b_k)\), números reales \(\alpha\) y \(\beta\), y naturales \(m<n\), se cumplen:
Demostración. Para la linealidad, el caso \(n=1\) es \(\alpha a_1+\beta b_1\) en ambos miembros, y el paso inductivo consiste en sumar \(\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 \(m\) fijo, por inducción en \(n\geq m+1\), sumando \(a_{n+1}\) a ambos miembros. Para la suma telescópica, con \(n=1\) ambos miembros valen \(b_2-b_1\), y si vale para \(n\), entonces
Para la inversión, se prueba por inducción en \(n\) la afirmación "la igualdad vale para toda sucesión". Con \(n=1\), ambos miembros son \(a_1\). Supóngase que vale para \(n\) y para toda sucesión. Separando el primer término de la suma invertida y renombrando el índice con \(j=k-1\),
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 \(b_{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, \(a^{m+n}=a^m a^n\) se demuestra fijando \(m\) e induciendo en \(n\): para \(n=1\) es la definición de \(a^{m+1}\), y si vale para \(n\), entonces \(a^{m+n+1}=a^{m+n}\cdot a=a^ma^n\cdot a=a^ma^{n+1}\). Las leyes \((a^m)^n=a^{mn}\) y \((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.
Recordatorio. Una recurrencia \(a_1=c\), \(a_{n+1}=g(n,a_n)\) define una única sucesión. \(\sum\) y \(\prod\) son sucesiones definidas por recurrencia, y sus propiedades se prueban por inducción. Telescópica: \(\sum_{k=1}^n(b_{k+1}-b_k)=b_{n+1}-b_1\).
§4. Recurrencias de orden dos¶
Algunas sucesiones se definen por una regla que usa los dos términos anteriores. La más famosa es la de Fibonacci:
cuyos primeros términos son \(1,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 \(X\) resuelve el problema. Se toma \(X=\mathbb{R}^2\) y se define la sucesión de pares \(v_n=(F_n,F_{n+1})\) por \(v_1=(1,1)\) y \(v_{n+1}=g(v_n)\), con \(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 \(\varphi=\tfrac{1+\sqrt5}{2}\) y \(\psi=\tfrac{1-\sqrt5}{2}\). Para todo \(n\in\mathbb{N}\),
Demostración. Los números \(\varphi\) y \(\psi\) son las dos raíces de \(t^2=t+1\), por la fórmula cuadrática del §1.5, así que \(\varphi^2=\varphi+1\) y \(\psi^2=\psi+1\); además \(\varphi-\psi=\sqrt5\). Sea \(P(n)\) la igualdad del enunciado. Para \(n=1\), el segundo miembro es \(\tfrac{\varphi-\psi}{\sqrt5}=1=F_1\). Para \(n=2\), es \(\tfrac{\varphi^2-\psi^2}{\sqrt5}=\tfrac{(\varphi+1)-(\psi+1)}{\sqrt5}=1=F_2\). Sea \(n\geq 3\) y supóngase \(P(k)\) para todo \(k<n\). Entonces, usando \(P(n-1)\) y \(P(n-2)\),
Por inducción fuerte, \(P(n)\) vale para todo \(n\). \(\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=2\). Omitir el segundo caso base es un error frecuente, y no es inocuo: la sucesión \(G_1=1\), \(G_2=5\), \(G_{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, \(\sqrt5\), aparece en todas partes, y sin embargo el resultado es siempre un número natural. Como \(|\psi|<1\), el término \(\tfrac{\psi^n}{\sqrt5}\) es muy pequeño, y \(F_n\) es el natural más próximo a \(\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.