El uso de la inducción para demostrar que un producto de sumas de cuadrados es una suma de cuadrados

Question

Para cualquier número natural $n\ge 1$, dado pares de $(a_1,b_1),(a_2,b_2),...,(a_n,b_n)$ de los números enteros, existen número entero $c$ $d$ tal que

$$\prod_{i=1}^{n}(a_i^2+b_i^2) = c^2+d^2$$

---

Mi planteamiento inicial es

Caso Base: $(a_1^2+b_1^2) = a_1^2+b_1^2$, lo cual es cierto. (Aunque es trivial)

Demostrar que la afirmación es verdadera cuando $n=2$: Tenemos $$(a^2+b^2)(c^2+d^2) = (ac-bd)^2+(ad+bc)^2$$ (Gracias André Nicolas para señalarla)

Así que si $a,b,c,d$ son enteros, $ac,bd,ad,bc$ son todos los números enteros y números enteros está cerrado bajo la suma y la resta. Por lo tanto $(ac-bd),(ad+bc)$ son enteros.

Inductivo Hipótesis: $\prod_{i=1}^{n}(a_i^2+b_i^2) = c^2+d^2$ es cierto

Inductivo Paso: $$\prod_{i=1}^{n+1}(a_i^2+b_i^2) = \prod_{i=1}^{n}(a_i^2+b_i^2)\cdot (a_{n+1}^2+b_{n+1}^2) = (c^2+d^2)\cdot (a_{n+1}^2+b_{n+1}^2)$$ Donde $c$ $d$ son enteros.

Pero cuando se aplican $n=2$, $(c^2+d^2)\cdot (a_{n+1}^2+b_{n+1}^2) = (e^2 + f^2)$ donde $e$ $f$ son enteros.

Por lo tanto, por el principio de inducción, la declaración que necesitaba para demostrar que es cierto.

Answer 1

Permítanme plantear un par de puntos:

1. Usted debe demostrar la base de la inducción ($n=1$de los casos); incluso si es evidente, debe ser mencionado.

2. La inducción de la hipótesis de que usted pone adelante es sólo "Si el resultado se mantiene para $n$, entonces se cumple para $n+1$." Usted no asumiendo que el resultado se cumple para todos los valores de $n$, sólo por una sola, aunque no se especifica, el valor. Para el paso inductivo, para ser válidos, la prueba debe ser válida para cualquier valor de $n$ que usted puede utilizar. Que es: no tiene "general" y "casos específicos" de la hipótesis de inducción, se tiene una sola, fija, inducción, hipótesis: que el resultado vale para un particular, fijo (aunque sin especificar) $n$. Está tratando de demostrar una declaración universal ("Para todos los números naturales $n$, si el resultado se mantiene para $n$ entonces se mantiene para $n+1$") mediante la adopción de un arbitrario $n$.

3. Que es posible hacer el paso inductivo, asumiendo que el resultado se cumple para todos los valores de $k$ menor que $n$; esto a veces se llama "fuerte" o "inducción transfinita." Hay algunas diferencias sutiles entre la fuerte inducción aplicada a los números naturales y normales "de un-paso-en-un-tiempo" inducción: ver por ejemplo este post.

4. Aún así, inductivo argumento debe ser tal que debe mantener para todos los valores de $n$. Su argumento no deja de ir de$P(1)$$P(2)$.

   Una "prueba falsa" que me gusta parece especialmente apropiado aquí. Considere la siguiente instrucción:

   En cualquier finito no vacío grupo de personas, si al menos uno tiene los ojos azules, a continuación, todos ellos tienen ojos azules.

   Aquí está una "prueba" por inducción: supongamos $n$ el número de personas en el grupo. Ponemos a prueba la declaración por inducción.

   Base: $n=1$. Sólo hay una persona, y si esa persona tiene los ojos azules, a continuación, todas las personas tienen los ojos azules.

   Inducción de la hipótesis: En cualquier grupo con $n$ de la gente, si al menos uno tiene los ojos azules, todos ellos tienen los ojos azules.

   Inductivo paso: tener un grupo con $n+1$ de la gente, $p_1,p_2,\ldots,p_n,p_{n+1}$, y se supone que uno de ellos tiene los ojos azules. Sin pérdida de generalidad, dicen que es $p_1$. Así que tenemos el conjunto: $$\{ {\color{blue}p_1}, p_2,\ldots,p_n,p_{n+1}\}.$$ Considerar el conjunto de la primera $n$ personas: $\{{\color{blue}p_1},p_2,\ldots,p_n\}$. Por la hipótesis de inducción, ya que uno de ellos tiene los ojos azules, todos ellos tienen los ojos azules: $$\{ {\color{blue}p_1}, {\color{blue}p_2},\ldots,{\color{blue}p_n}, p_{n+1}\}.$$ Ahora consideremos el conjunto de los últimos $n$ personas que: $$\{{\color{blue}p_2},\ldots, {\color{blue}p_n}, p_{n+1}\}.$$ Dado que al menos uno tiene los ojos azules, todos ellos tienen los ojos azules: $$\{{\color{blue}p_2},\ldots, {\color{blue}p_n}, {\color{blue}p_{n+1}}\}.$$ Poniendo todo junto, tenemos: $$\{ {\color{blue}p_1}, {\color{blue}p_2},\ldots,{\color{blue}p_n}, {\color{blue}p_{n+1}}\}.$$ Por lo tanto, todos tienen los ojos azules. Por inducción, la declaración está probada.

   ¿Cuál es el error?

   El error es que el argumento inductivo no funciona al $n=1$. Hay que probar que el hecho de que $P(1)\implies P(2)$ , de alguna manera, y este argumento no funciona. (De hecho, este es el paso que no funciona, período, que es la razón por la afirmación es falsa...)

Así, su argumento es incompleto, incluso si se reformuló de manera apropiada, debido a que (i) le falta la base; y (ii) el argumento inductivo no trabajo para ir de $n=1$$n=2$.

De hecho, la base es trivial; el verdadero punto de fricción es la $n=2$ de los casos. Si usted sabe el $n=2$ de los casos es cierto, entonces usted puede también utilizar para reemplazar el problema paso en su "inducción argumento": eliminar el paso donde reclaman la conclusión sigue, ya que "es sólo un caso especial de la inducción de la hipótesis" (que es un argumento no válido como dado), y reemplazarlo con "desde el $n=2$ de los casos es cierto, entonces..."

Eso significa que, después de añadir que el $n=1$ de los casos es inmediata y la fijación de su inductivo argumento anterior:

Si usted puede probar que el $n=2$ caso directamente, entonces usted va a hacer.

Así que... intenta demostrar la $n=2$ de los casos. Si el $n=2$ de los casos funciona, entonces usted puede invocar la $n=2$ de los casos en su paso inductivo (que estaría bien) en lugar de cometer el error de hablar de "casos especiales" de la hipótesis inductiva.

Answer 2

La siguiente identidad es útil: $$(a^2+b^2)(x^2+y^2)=(ax\pm by)^2 + (ay \mp bx)^2.\qquad\qquad(\ast)$$ Esta identidad está conectado con la multiplicación de números complejos. Tenga en cuenta que $$(a+ib)(x+iy)=ax-by+i(ay+bx).$$ La identidad de $(\ast)$ puede ser pensado como la afirmación de que el producto de las normas de $a+ib$$x+iy$, es decir,$\sqrt{(x^2+y^2)(a^2+b^2)}$, es igual a la norma de su producto, es decir,$\sqrt{(ax-by)^2 +(ay+bx)^2}$.

Answer 3

Esto es como Polya la famosa prueba de que todos los caballos tienen el mismo color (la metáfora de "caballo de un color diferente" es quizás menos conocido universalmente que formalmente, así que tal vez el nombre para que no funciona tan bien como antes?).

Es trivial si sólo hay un caballo: un caballo---uno de color.

Para $n+1$ caballos llamado $1,2,3,4,\ldots,n,n+1$ vistazo a los conjuntos de $\{1,2,3,\ldots,n\}$ sólo con $n$ caballos, y $\{2,3,4,\ldots,n,n+1\}$, también con sólo $n$ caballos. En cualquier conjunto de $n$ caballos, todos ellos tienen el mismo color, ya que es la hipótesis de inducción. Pero los dos conjuntos de superposición, de modo que sólo hay un color entre todos los $n+1$ caballos.

Un montón de pruebas por inducción son como este: Vacuously true si $n=1$; y la inducción paso es trivial, pero la inducción de paso no funciona al $n=1$, y que uno de los casos---que es verdad cuando $n=2$---es la parte difícil.

Answer 4

Sugerencia $\ $ Por inducción, cierre bajo binario de productos se extiende a cierre bajo $\rm\:n$-ary productos.

Teorema $\ $ Si $\rm\ S\subset \mathbb N\ $ $\rm\ s,s'\in S\ \Rightarrow s\:s'\in S\ $ $\rm\ s_1,\ldots,s_n \in S\ \Rightarrow\ s_1\cdots s_n\in S\:.$

Prueba de $\rm\,\ n=1\:$ claro. Asumir como hipótesis de inducción: todos los productos de $\rm\:n\:$ elementos de $\rm\:S\:$ $\rm\:S.\:$ Ahora una longitud de $\rm\:n\!+\!1\:$ producto $\rm\:s_1\cdots\: s_{n}\:s'\ $ factores como la longitud de la $\rm\:n\:$ producto $\rm\:s = s_1\cdots\:s_n\:$ veces $\rm\:s'.\:$ Por inducción $\rm\:s\in S.\:$ Por hipótesis, $\rm\:s,s'\in S\ \Rightarrow\ s\:s'\in S,\:$ probando así la inducción de paso. $\, $ QED

El ejercicio es simplemente el caso especial donde $\rm\:S = \mathbb N^2\! + \mathbb N^2,\:$ a que un binario producto tiraron de la multiplicativity de las normas de los enteros de Gauss (Brahmagupta–Fibonacci de identidad), generando que las sumas de cuadrados son cerrado bajo la multiplicación.