10 Ejemplos de Demostraciones por Inducción

Anteriormente presentamos una breve explicación del Método de Inducción Matemática.

En esta ocasión vamos a exponer 10 ejemplos de problemas resueltos utilizando este método, con el fin de ilustrar un poco más los alcances de este recurso.

(Esta entrada participa en el «Carnaval de Matemáticas» cuyo blog anfitrión es Gaussianos).

Problema 1. Demostrar que si \( n\) es un número entero positivo, entonces \( 4^n+15n-1\) es múltiplo de \( 9\).

Solución:

a) Primeramente, si \( n=1\) entonces: \( 4^1+15(1)-1=18\) y como \( 9 \mid 18\) se tiene que la afirmación es cierta.

b) Asumimos como hipótesis de inducción que \( 9 \mid (4^n + 15n -1)\), y debemos demostrar que \( 9 \mid (4^{n+1} + 15(n+1) -1)\).

En efecto:

\[ 4^{n+1} + 15(n+1) – 1\]
\[ = 4^{n+1} + 15n + 15 – 1\]
\[ = 4^{n+1} – 4^n + (4^n + 15n – 1) + 15\]
\[ = 4^n(4-1) + 9k + 15\]

con \( k \in \mathbb{N}\), por la hipótesis de inducción.

\[ = 3(4^n) + 9k + 15\]
\[ = 3(3+1)^n + 15 + 9k\]

Aplicando Binomio de Newton:

\( = 3(3^n+3^2p+1) + 15 + 9k\); para algún \(p \in \mathbb{N}\)

\[ = 9 \cdot 3^{n-1} + 9 \cdot 3p + 18 + 9k\]
\[ = 9 (3^{n-1} + 3p + 2 + k)\]
\[ \Rightarrow 9 \mid [4^{n+1} + 15(n+1) – 1] \blacksquare \]

Problema 2. Demuestre que si \( n \in \mathbb{N}\), entonces:

\[ \displaystyle { 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{2^n – 1} > \frac{n}{2} } .\]

Solución:

a) Si \( n=1\) se tiene que \( 1 > \frac{1}{2}\) lo cual es cierto.

b) Asumimos ahora que:

\[ \displaystyle { 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{2^n – 1} > \frac{n}{2} }\]

y habrá que utilizar esto para demostrar que:

\[ \small{ 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{2^n – 1} + \frac{1}{2^n} + \frac{1}{2^n + 1} + \cdots + \frac{1}{2^{n+1} – 1}> \frac{n+1}{2} }. \]

Pero aplicando la hipótesis de inducción, basta probar que

\[ \displaystyle { \frac{1}{2^n} + \frac{1}{2^n + 1} + \cdots + \frac{1}{2^{n+1} – 1} \geq \frac{1}{2} } . \]

Esta última expresión contiene \( [2^{n+1} – 1 – (2^n)] + 1 = 2^n\) fracciones. Pero entonces:

\[ \displaystyle { \frac{1}{2^n} + \frac{1}{2^n + 1} + \cdots + \frac{1}{2^{n+1} – 1} \geq \frac{1}{2^{n+1}} + \frac{1}{2^{n+1}} + \cdots + \frac{1}{2^{n+1}} } \]

repitiéndose la fracción \( \frac{1}{2^{n+1}}\) en el segundo término \( 2^n\) veces.

\[ \displaystyle { \Rightarrow \frac{1}{2^n} + \frac{1}{2^n + 1} + \cdots + \frac{1}{2^{n+1} – 1} \geq 2^n \cdot \frac{1}{2^{n+1}} = \frac{1}{2} } \blacksquare \]

Problema 3. Demuestre que si \( n \in \mathbb{N}\), y

\[ S_n = \frac{0}{1!} + \frac{1}{2!} + \frac{2}{3!} + \cdots + \frac{n-1}{n!} , \]

entonces \( S_n = \frac{n!-1}{n!}\).

Solución:

a) Sea \( n = 1\), \( S_1 = \frac{0}{1!} = 0 = \frac{1!-1}{1!}\).

b) Asumimos ahora que para \( n = p\), \( S_p = \frac{p!-1}{p!}\).

Hay que demostrar que para \( n = p + 1\), \( S_{p+1} = \frac{(p+1)!-1}{(p+1)!}\).

Pero, por definición:

\[ \displaystyle { S_{p+1} = \frac{0}{1!} + \frac{1}{2!} + \frac{2}{3!} + \cdots + \frac{p-1}{(p)!} + \frac{p}{(p+1)!} } , \]

y al aplicar la hipótesis te inducción:

\[ = \displaystyle { \frac{p!-1}{p!} + \frac{p}{(p+1)!} } \]
\[ = \displaystyle \frac{(p!-1)(p+1) + p}{(p+1)!} \]
\[ = \displaystyle \frac{p \cdot p! – p + p! -1 + p}{(p+1)!} \]
\[ = \displaystyle \frac{p! (p + 1) – 1}{(p+1)!} \]
\[ = \displaystyle \frac{(p + 1)! – 1}{(p+1)!} \blacksquare \]

Problema 4. Demuestre que si \( n \in \mathbb{N}; n \geq 2\) entonces

\( \sqrt {1} + \sqrt {2} + \sqrt {3} + \cdots + \sqrt {n} > n\).

Solución:

a) Sea \( n = 2\), tenemos \( (\sqrt {1} + \sqrt {2})^2 = 1 + 2\sqrt{2} + 4 \).

\[ \Rightarrow \sqrt {1} + \sqrt {2} = \sqrt{5 + 2\sqrt{2}} > \sqrt{4} = 2 \]

b) Tenemos como hipótesis inductiva que para \( n = k\) se cumple

\[ \sqrt {1} + \sqrt {2} + \sqrt {3} + \cdots + \sqrt {k} > k .\]

Hay que demostrar que, sea \( n = k+1\), es cierto que

\[ \sqrt {1} + \sqrt {2} + \sqrt {3} + \cdots + \sqrt {k} + \sqrt {k+1} > k+1 . \]

Pero, utilizando la hipótesis inductiva:

\[ \sqrt {1} + \sqrt {2} + \sqrt {3} + \cdots + \sqrt {k} + \sqrt {k+1}> k + \sqrt {k+1} . \]

Y como:

\[ (k + \sqrt {k+1})^2 = k^2 + 2k\sqrt{k+1} + k + 1 > k^2 + 2k + 1 \]
\[ \Rightarrow k + \sqrt {k+1} > k + 1 \]
\[ \Rightarrow \sqrt {1} + \sqrt {2} + \sqrt {3} + \cdots + \sqrt {k} + \sqrt {k+1} > k + \sqrt {k+1} > k + 1 \]

Por tanto \( \forall n \in \mathbb{N}; n \geq 2\),

\[ \sqrt {1} + \sqrt {2} + \sqrt {3} + \cdots + \sqrt {n} > n. \blacksquare \]

Problema 5. Demuestre que si \( n \in \mathbb{N}\) entonces \( 3 \mid (10^{n+1} + 10^n + 1)\).

Solución:

a) Probemos que para \( n = 1\) se cumple:

\[ 10^{1+1} + 10^1 + 1 = 21 \]
\[ 3 \mid 21 .\]

b) Como hipótesis de inducción asumimos que para

\[ n = k, 3 \mid (10^{k+1} + 10^k + 1) ; \]

entonces hay que demostrar que

\[ 3 \mid (10^{n+1} + 10^{k+1} + 1) . \]

Pero notemos que:

\[ 10^{k+2} + 10^{k+1} + 1 \]
\[ = 10\cdot 10^{k+1} + 10 \cdot 10^{k} + 1 \]
\[ = 10(10^{k+1} + 10^{k}) + 1 + 10^{k+1} + 10^{k} – 10^{k+1} – 10^{k} \]
\[ = 10(10^{k+1} + 10^{k}) – 1(10^{k+1} + 10^{k}) + (10^{k+1} + 10^{k} + 1) \]

y aplicando la hipótesis te inducción:

\( = 9(10^{k+1} + 10^{k}) + 3p\); con algún \( p \in \mathbb{N} \)

\[ = 3[3(10^{k+1} + 10^{k}) + p] \]

con lo cual queda demostrada la tesis. \( \blacksquare\)

Problema 6. Pruebe que

\[ \displaystyle {S_n = 1^3 + 2^3 + 3^3 + \cdots + n^3 = \left [\frac{n(n+1)}{2} \right ]^2 } . \]

Solución:

a) Sea \( n = 1\), \( S_1 = 1^3 = 1 = 1^2 = \left [\frac{2}{2} \right]^2 = \left [\frac{1(1+1)}{2} \right ]^2 \).

b) Sea \( n = p\), asumimos que \( S_p = \left [\frac{p(p+1)}{2} \right ]^2\), y con esto demostremos que \( S_{p+1} = \left [\frac{(p+1)(p+2)}{2} \right]^2 \).

Por definición:

\[ \displaystyle {S_{n+1} = 1^3 + 2^3 + 3^3 + \cdots + p^3 + (p+1)^3 = S_p + (p+1)^3 } \]

y haciendo uso de la hipótesis inductiva:

\[ \displaystyle { = \left [\frac{p(p+1)}{2} \right]^2 + (p+1)^3 } \]
\[ = \displaystyle \frac{p^2(p^2+2p+1) + 4p^3 + 12p^2 + 12p + 4}{4} \]
\[ = \displaystyle \frac{p^4 + 2p^3 + p^2 + 4p^3 + 12p^2 + 12p + 4}{4} \]
\[ = \displaystyle \frac{p^4 + 4p^3 + 4p^2 + 2p^3+ 8p^2 + 8p + p^2 + 4p + 4}{4} \]
\[ = \displaystyle \frac{(p^2 + 2p + 1)(p^2 + 4p + 4)}{4} \]
\[ = \displaystyle \frac{(p+1)^2(p+2)^2}{2^2} \]
\[ = \displaystyle \left [\frac{(p+1)(p+2)}{2} \right ]^2 . \]

Y de esta manera queda demostrado. \( \blacksquare\)

Problema 7. Si \( x \in \mathbb{R}; x > -1\), \( n \in \mathbb{N}; n \geq 2\), demuestre la siguiente desigualdad:

\[ (1 + x)^n \geq 1 + nx .\]

Solución:

a) Sea \( n = 2\), esto implica que \( (1+x)^2 = 1 + 2x + x^2\), y como \( x^2 \geq 0\)

\[ \Rightarrow 1 + 2x + x^2 \geq 1 + 2x \]
\[ \Rightarrow (1+x)^2 \geq 1 + 2x . \]

b) Asumimos ahora como hipotesis inductiva que si \( n \in \mathbb{N}; n \geq 2\) se cumple que \( (1 + x)^n \geq 1 + nx\).

Debemos demostrar que \( (1 + x)^{n+1} \geq 1 + (n+1)x\).

Pero \( (1 + x)^{n+1} = (1 + x)^n(1 + x)\) y aplicando la hipótesis de inducción:

\[ \small { ((1 + x)^{n+1} \geq (1 + nx)(1 + x) = 1 + nx + x +nx^2 = 1 + x(n + 1) + nx^2 } \]

y dado que \( x^2 \geq 0\), entonces \( 1 + x(n + 1) + nx^2 \geq 1 + x(n + 1)\).

Entonces tenemos que \( (1 + x)^{n+1} \geq 1 + x(n + 1)\) y con esto se demuestra la tesis. \( \blacksquare\)

Para un caso más general, puede revisar el artículo publicado sobre la Desigualdad de Bernoulli.

Problema 8. Pruebe que la desigualdad

\[ \displaystyle {1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \leq \frac{n}{2} + 1 } \]
es válida \( \forall n \in \mathbb{N}; n \geq 1\).

Solución:

a) Para \( n = 1\) es válido pues \( 1 \leq \frac{1}{2} + 1\).

b) Asumimos como hipótesis de inducción que efectivamente se cumple

\[ \displaystyle {1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \leq \frac{n}{2} + 1 } . \]

Debemos demostrar que

\[ \displaystyle {1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} + \frac{1}{n+1} \leq \frac{n+1}{2} + 1 } . \]

Pero, aplicando la hipótesis de inducción:

\[ \displaystyle {1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} + \frac{1}{n+1} \leq \frac{n}{2} + 1 + \frac{1}{n+1}} . \]

Y dado que \( 1 \leq n\), sumando \( n^2 + n + 1\) en ambos lados de la desigualdad tenemos:

\[ n^2 + n + 2 \leq n^2 + 2n + 1 \]
\[ \Rightarrow n^2 + n + 2 \leq (n+1)^2 \]
\[ \Rightarrow \displaystyle { \frac{n(n+1)+2}{2(n+1)} \leq \frac {n+1}{2} }\]
\[ \Rightarrow \displaystyle { \frac{n}{2} + 1 + \frac{1}{n+1} \leq \frac {n+1}{2} + 1 } \]

y esto implica que

\[ \displaystyle {1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} + \frac{1}{n+1} \leq \frac{n}{2} + 1 + \frac{1}{n+1} \leq \frac {n+1}{2} + 1} . \]

Por lo tanto se demuestra la tesis. \( \blacksquare\)

Problema 9. Demuestre la siguiente proposición:

\[ \displaystyle { \sum_{k=1}^n (2k – 1) 3^k = (n – 1) 3^{n+1} + 3 }; \forall n \in \mathbb{N} \]

Solución:

a) Se comprueba para \( n = 1\)

\[ \displaystyle { \sum_{k=1}^1 (2 – 1) 3^1 = 3 = (1 – 1) 3^{1+1} + 3 } \]

b) Luego, se tiene la hipótesis inductiva para \( n = h\)

\[ \displaystyle { \sum_{k=1}^h (2k – 1) 3^k = (h – 1) 3^{h+1} + 3 } \]

y debemos demostrar que para \( n = h+1\) se cumple

\[ \displaystyle { \sum_{k=1}^{h+1} (2k – 1) 3^k = (h + 1 – 1) 3^{h+1+1} + 3 } \]

es decir

\[ \displaystyle { \sum_{k=1}^{h+1} (2k – 1) 3^k = 3^{h+2} \cdot h + 3 } \]

Pero, por definición

\[ \displaystyle { \sum_{k=1}^{h+1} (2k – 1) 3^k = \sum_{k=1}^{h} (2k – 1) 3^k +(2(h+1) – 1) 3^{h+1} } \]

y aplicando la hipótesis de inducción esto es:

\[ \displaystyle { \sum_{k=1}^{h+1} (2k – 1) 3^k = (h – 1) 3^{h+1} + 3 + [2(h+1) – 1] 3^{h+1} } \]
\[ \Rightarrow \displaystyle { \sum_{k=1}^{h+1} (2k – 1) 3^k = (h – 1) 3^{h+1} + 3 + (2h+2 – 1) 3^{h+1} } \]
\[ \Rightarrow \displaystyle { \sum_{k=1}^{h+1} (2k – 1) 3^k = 3^{h+1} (h – 1 + 2h + 1) + 3 } \]
\[ \Rightarrow \displaystyle { \sum_{k=1}^{h+1} (2k – 1) 3^k = 3^{h+1} 3h + 3 } \]
\[ \Rightarrow \displaystyle { \sum_{k=1}^{h+1} (2k – 1) 3^k = 3^{h+2}\cdot h + 3 } \]

Y por lo tanto la proposición dada se verifica \( \forall n \in \mathbb {N}\). \( \blacksquare\)

Problema 10. Sea \( (a_n)\) definido por: \( a_1 = 14; a_{n+1} = {a_n}^2 – 2\), pruebe por inducción que \( \forall n \geq 1\) el número

\[ \displaystyle { \sqrt{3({a_n}^2 – 4)} } \]

es divisible por 4.

Solución:

a) Sea \( n = 1\), por definición \( a_1 = 14\)

\[ \Rightarrow \displaystyle { \sqrt{3({a_1}^2 – 4)} = \sqrt{3(196 – 4)} = \sqrt{576} = 24 } \]

y \( 4 \mid 24\).

a) Por otro lado, asumimos que para \( n = p\) se ha demostrado que \( 4 \mid \sqrt{3({a_p}^2 – 4)}\), como hipótesis de inducción.

Debemos probar que para \( n = (p+1); 4 \mid \sqrt{3({a_{p+1}}^2 – 4)}\).

Pero, por definición de \( (a_n)\):

\[ \displaystyle \sqrt{3({a_{p+1}}^2 – 4)} \]
\[ = \displaystyle \sqrt{3[({a_p}^2 – 2)^2 – 4]} \]
\[ = \displaystyle \sqrt{3[({a_p}^4 – 4{a_p}^2 + 4) – 4]} \]
\[ = \displaystyle \sqrt{3({a_p}^4 – 4{a_p}^2)} \]
\[ = \displaystyle a_p \sqrt{3({a_p}^2 – 4)} \]

y según la hipótesis inductiva, \( a_p = 4k\) para algún \( k \in \mathbb{N}\), entonces

\[ = \displaystyle 4k \sqrt{3({a_p}^2 – 4)} \]
\[ \Rightarrow 4 \mid \displaystyle \sqrt{3({a_{p+1}}^2 – 4)} \]

con lo cual queda demostrada la tesis. \( \blacksquare\)