1r ciclo Demostración por inducción: 2^n>n

[arreldepi]

Hola, tengo otro problema con la siguiente demostración por inducción:

$2^n>n$

En general, todas las demostraciones por inducción con desigualdades me cuestan bastante, ya que no entiendo qué es lo que hacen en el último paso:

1. Suponemos cierta para n=1:

$2^1>1$

2. Suponemos que es cierta para n

$2^n>n \overbrace{\Rightarrow}^{?} 2^{n+1}>n+1$

3. Y a partir de aquí empiezan a comparar $2^n\cdot 2$ con términos hasta que llegan al resultado inicial, pero no entiendo qué procedimiento siguen.


Muchas Gracias.

[pod]

Re: Demostración por inducción: 2^n>n

Este ejercicio me suena bastante. Vamos, que me tocaba hacerlo en clase cuando daba problemas en el curso cero

1. Suponemos cierta para n=1:

$2^1<1$

A mi esa ecuación me da un poco de mala espina.

Por cierto, no centres las ecuaciones así. Usa [tex=*], se centran solas.

2. Suponemos que es cierta para n

$2^n>n \overbrace{\Rightarrow}^{?} 2^{n+1}>n+1$

3. Y a partir de aquí empiezan a comparar $2^n\cdot 2$ con términos hasta que llegan al resultado inicial, pero no entiendo qué procedimiento siguen.

Muchas Gracias.

Hombre, el procedimiento que siguen no lo sé (hay varias formas de hacerlo). Pero la forma más sencilla es partir de lo que se sabe (por hipotesis),

$$2^n > n\ ,$$

y multiplicar por dos ambos miembros de la desigualdad (como dos es un número positivo, al multiplicar no cambia la desigualdad)

$$2^{n+1} > 2n\ .$$

Por lo tanto, lo que queremos demostrar es cierto si

$$2n \ge n+1\ .$$

Supongo que este es el paso más difícil de entender. Básicamente, estamos haciendo una cadena de desigualdades. 2n es más pequeño que $2^n$; por lo tanto si demostramos que n+1 es igual o menor a 2n, entonces la desigualdad original se cumplirá,

$$2^n > 2n \ge n+1 \Longrightarrow 2^n > n+1\ .$$

Es obvio que $2n \ge n+1$ para cualquier valor positivo de n, es decir $n \ge 1$. Esto completa la demostración.

Si no recuerdo mal, después de este ejercicio te toca demostrar que $3^n > 2n$. Se hace de forma similar, inténtalo.

[Afisionado]

Re: Demostración por inducción: 2^n&gt;n

Hola. No había visto el de Pod antes de la previsualización pero ya que lo he escrito, lo envío aunque es más o menos igual
Yo lo haría así:

1. Suponemos cierta para n=1:

$2^1>1$

2. Suponemos que es cierta para n, donde $n \in \mathbb{N}$. Si a n+1 le llamamos m resulta que también $m \in \mathbb{N}$, y tenemos que

$2^n>n \Rightarrow 2^{n+1}=2^m > m=n+1$

3. Por otro lado, tenemos que $2^{n+1} = 2^n\cdot 2$. Si, como ya sabemos, $2^n>n$ podemos sustituir $2^n$ por n y observamos que sigue siendo válido que $2n > n+1$ para todo número natural, luego es también $2^{n+1}>n+1$ como se quería demostrar.

Saludos.

[arreldepi]

Re: Demostración por inducción: 2^n&gt;n

A mi esa ecuación me da un poco de mala espina.

Uis, cierto, me he equivocado al teclear xD.

$$2n \ge n+1\ .$$

Supongo que este es el paso más difícil de entender. Básicamente, estamos haciendo una cadena de desigualdades. 2n es más pequeño que $2^n$; por lo tanto si demostramos que n+1 es igual o menor a 2n, entonces la desigualdad original se cumplirá,

$$2^n > 2n \ge n+1 \Longrightarrow 2^n > n+1\ .$$

Es obvio que $2n \ge n+1$ para cualquier valor positivo de n, es decir $n \ge 1$. Esto completa la demostración.

Oks, creo que ya entiendo algo más. Lo comparas con este término porque en lugar de indicar que:

$$2^n\cdot 2 >2n.$$

Podrías indicarlo así:

$$2^{n+1} > n+1$$

Ahora entiendo lo que se compara pero no el por qué . No termino de ver la relación entre que 2n es menor que $2^n$ (bueno, no sé si esto importa pero para n=1 y n=2, no se cumple, no?) y tampoco qué relación hay entre que el 2n sea mayor o igual que n+1 influya para la demostración.

Bueno, creo que me he explicado un poco mal, pero la idea es esa, que no termino de ver las relaciones entre $2^n,\; 2n \; \textrm{y}\; n+1$

Si no recuerdo mal, después de este ejercicio te toca demostrar que $3^n > 2n$. Se hace de forma similar, inténtalo.

Pues sí, ése es el siguiente! Tienes buena memoria


Gracias de nuevo!

[ser humano]

Re: Demostración por inducción: 2^n&gt;n

como ya te dijeron, como tenes que

$2^{n+1}> 2n$, para que la hipotesis valga tiene que ser valido que $2n \ge n + 1$.
porque a lo que vos queres llegar es a que $2^{n+1}$(1) es siempre mayor a $n+1$. a lo que en principio llegas operando es que (1) es mayor a $2n$, por lo tanto si $2n$ es mayor o igual a $n+1$, claramente (1) sera mayor (ya que es mayor a $2n$).
yo demostraria esto tambien por induccion.
vale para uno pues:
$2*1 \ge 1+1$

hipotesis inductiva:
vale que
$2k \ge k + 1$

vale para K + 1 pues:

por hipotesis
$2k \ge k + 1$

sumando 2 a ambos terminos

$2k +2 \ge k + 1 + 2$

entonces

$2(k+1) \ge k + 3$

como para todo k vale que $k+3>k+2$
entonces
$2(k+1) > (k + 1) +1$

ya ahi queda demostrado

[pod]

Re: Demostración por inducción: 2^n&gt;n

Creo que lo que ocurre es que no entiendes la filosofía del método de inducción. La cosa es la siguiente. Tenemos un enunciado A(n) que depende de un número natural, $n \in \mathbb{N}$. Queremos demostrar que ese enunciado es cierto para todos los valores de n. Una forma de hacerlo sería tomar todos los valores posibles y ver que se cumple; es decir, A(1), A(2), A(3)... Pero como hay infinitos números naturales, sería un coñazo por que no terminaríamos a tiempo para la cena.

A alguien que tenía muchas ganas de cenar ya se le ocurrió una forma de hacer todas esas demostraciones a la vez. Se dio cuenta que, tras hacer muchas demostraciones de estas, cada vez que iba al siguiente número tenía que repetir prácticamente el mismo procedimiento. Pensó que sería fantástico que, una vez hecha una demostración, la siguiente ya estuviera hecha por si sola, ya que sería similar. Entonces, se le ocurrió lo siguiente.

Supongamos que A(n) es cierta. Fíjate que aquí n es un número natural cualquiera. Es un número fijo, pero puede ser cualquiera de ellos. Este A(n) no hay que demostrarlo, supongo que es cierto. Esto es lo que llamamos hipótesis.

Entonces, si soy capaz de demostrar que el hecho que A(n) sea cierto, implica necesariamente que A(n+1) también es cierto, tendré mucho trabajo hecho. Es decir, utilizando el hecho que A(n) se cumple, tengo llegar a demostrar que A(n+1) también es cierto.

Si consigo hacer esa demostración, entonces siempre que encuentre un A(m) que sea cierto, entonces automáticamente sabré que A(m+1) también es cierto. Repitiendo el razonamiento, sabré que A(m+2) también es cierto. Y así sucesivamente.

Una vez hecho esto, si yo consigo demostrar que A(1) es cierto (es decir, la proposición para el primer número natural posible), entonces automáticamente sabré que A(2) es cierto. Y A(3)... y de hecho, saltando de uno en uno podré llegar a cualquier número natural.

A la práctica, para usar el método de inducción, tengo que seguir los siguientes pasos.

1) Demostrar que la proposición es cierta para el primer valor posible, A(1). A veces, puede ser que el primer valor posible sea cero; o puede que sea para un valor mayor.

2) Suponer que A(n) es cierto para un valor general de n. Fijaos que aquí no tengo que demostrar nada, supongo que es cierto. Es mi hipótesis de inducción.

3) Haciendo uso de que sé que A(n) es cierto, tengo que demostrar que A(n+1) también es cierto. Éste es el paso más complicado. En general, hay dos vías para hacer esa demostración: partir de lo que sabemos que es cierto y, tras ciertas manipulaciones, obtener la expresión A(n+1) (esto es lo que hacemos en este problema). O bien, partir de A(n+1) y haciendo uso de la hipótesis, demostrar que es cierta (como en este otro problema).

Hagamos el problema de nuevo para ejemplificar lo dicho. Queremos demostrar que $2^n > n$.

1) El primer valor es n = 1. Simplemente tenemos que substituir,

$$2 > 1\ ,$$

lo cual es cierto. Por lo tanto, el enunciado es cierto para el primero de los números posibles.

2) Suponemos que la expresión es cierta para un n arbitrario,

$$2^n >n \ .$$

Esto es algo que es cierto, por hipótesis, y por lo tanto lo puedo utilizar siempre que lo necesite.

3) Ahora, haciendo uso de lo anterior, tengo que demostrar que también es cierto

$$2^{n+1} > n+1\ .$$

¿Cómo demuestro que (2) es cierto? Pues parto de (1), que sé que es cierto. Multiplico por dos ambos lados de la desigualdad,

$$2^{n+1} > 2n\ .$$

Como he multiplicado por dos una desigualdad que sé que es cierta, esta última desigualdad también debe serlo, forzosamente. Ahora bien, comparando (2) y (3), se me ocurre escribir la cadena de desigualdades

$$2^{n+1} > 2n \ge n+1\ .$$

Fíjate que si esta cadena de desigualdades se cumple, se deduce que (2) es cierta. Así que ahora tengo que demostrar esta cadena de igualdades.

La primera desigualdad de la cadena yo sé que es cierta, por que no es más que (3). Sólo me queda demostrar la segunda desigualdad,

$$2n \ge n+1 \Longrightarrow n \ge 1 \ .$$

Como n es mayor (o igual) a 1, entonces este eslabón de la cadena también es cierto. En resumen, ya hemos demostrado toda la cadena. De esa cadena, se deduce que la ecuación (2) es cierta. Eso completa la demostración.

[arreldepi]

Re: Demostración por inducción: 2^n&gt;n

Muchas Gracias!!!
La verdad es que ahora lo veo mucho más claro, he probado el otro y también me ha salido!

Gracias!

[ser humano]

Re: Demostración por inducción: 2^n&gt;n

Supongamos que A(n) es cierta. Fíjate que aquí n es un número natural cualquiera. Es un número fijo, pero puede ser cualquiera de ellos. Este A(n) no hay que demostrarlo, supongo que es cierto. Esto es lo que llamamos hipótesis.

una pregunta: si n es cualquiera ¿no podria ser a lo que consideramos n+1, tambien n? si fuese asi, ya con la propia hipotesis inductiva estariamos afirmando arbitrariamente que vale en todos los casos.

[pod]

Re: Demostración por inducción: 2^n&gt;n

una pregunta: si n es cualquiera ¿no podria ser a lo que consideramos n+1, tambien n? si fuese asi, ya con la propia hipotesis inductiva estariamos afirmando arbitrariamente que vale en todos los casos.

No, n es fijo pero arbitrario. Sólo uno.

Queremos demostrar que uno si uno cualquiera es cierto, el siguiente también lo es. Por lo tanto, elegimos uno (y sólo uno).