Principio di induzione
Un dubbio che mi è sorto quando mi sono trovato a voler dimostrare che la successione $a_n=q_n a_{n-1}+a_{n-2}$ è illimitata superiormente, dove i vari $q_n$ sono fissati e sono numeri naturali ($a_1 = 1$, $a_2=q_2$).
La mia idea è stata quella di procedere per induzione, definendo cioè l'insieme $E= \{n \in \mathbb{N} | a_n > n-2\}$, facendo vedere che $2 \in E$ e poi dimostrando che $n \in E \Rightarrow n+1 \in E$.
Innanzitutto, poiché la successione produce i suoi termini basandosi sui due precedenti, è necessario mostrare come punto di partenza che $2 \in E$, ma anche $3 \in E$, e questo si fa senza problemi.
Poi viene fuori il mio problema: per lo stesso motivo appena citato, non basta solo supporre che $n \in E$ per dimostrare che allora anche $n+1 \in E$, ma serve anche introdurre nelle ipotesi che $n-1 \in E$.
Questo mi crea qualche intoppo, perché non riesco bene a vedere se così facendo è corretto poi concludere che $E=\{2,3,4,...\}$ oppure è un errore logico.
Un aiutino, per favore?
La mia idea è stata quella di procedere per induzione, definendo cioè l'insieme $E= \{n \in \mathbb{N} | a_n > n-2\}$, facendo vedere che $2 \in E$ e poi dimostrando che $n \in E \Rightarrow n+1 \in E$.
Innanzitutto, poiché la successione produce i suoi termini basandosi sui due precedenti, è necessario mostrare come punto di partenza che $2 \in E$, ma anche $3 \in E$, e questo si fa senza problemi.
Poi viene fuori il mio problema: per lo stesso motivo appena citato, non basta solo supporre che $n \in E$ per dimostrare che allora anche $n+1 \in E$, ma serve anche introdurre nelle ipotesi che $n-1 \in E$.
Questo mi crea qualche intoppo, perché non riesco bene a vedere se così facendo è corretto poi concludere che $E=\{2,3,4,...\}$ oppure è un errore logico.
Un aiutino, per favore?
Risposte
Si funziona lo stesso:
\[ a_1 \in E \wedge a_2 \in E \Rightarrow a_3 \in E \]
\[ a_2 \in E \wedge a_3 \in E \Rightarrow a_4 \in E \]
e così via.
La tua proposizione è
\[ p(n) := \{ a_k \in E \quad \forall k \le n \} \]
La tua ipotesi di induzione è "$p(2)$ vera".
Devi mostrare che "$p(n)$ vera" implica "$p(n+1)$ vera".
\[ a_1 \in E \wedge a_2 \in E \Rightarrow a_3 \in E \]
\[ a_2 \in E \wedge a_3 \in E \Rightarrow a_4 \in E \]
e così via.
La tua proposizione è
\[ p(n) := \{ a_k \in E \quad \forall k \le n \} \]
La tua ipotesi di induzione è "$p(2)$ vera".
Devi mostrare che "$p(n)$ vera" implica "$p(n+1)$ vera".
Grazie della risposta.
Questa cosa non andrebbe dimostrata formalmente? E' questo che non riesco bene a capire come fare.
$\mathbb{N}$ lo definisco come il più piccolo sottoinsieme di $\mathbb{R}$ che sia induttivo e che contenga 1.
Quindi oltre alla classica implicazione:
$$(E \subset \mathbb{N}) \wedge (1 \in E) \wedge \left(n \in E \Rightarrow n+1\in E\right) \Rightarrow E=\mathbb{N}$$
vorrei dimostrare che:
$$(E \subset \mathbb{N}) \wedge (1 \in E) \wedge \left(n-1,n \in E \Rightarrow n+1\in E\right) \Rightarrow E=\mathbb{N}$$
magari sto facendo domande stupide ma vorrei capire come si affronta formalmente il problema.
PS: $E$ è un insieme di indici.
Questa cosa non andrebbe dimostrata formalmente? E' questo che non riesco bene a capire come fare.
$\mathbb{N}$ lo definisco come il più piccolo sottoinsieme di $\mathbb{R}$ che sia induttivo e che contenga 1.
Quindi oltre alla classica implicazione:
$$(E \subset \mathbb{N}) \wedge (1 \in E) \wedge \left(n \in E \Rightarrow n+1\in E\right) \Rightarrow E=\mathbb{N}$$
vorrei dimostrare che:
$$(E \subset \mathbb{N}) \wedge (1 \in E) \wedge \left(n-1,n \in E \Rightarrow n+1\in E\right) \Rightarrow E=\mathbb{N}$$
magari sto facendo domande stupide ma vorrei capire come si affronta formalmente il problema.
PS: $E$ è un insieme di indici.
Ma no, secondo me è molto più semplice di così. A parte che ho confuso la tua notazione e non ho visto che $E$ per te era un insieme di indici.
La versione che conosco io del principio di induzione è :
Se $P$ è una proprietà allora
\[ \Biggl [ P(n_0) \wedge (\forall n \ge n_0 )\biggl ( P(n) \Rightarrow P(n+1) \biggr ) \Biggr ] \Rightarrow \Biggl [ (\forall n \ge n_0 ) P(n) \Biggr ] \]
La tua $P(n)$ è :
\( (\forall k \le n ) \,\, a_k > k-2 \)
E quindi tutto funziona, cioè non importa quali indici coinvolge $P$, l'importante è che dipenda da $n$ e che funzioni l'implicazione \( (\forall n \ge n_0 )\biggl ( P(n) \Rightarrow P(n+1) \biggr ) \)
Usando la tua notazione (che probabilmente è più formale) credo sia sufficiente ridefinire $E$ come:
\[ E = \{ n \in \mathbb{N} : (\forall k \le n) \, \, a_k > k-2 \} \]
Dunque hai che $3 \in E$. Poi riesci a far vedere che $n \in E \Rightarrow n+1 \in E$. E così stai usando il classico principio di induzione, cioè mostri che $E$ è induttivo ed è un sottoinsieme dei naturali che implica che $E=\mathbb{N}$.
Ti torna?
In ogni caso io non so un acca di logica quindi, se vuoi risposte più approfondite/formali devi aspettare che passi qualcuno più esperto.
La versione che conosco io del principio di induzione è :
Se $P$ è una proprietà allora
\[ \Biggl [ P(n_0) \wedge (\forall n \ge n_0 )\biggl ( P(n) \Rightarrow P(n+1) \biggr ) \Biggr ] \Rightarrow \Biggl [ (\forall n \ge n_0 ) P(n) \Biggr ] \]
La tua $P(n)$ è :
\( (\forall k \le n ) \,\, a_k > k-2 \)
E quindi tutto funziona, cioè non importa quali indici coinvolge $P$, l'importante è che dipenda da $n$ e che funzioni l'implicazione \( (\forall n \ge n_0 )\biggl ( P(n) \Rightarrow P(n+1) \biggr ) \)
Usando la tua notazione (che probabilmente è più formale) credo sia sufficiente ridefinire $E$ come:
\[ E = \{ n \in \mathbb{N} : (\forall k \le n) \, \, a_k > k-2 \} \]
Dunque hai che $3 \in E$. Poi riesci a far vedere che $n \in E \Rightarrow n+1 \in E$. E così stai usando il classico principio di induzione, cioè mostri che $E$ è induttivo ed è un sottoinsieme dei naturali che implica che $E=\mathbb{N}$.
Ti torna?
In ogni caso io non so un acca di logica quindi, se vuoi risposte più approfondite/formali devi aspettare che passi qualcuno più esperto.
Sì, molto bello ed efficace il modo in cui hai ridefinito l'insieme.
Grazie Bremen000
Grazie Bremen000
Di nulla!
Ricordo che esiste anche una seconda forma del PIM, la quale a volte torna utile per gestire casi come questo.
Grande, bel post, grazie gugo
Direi che per dimostrare l'equivalenza tra le due, basta definire opportunamente \(\displaystyle E \) (o \(\displaystyle T \), nel tuo post) proprio come sopra.
Direi che per dimostrare l'equivalenza tra le due, basta definire opportunamente \(\displaystyle E \) (o \(\displaystyle T \), nel tuo post) proprio come sopra.
Sette anni fa scrivevo cose utili... 
Sì, Ianero, penso che la dimostrazione si possa fare facilmente seguendo lo spunto di Bremen000.
Sì, Ianero, penso che la dimostrazione si possa fare facilmente seguendo lo spunto di Bremen000.
Grazie ancora a entrambi, alla prossima domanda 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo