¿Cuál es el propósito de la primera prueba en una prueba inductiva?

Question

Aprendizaje acerca de la prueba por inducción, supongo que el primer paso es siempre algo así como "la prueba de si la propuesta tiene por $n = \textrm{[the minimum value]}$"

Como este:

---

Demostrar que $1+2+3+...+n = \frac{n(n + 1)}{2}$ todos los $n \ge 1$.

La prueba de la $n = 1$:

$$n = \frac{n(n + 1)}{2} \implies 1 = \frac{2}{2}\textrm{, which holds.}$$

* El resto de la prueba aquí va *

---

Así que, yo lo hago todo el tiempo (como estándar). Pero nunca he pensado realmente acerca de por qué. ¿Por qué hago tal prueba? Puedo ver que si la prueba no se sostiene, no puede ser demostrado por inducción, supongo. Pero hay otra razón por la que hacemos esto?

Answer 1

Imagine un estanque con una infinita progresión lineal de hojas de nenúfar. Usted tiene una rana que, si él salta en un pad, que está garantizado para saltar a la siguiente. Si él salta en la primera almohadilla, él va a visitar a todos ellos. Pero si él nunca se hace la primera lilypad, todas las apuestas están apagadas.

Answer 2

Tenemos que probar el "caso base", porque de lo contrario nos podría "probar" cosas por inducción que no son verdad. Por ejemplo: vamos a "demostrar" que la suma de los primeros a $n$ números impares es impar. Ciertamente, si $S = 2+4+\cdots+2n$ es impar, entonces $2+4+\cdots+2n+(2n+2) = S + 2n+2$ también es extraño, ya que un número par, además de un número impar es impar.

Así por "inducción", la suma de los primeros a $n$ números impares es impar.

Por supuesto, esto es falso, y la razón de que tiene algo falso es que no hemos de comprobar que el caso base se conserva (no).

Answer 3

La inducción de la prueba es, en una metáfora, un juego de dominó. Su objetivo es hacer que las piezas caen, donde si el $n$th domino cae, lo hará el $(n+1)$pt. Sin embargo, si usted no derribar el principio de domino, ninguno podría caerse.

---

Un ejemplo de lo que va mal sin una adecuada base de caso...

Reclamo: Para todos los $n \in \Bbb{N}=\{1, 2, 3, ...\}$, $n \geq 1000$.

Prueba sin caso base: Si $n \geq 1000$$n+1 > n \geq 1000$.

---

Un ejemplo de lo que pasa totalmente equivocado...

Reclamo: Para todos los $n \in \Bbb{N}$, $n > n$.

Prueba sin caso base: Si $n > n$, y luego agregando $1$ a ambos lados vemos a $n+1>n+1$. Por lo tanto, por el fundamento de la inducción, hemos "probado" la reclamación.

Answer 4

Tomemos su ejemplo y modifica ligeramente:

Demostrar que $1+2+\cdots+n=\frac{n^2+n+1}{2}$ todos los $n\ge 1$.

Deje $P(n)$ ser la afirmación "$1+2+\cdots+n=\frac{n^2+n+1}{2}$". Entonces usted necesita mostrar que $P(n)$ implica $P(n+1)$. Sustituyendo $n+1$ $n$ nos encontramos con que $$ P(n+1) =\frac{n^2+3n+3}{2} $$ Ahora vamos a establecer el paso inductivo, es decir, que podemos utilizar $P(n)$ establecer $P(n+1)$. $$ \begin{align} 1+2+\cdots+n+(n+1) &=(1+2+\cdots+n)+(n+1)\\ &= \frac{n^2+n+1}{2}+(n+1)&\text{by the inductive hypothesis}\\ &= \frac{n^2+3n+3}{2}&\text{as required} \end{align} $$ Así que podemos concluir que el resaltado de la declaración. Tipo de. Excepto por el hecho de que $P(1)$, en el caso base, sinply no es cierto, ya que afirma que $$ 1=\frac{1^2+1+1}{2} $$ Como se ha señalado antes, si usted no puede conseguir la primera ficha de dominó para derrocar, ninguno de los demás se, tampoco.

Answer 5

Vamos a demostrar que todos los objetos del universo son del mismo color. Vamos a demostrar por inducción que, dado cualquier conjunto de $n$ objetos, todos ellos son del mismo color.

Inductivo paso: Dado un conjunto $\{1, ... n+1\}$ de los objetos, sabemos que $\{1, ... n\}$ son todos del mismo color $c_1$, $\{2, ... n+1\}$ son todos del mismo color $c_2$. Pero si $n\geq 2$ estos dos conjuntos se superponen, por lo $c_1$ $c_2$ debe ser el mismo. Por lo tanto, $\{1, ... n+1\}$ son todos del mismo color.

Caso Base: Si $n=1$, es obvio. Si $n=2$, entonces los dos elementos son del mismo color porque... er...

Caso Base de la izquierda como una prueba para el lector.