Demostrar el principio de inducción fuerte

Question

Lo siguiente es de Analysis with an Introduction to Proof de Steven Lay

Demuestra el principio de inducción fuerte: Sea $P(n)$ sea una afirmación que sea verdadera o falsa para cada $n \in \mathbb{N}$ siempre que

$(a)$ $P(1)$ es verdadera, y

$(b)$ para cada $k \in \mathbb{N}$ Si $P(j)$ es verdadera para todos los enteros $j$ tal que 1 $\le$ $j$ $\le$ $k$ entonces $P(k+1)$ es cierto.

Prueba.

Definir $Q(n):=$ " $P(j)$ es cierto para 1 $\le$ $j$ $\le$ $n$ ."

Desde $(a)$ sabemos que $Q(1)$ se mantiene.

Además, sabemos que $Q(n)$ se mantiene ya que $P(j)$ es cierto para 1 $\le$ $j$ $\le$ $n$ . Así, por $(b)$ , $P(n+1)$ es cierto. De ello se desprende que $P(j)$ es cierto para 1 $\le$ $j$ $\le$ $(n+1)$ y así $Q(n+1)$ se mantiene.

Por lo tanto, hemos verificado el paso inductivo. Por lo tanto, $Q(n)$ es válida para todos los $n \in \mathbb{N}$ Q.E.D.

Me gustaría saber si la prueba que he proporcionado es suficiente y fluye lógicamente. Además, me gusta probar la inducción fuerte sin incorporar el Principio de Ordenamiento Bueno.

Answer 1

Algo está mal. Tu b) es el típico enunciado de la inducción fuerte, es decir, esto es lo que necesitas demostrar si quieres derivar la inducción fuerte de la inducción débil... y sin embargo en tu prueba te apoyas en b), por lo que la conviertes en una suposición.

Deberías ser más explícito en lo que supones y en lo que intentas demostrar.