Prueba $3^n > n^2$ por inducción

Question

Demostrar que %#% $ #%

Estoy usando inducción y entiendo que cuando $$3^n > n^2$ es true. La hipótesis de inducción es cuando $n=1$ % que $n=k$. Para el paso de inducción tenemos $3^k>k^2$ % que $n=k+1$que es igual a $3^{k+1} > (k+1)^2$. Sé que varios ambos lados de la hipótesis de inducción por $3\cdot3^k > k^2+2k+1$ pero no estoy seguro de qué hacer.

Answer 1

Vamos a dejar de lado el paso base, por el momento.

Supongamos que la desigualdad sostiene $n=k$; luego $ 3 $^ {k+1} = 3\cdot 3 ^ k > 3k^2=k^2+2k+1+2k^2-2k-1=(k+1)^2+(2k^2-2k-1) $$ la hipótesis de inducción se ha aplicado a la primera señal de $>$.

Tenemos tan pronto como $2k^2-2k-1>0$ $k\ge2$. De hecho, $2x^2-2x-1

Aquí el paso base es $n=2$, no $n=1$, pero por supuesto la desigualdad también tiene $n=1$.

Answer 2

$3^{n + 1} = 3 * 3^n > 3 n^2 > (n + 1)^2$ para suficientemente grande $n$. La hipótesis de que la $3^n > n^2$ es utilizado para la primera desigualdad, y probablemente te puedes imaginar lo "suficientemente grande $n$" es para el último paso.

El $3n^2 > (n + 1)^2$ la desigualdad podría parecer sospechoso. Una manera de ver que va a ser válida para suficientemente grande $n$ es considerar el orden de crecimiento de ambos lados de la desigualdad. Ambos lados son de segundo grado y, en particular, para suficientemente grande $n$, $n^2$ plazo de $(n + 1)^2 = n^2 + 2n + 1$ "dominar" a los otros términos. En ese momento tendremos $(n + 1)^2 = n^2 + 2n + 1\approx n^2 < 3n^2$, pero tal vez eso es un poco demasiado de la mano ondulado ahora. Otra manera de verlo es la nota que $3n^2 > (n + 1)^2$ es equivalente a $n^2 - 2n - 1 > 0$:

\begin{align} 3n^2 &> (n + 1)^2\\ 3n^2 - (n + 1)^2 &> 0\\ 3n^2 - 2n^2 - 2n - 1 &> 0\\ n^2 - 2n - 1 &> 0 \end{align}

y usted puede solucionar $n^2 - 2n - 1 > 0$ el uso de la ecuación cuadrática. Usted encontrará que $n > \frac{1}{2}(1+\sqrt{3})$ (o $n < \frac{1}{2}(1-\sqrt{3})$, pero la solución negativa no es relevante aquí). Desde $\frac{1}{2}(1+\sqrt{3})\approx 1.366<2$ el argumento que utiliza $3n^2>(n+1)^2$ aplica para $n = 2, 3,$ etc. Si, en cambio, se había descubierto que "lo suficientemente grande $n$" significaba $n > N \geq 2$ a continuación, se habría tenido que comprobar adicionales de la base de casos, $n = 2, 3, \ldots, N$ con el fin de completar la prueba.

Como un aparte, me da la impresión de que usted está pensando de la prueba por inducción como una especie de proceso mecánico: "La hipótesis de inducción es al $n=k$", "yo sé que usted se multiplican ambos lados de la hipótesis de inducción por $3$", etc. No tiene que ser tan mecánico. Por ejemplo, el aviso de que "$k$" ni siquiera aparece en los pasos anteriores. Esto no significó, como una crítica, sólo es algo a tener en cuenta cuando se desarrollan de sus habilidades.