¿Es la inducción mejor que otros métodos de prueba?

Question

¿Es la inducción mejor que otros métodos de prueba?

inducción
Matemáticas
solución-verificación
teoría-de-números-elemental

Oscar Vernon

Entonces, me hicieron la siguiente pregunta en una tarea:

Dejar $a,b\in\mathbb{Z}$ y $m,n\in\mathbb{N}$ . Muestra esa $(a,b)=1\iff (a^n,b)=1$ , y también $(a,b)=1\iff (a^n,b^m)=1$ .

Y aquí está mi intento...

Prueba de $(a,b)=1\iff(a^n,b)=1$ .

$\implies)$ Suponer $(a,b)=1$ . Por lo tanto, existen $s,t\in\mathbb{Z}(as+bt=1)$ . Tenga en cuenta que $1^n=(as+bt)^n=1$ .

∴ \sum_{k = 0}^{norte} (\binom{norte}{k}) (a s)^{norte - k} (b t)^{k} = 1. ∴ a^{norte} (s^{norte}) + b (\sum_{k = 1}^{norte} (\binom{norte}{k}) (a s)^{norte - k} b^{k - 1} t^{k}) = 1.

$\therefore\sum_{k=0}^{n}{n\choose k}(as)^{n-k}(bt)^k=1.\\ \therefore a^n(s^n)+b\left(\sum_{k=1}^{n}{n\choose k}(as)^{n-k}{\space}b^{k-1}t^k\right)=1.$ Desde

1

$1$ es una combinación lineal de

a^{n}

$a^n$ y

b

$b$ , entonces

(a^{n}, b) = 1

$(a^n,b)=1$ .

$\impliedby)$ Suponer $(a^n,b)=1$ . Por lo tanto, existen $s,t\in\mathbb{Z}(a^ns+bt=1)$ . Entonces, $a(a^{n-1}s)+bt=1$ .

Desde $1$ es una combinación lineal de $a$ y $b$ , entonces $(a,b)=1$ .

Prueba de $(a,b)=1\iff(a^n,b^m)=1$ .

De la proposición anterior se sigue que $(a,b)=1\iff (a^n,b)=1$ .

Entonces, $(a^n,b)=(b,a^n)=1\iff (b^m,a^n)=1=(a^n,b^m)$ , haciendo uso de la proposición una vez más.

Ahora, tengo dos preguntas .

Primero: ¿es correcta esta prueba? por alguna razón, siento que debo usar la inducción para probar esto formalmente (la primera proposición). Además, siento que la segunda prueba solo se cumple cuando se prueba la primera proposición por inducción, pero no sé por qué (es solo una sensación).

Segundo: ¿es mejor la inducción? Si es así, ¿por qué? Siento que la primera prueba debería estar bien, pero al mismo tiempo, siento que estoy haciendo algo mal... que no estoy demostrando para todos los números naturales por no usar la inducción. Pero, de nuevo, usamos esta estrategia de "elegir un número arbitrario en un conjunto para demostrar que es cierto para todos los números en ese conjunto", así que no veo por qué no debería ser así .

No sé si me estoy expresando lo suficientemente claro con mis preguntas, pero lo dejaré así por ahora.

Alan

Hay un uso oculto de la inducción en el uso de la expansión binomial. Eso es lo que te permite probarlo para un arbitrario

n

$n$ sin usar explícitamente la inducción aquí, la inducción se usó para probar que la fórmula

Oscar Vernon

¿Podría elaborar? Además, ¿eso significa que ambas pruebas son correctas?

Alan

Quiero decir que estás usando un resultado previamente probado, la expansión de

(a s + b t)^{n}

$(as+bt)^n$ . Esa fórmula se prueba por inducción. No revisé el tuyo en detalle, pero está perfectamente bien no usar la inducción explícitamente si ya tienes un resultado anterior que es válido para todos.

n

$n$

Arbashn

+1 para una prueba que no he visto antes. La prueba goto asume factorización prima única en

Z

$\Bbb{Z}$ .

Oscar Vernon

@arbashn. ¡Gracias! Me tomó un tiempo dar con él.

Respuestas (2)

¿Es la inducción mejor que otros métodos de prueba?

Hay un uso oculto de la inducción en el uso de la expansión binomial. Eso es lo que te permite probarlo para un arbitrario $n$ sin usar explícitamente la inducción aquí, la inducción se usó para probar que la fórmula
¿Podría elaborar? Además, ¿eso significa que ambas pruebas son correctas?
Quiero decir que estás usando un resultado previamente probado, la expansión de $(as+bt)^n$ . Esa fórmula se prueba por inducción. No revisé el tuyo en detalle, pero está perfectamente bien no usar la inducción explícitamente si ya tienes un resultado anterior que es válido para todos. $n$
+1 para una prueba que no he visto antes. La prueba goto asume factorización prima única en $\Bbb{Z}$ .

Troposfera · Answer 1

Tus pruebas me parecen perfectamente buenas, y no hay nada en la segunda parte que requiera que la primera haya sido probada por inducción.

La inducción no es en sí misma una forma "mejor" de probar cosas. Hay dos factores diferentes que (cada uno a su manera) pueden hacer que se sienta así a veces:

Probablemente haya tenido ejercicios de tarea en los que se le pidió explícitamente que probara tal y cual por inducción y, por lo tanto, demostrarlo de otra manera fue una solución incorrecta para esa tarea . Sin embargo, eso se debe a que el objetivo de esos ejercicios no era realmente probar tal o cual cosa , sino darte la oportunidad de practicar la inducción . Esa tarea en particular se trataba más del viaje que del destino, pero nadie dice que debas permanecer en ese modo para siempre.
En un sentido fundamental, probar algo interesante sobre todos los números naturales necesita un argumento de inducción para estar presente en alguna parte . Eso es al menos cierto si se reduce todo a un argumento totalmente formal que descansa sobre una base convencional de las matemáticas, porque en esa base convencional, lo único que sabemos realmente sobre los números naturales por definición es que son el conjunto que las matemáticas la inducción funciona para!

Sin embargo, esto no significa que este uso subyacente de la inducción deba ser visible en la superficie de su prueba, o incluso que, en cierto sentido, sea "mejor" que lo sea. Una prueba que se basa en un resultado intermedio que demostraste previamente usando algún tipo de inducción, como el teorema del binomio, es tan buena como una en la que haces todo desde cero. De hecho, podría decirse que una prueba que usa conceptos conocidos (de una manera bien motivada) es estrictamente mejor que una que hace todo desde cero solo porque sí.

Espectro · Answer 2

Por lo que veo de su respuesta (no he intentado esa pregunta antes, pero desde una perspectiva de primera vista), supongo que su primera prueba es correcta (francamente, no verifiqué la segunda). Incluso soy un principiante, por lo que estaré listo para revisar la prueba un poco más tarde y decirles si realmente es correcta (tengo una clase a la que asistir, por lo que no prefiero tomarme a mí mismo para verificar esto ahora).

Ahora, a tu segunda pregunta: no necesitas pensar así. A medida que cambia el tipo de pregunta, tendrá que pensar en diferentes formas. Por ejemplo, para demostrar que la perpendicular de un punto a una línea es la distancia más corta entre ellos, se requiere usar el método de la contradicción. La razón por la que la inducción funciona es porque si la declaración dada para probar es realmente aplicable al dominio en el que actúa, entonces, de una forma u otra, llegará a la conclusión correcta de que la declaración se cumple en el dominio dado. Entonces, en general, el método de prueba depende del tipo de pregunta dada. Por ejemplo, en mi opinión, la forma más sencilla de demostrar que $\nexists p \in \mathbb{P} : p \mid \sqrt{n }, p \leq \sqrt{n}, n\in \mathbb{N} \implies n \in \mathbb{P}$ y eso $(a,b) = 1 \implies (a^n,b) = 1$ son completamente diferentes. Probablemente, lo primero se puede probar mediante inducción, pero hasta donde yo veo, el tipo de prueba depende de la pregunta.

¡Hey gracias! Por cierto, ¿cuál es tu primer ejemplo? Es $\mathbb{P}$ el conjunto de los números primos? Si es así, ¿no debería ser la conclusión $n=1$ ?
@OscarVernon, mi primer ejemplo es algo que aprendí en la escuela y finalmente logré escribir en mi cuaderno de teoría de números que guardo para uso privado (quiero decir, me estoy preparando para la PRMO en mi región). Es una prueba que se utiliza para determinar si un número es primo o no. Y si $\mathbb{P}$ es el conjunto de todos los números primos.
@OscarVernon por cierto, me has señalado un pequeño error de tipeo. Como ven, tenía prisa por terminar una clase, y gracias por dejarme notar mi paso en falso.

¿Es la inducción mejor que otros métodos de prueba?

Oscar Vernon

Alan

Oscar Vernon

Alan

Arbashn

Oscar Vernon

Respuestas (2)

Troposfera

Oscar Vernon

Espectro

Oscar Vernon

Espectro

Espectro

Demostración por inducción sobre los números de Fibonacci: demuestre que fn∣f2nfn∣f2nf_n\mid f_{2n}

¿Los productos consecutivos de la forma 2k−12k−12^k-1 son divisibles por el primero de esos productos consecutivos?

Una demostración no inductiva de una propiedad de los números naturales

Verificación de prueba: No existe ningún número primo más grande.

Usando números primos de Fermats para probar que hay infinitos números primos [duplicar]

Enteros mmm y nnn tales que 9|(m+2n+1)9|(m+2n+1)9|(m + 2n + 1) y 9|(5m+n)9|(5m+n)9| (5m + n)?

Puntuaciones alcanzables en un juego de dardos

Estoy tratando de aprender a probar por inducción.

La suma de las potencias nthnthn^{\text{th}} de las raíces de un polinomio mónico con coeficientes enteros es siempre un número entero

K-topología satisface el axioma de Hausdorff