Dubbio amletico sull'induzione...
Salve a tutti, sono nuovo su questo forum.
Sto frequentando il primo anno di università e studiando il principio di induzione (che già avevo incontrato al liceo e che - sinceramente - penso di aver capito) mi sono trovato davanti a un dubbio grosso come una casa.
Purtroppo non ho ancora avuto modo di fare direttamente la domanda al mio professore - non so nemmeno se risponderebbe - quindi ho deciso di sfogare qui la mia frustrazione.
Ho fatto la stessa domanda a tanti miei compagni di corso ma loro mi hanno ripetuto quello che avrebbe potuto ripetermi chiunque senza mai convincermi davvero.
A quanto ho capito, il principio di induzione afferma che se un particolare proprietà risulta vera per il "primo" elemento di un insieme ordinato N e, supposta vera per n, risulta vera anche per n+1 allora la proprietà vale per tutti gli n>= al primo elemento.
Generalmente, dagli esercizi che ho svolto e dagli esempi che ho visto, per dimostrare un proprietà basta:
-verificarla per il primo elemento (ad esempio 0, 1, ma anche 4 se vale per n>=4);
-supporla vera per n;
-tentare di ricondurre l'uguaglianza alla forma in (n+1);
-verificare che sia corretta;
Se ad esempio voglio dimostrare : $ \sum_{k=1}^(n) k=(n(n+1))/2 $
-verifico per 1 : $ \sum_{k=1}^1 k=(1(1+1))/2=1 $
-suppongo vera per n : $ \sum_{k=1}^n k=(n(n+1))/2 $
-riconduco a n+1: $ \sum_{k=1}^(n+1) k =1+2+3+...+n+(n+1)= (n(n+1))/2 + (n+1)=(n^2+n)/2+(2(n+1))/2 = (n^2+3n+2)/2=((n+1)(n+2))/2 $
-verifico che sia corretta.
Ma, per quanto ne so, come verifico che sia corretta? La risposta che mi viene da pensare è che sia ovvio, dal momento che in $ ((n+1)(n+2))/2 $ posso raccogliere n+1 e ricondurmi a una forma uguale a quella che ho supposto vera. Ossia $ h=n+1 => \sum_{k=1}^(n+1) k=((n+1)(n+2))/2 = \sum_{k=1}^(h) k=(h(h+1))/2 $
Fin qua tutto chiaro (ma non chiarissimo l'ultimo passaggio).
Ora quello che mi chiedo io è, anziché tentare di ricondurre a n+1 l'espressione e poi sostituire con h *, non si potrebbe:
-verificare per 1 : $ \sum_{k=1}^1 k=(1(1+1))/2=1 $
-supporre vera l'espressione per n : $ \sum_{k=1}^n k=(n(n+1))/2 $
-scrivere $ \sum_{k=1}^(n+1) k =((n+1)(n+2))/2 $ e poi trovare un modo per dimostrare che è vera.
Ad esempio: $ \sum_{k=1}^(n+1) k =((n+1)(n+2))/2 $ è una uguaglianza che può essere ancora vera o falsa.
Sottraggo al primo membro $ \sum_{k=1}^n k $ e al secondo $ (n(n+1))/2 $ perché $ \sum_{k=1}^n k=(n(n+1))/2 $ è vera per "ipotesi" per cui $ \sum_{k=1}^(n+1) k - \sum_{k=1}^n k=((n+1)(n+2))/2 - (n(n+1))/2$ è ancora una frase che potrà essere vera o falsa (analogamente, $ x = 5 $ non cambia soluzione se aggiungo a primo membro 1 e a secondo membro 2-1 perché $ 1 = 2-1 $).
Da cui:
$ \sum_{k=1}^(n+1) k - \sum_{k=1}^n k=n+1 $ che è vera perché si tratta della differenza della sommatoria sino a n+1 e di quella sino a n (lo "stacco" tra le due è esattamente n+1).
Quello che mi chiedo io è... anche se non credo che questo secondo modo sia più veloce del primo, è anch'esso dimostrare la formula per n+1? E' anch'esso valido in una dimostrazione per induzione?
La maggior parte delle persone (anche l'assistente del professore) mi ha risposto che si tratta di una identità che non dimostra nulla: il fatto che non capisco è come questa non sia una dimostrazione dal momento che si eseguono alla lettera le istruzioni dell'induzione.
Cioè dimostro per n=1; suppongo per n; dimostro per n+1.
Scusate lo sproloquio, volevo esporre bene l'idea...spero che qualcuno mi possa illuminare. So che sembra una cavolata, ma il fatto è che nessuno capisce questo procedimento o peggio dice che sia una ovvietà
.
*(come penso si debba fare nell'ultimo passaggio (quello che non ho capito) che spesso viene dato sottinteso)
PS complimenti per il sistema di scrittura delle formule, è veramente comodissimo ! Io mi aspettavo di metterci una eternità a scrivere tutto il messaggio...
Sto frequentando il primo anno di università e studiando il principio di induzione (che già avevo incontrato al liceo e che - sinceramente - penso di aver capito) mi sono trovato davanti a un dubbio grosso come una casa.
Purtroppo non ho ancora avuto modo di fare direttamente la domanda al mio professore - non so nemmeno se risponderebbe - quindi ho deciso di sfogare qui la mia frustrazione.
Ho fatto la stessa domanda a tanti miei compagni di corso ma loro mi hanno ripetuto quello che avrebbe potuto ripetermi chiunque senza mai convincermi davvero.A quanto ho capito, il principio di induzione afferma che se un particolare proprietà risulta vera per il "primo" elemento di un insieme ordinato N e, supposta vera per n, risulta vera anche per n+1 allora la proprietà vale per tutti gli n>= al primo elemento.
Generalmente, dagli esercizi che ho svolto e dagli esempi che ho visto, per dimostrare un proprietà basta:
-verificarla per il primo elemento (ad esempio 0, 1, ma anche 4 se vale per n>=4);
-supporla vera per n;
-tentare di ricondurre l'uguaglianza alla forma in (n+1);
-verificare che sia corretta;
Se ad esempio voglio dimostrare : $ \sum_{k=1}^(n) k=(n(n+1))/2 $
-verifico per 1 : $ \sum_{k=1}^1 k=(1(1+1))/2=1 $
-suppongo vera per n : $ \sum_{k=1}^n k=(n(n+1))/2 $
-riconduco a n+1: $ \sum_{k=1}^(n+1) k =1+2+3+...+n+(n+1)= (n(n+1))/2 + (n+1)=(n^2+n)/2+(2(n+1))/2 = (n^2+3n+2)/2=((n+1)(n+2))/2 $
-verifico che sia corretta.
Ma, per quanto ne so, come verifico che sia corretta? La risposta che mi viene da pensare è che sia ovvio, dal momento che in $ ((n+1)(n+2))/2 $ posso raccogliere n+1 e ricondurmi a una forma uguale a quella che ho supposto vera. Ossia $ h=n+1 => \sum_{k=1}^(n+1) k=((n+1)(n+2))/2 = \sum_{k=1}^(h) k=(h(h+1))/2 $
Fin qua tutto chiaro (ma non chiarissimo l'ultimo passaggio).
Ora quello che mi chiedo io è, anziché tentare di ricondurre a n+1 l'espressione e poi sostituire con h *, non si potrebbe:
-verificare per 1 : $ \sum_{k=1}^1 k=(1(1+1))/2=1 $
-supporre vera l'espressione per n : $ \sum_{k=1}^n k=(n(n+1))/2 $
-scrivere $ \sum_{k=1}^(n+1) k =((n+1)(n+2))/2 $ e poi trovare un modo per dimostrare che è vera.
Ad esempio: $ \sum_{k=1}^(n+1) k =((n+1)(n+2))/2 $ è una uguaglianza che può essere ancora vera o falsa.
Sottraggo al primo membro $ \sum_{k=1}^n k $ e al secondo $ (n(n+1))/2 $ perché $ \sum_{k=1}^n k=(n(n+1))/2 $ è vera per "ipotesi" per cui $ \sum_{k=1}^(n+1) k - \sum_{k=1}^n k=((n+1)(n+2))/2 - (n(n+1))/2$ è ancora una frase che potrà essere vera o falsa (analogamente, $ x = 5 $ non cambia soluzione se aggiungo a primo membro 1 e a secondo membro 2-1 perché $ 1 = 2-1 $).
Da cui:
$ \sum_{k=1}^(n+1) k - \sum_{k=1}^n k=n+1 $ che è vera perché si tratta della differenza della sommatoria sino a n+1 e di quella sino a n (lo "stacco" tra le due è esattamente n+1).
Quello che mi chiedo io è... anche se non credo che questo secondo modo sia più veloce del primo, è anch'esso dimostrare la formula per n+1? E' anch'esso valido in una dimostrazione per induzione?
La maggior parte delle persone (anche l'assistente del professore) mi ha risposto che si tratta di una identità che non dimostra nulla: il fatto che non capisco è come questa non sia una dimostrazione dal momento che si eseguono alla lettera le istruzioni dell'induzione.
Cioè dimostro per n=1; suppongo per n; dimostro per n+1.
Scusate lo sproloquio, volevo esporre bene l'idea...spero che qualcuno mi possa illuminare. So che sembra una cavolata, ma il fatto è che nessuno capisce questo procedimento o peggio dice che sia una ovvietà
.*(come penso si debba fare nell'ultimo passaggio (quello che non ho capito) che spesso viene dato sottinteso)
PS complimenti per il sistema di scrittura delle formule, è veramente comodissimo ! Io mi aspettavo di metterci una eternità a scrivere tutto il messaggio...
Risposte
Guarda, il procedimento è giusto, ma il fatto è che tra la dimostrazione "vecchia" e la tua "nuova" non c'è differenza.... sono la stessa cosa rigirata in un altro modo.
il terzo punto come lo dimostri? Esattamente come ti hanno fatto vedere a lezione:
$\sum_{k=1}^{n+1}k=\sum_{k=1}^{n}k+(n+1)$ (questa non è un'uguaglianza che può essere vera o falsa. Questa è VERA)
$\sum_{k=1}^{n}k+(n+1)=\frac{n(n+1)}{2}+(n+1)$ (e anche questa è vera per ipotesi di induzione)
$\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1}}{2}=\frac{(n+1)(n+2)}{2}$ e con questo hai concluso.
Il procedimento che fai tu è del tutto equivalente.
È un po' come dire: "posto $x=5$ e $y=x+1$, dimostrare che $y=6$".
Nella "mia" dimostrazione i passaggi sono $y=x+1=5+1=6$, mentre nella "tua" dici:
$y=6$ (potrebbe essere vera o falsa)
$y-6=0$
$x+1-6=0$
$x-5=0$
$x=5$
che essendo vera allora era vera anche la prima
Io direi che sono la stessa dimostrazione....
"IlToro":
Ora quello che mi chiedo io è, anziché tentare di ricondurre a $n+1$ l'espressione e poi sostituire con $h$ *, non si potrebbe:
-verificare per $1$ : $\sum_{k=1}^1k=\frac{1(1+1)}{2}=1$
-supporre vera l'espressione per $n$ : $\sum_{k=1}^nk=\frac{n(n+1)}{2}$
-scrivere $\sum_{k=1}^{n+1}k=\frac{(n+1)(n+2)}{2}$ e poi trovare un modo per dimostrare che è vera.
il terzo punto come lo dimostri? Esattamente come ti hanno fatto vedere a lezione:
$\sum_{k=1}^{n+1}k=\sum_{k=1}^{n}k+(n+1)$ (questa non è un'uguaglianza che può essere vera o falsa. Questa è VERA)
$\sum_{k=1}^{n}k+(n+1)=\frac{n(n+1)}{2}+(n+1)$ (e anche questa è vera per ipotesi di induzione)
$\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1}}{2}=\frac{(n+1)(n+2)}{2}$ e con questo hai concluso.
Il procedimento che fai tu è del tutto equivalente.
È un po' come dire: "posto $x=5$ e $y=x+1$, dimostrare che $y=6$".
Nella "mia" dimostrazione i passaggi sono $y=x+1=5+1=6$, mentre nella "tua" dici:
$y=6$ (potrebbe essere vera o falsa)
$y-6=0$
$x+1-6=0$
$x-5=0$
$x=5$
che essendo vera allora era vera anche la prima
Io direi che sono la stessa dimostrazione....
Comunque, una precisazione:
un insieme ordinato NNon "un" insieme ordinato, deve per forza essere \(\mathbb N\), l'insieme dei numeri naturali. Per esempio, ovviamente, non vale su \(\mathbb R\), che pure è ordinato.
Wow, che velocità! Grazie mille per i messaggi!
Non c'è dubbio sul fatto che si tratti di due dimostrazioni equivalenti, se dimostrano la stessa cosa allora possono essere manipolate in modo da farle risultare equivalenti (La Palice insegna).
Quello di cui volevo essere certo è che il mio ragionamento non fosse una tautologia, una identità, che non dimostrasse nulla -
come molti mi hanno detto (anche gente che dovrebbe saperne più di me).
Detto questo:
io ho scritto:
$ \sum_{k=1}^(n+1) k =((n+1)(n+2))/2 $ NON è ancora dimostrata, credo.
Avrei potuto supporre vera anche $ \sum_{k=1}^(n) k =3n $ e poi scrivere $ \sum_{k=1}^(n+1) k =3(n+1) $, svolgere i calcoli alla stessa maniera ma otterrei che $ \sum_{k=1}^(n+1) k - \sum_{k=1}^n k=3 $, il che è falso.
Dopo aver scritto il primo messaggio ci ho pensato ancora un po' (non troppo, giuro) e sono giunto alla conclusione che nella dimostrazione "alternativa" si usano esattamente le stesse identiche proposizioni vere della dimostrazione standard ma in ordine inverso: la formula vera per ipotesi e lo sviluppo della successione (cioè che la (sommatoria fino a n+1) è uguale alla (sommatoria fino a n) + (n+1)).
Detto questo ho un'altra domanda per voi: può succedere applicando un ragionamento di questo tipo (sottrarre ecc.) di arrivare a enunciati sempre veri o a loro volta da dimostrare? Giusto una curiosità eh. Pensavo a cose del tipo n>=-1, o altre equazioni dimostrabili per via induttiva (cioè spostare la dimostrazione su un'altra dimostrazione più semplice)...sinceramente non ho ben chiaro neppure io di cosa sto parlando.
GRAZIE MILLE, questo forum è fantastico.
Non c'è dubbio sul fatto che si tratti di due dimostrazioni equivalenti, se dimostrano la stessa cosa allora possono essere manipolate in modo da farle risultare equivalenti (La Palice insegna).
Quello di cui volevo essere certo è che il mio ragionamento non fosse una tautologia, una identità, che non dimostrasse nulla -
come molti mi hanno detto (anche gente che dovrebbe saperne più di me).
Detto questo:
"billyballo2123":
$ \sum_{k=1}^{n+1}k=\sum_{k=1}^{n}k+(n+1) $ (questa non è un'uguaglianza che può essere vera o falsa. Questa è VERA)
io ho scritto:
"IlToro":
Ad esempio: $ \sum_{k=1}^(n+1) k =((n+1)(n+2))/2 $ è una uguaglianza che può essere ancora vera o falsa.
Sottraggo al primo membro $ \sum_{k=1}^n k $ e al secondo $ (n(n+1))/2 $ perché $ \sum_{k=1}^n k=(n(n+1))/2 $ è vera per "ipotesi" per cui $ \sum_{k=1}^(n+1) k - \sum_{k=1}^n k=((n+1)(n+2))/2 - (n(n+1))/2 $ è ancora una frase che potrà essere vera o falsa
$ \sum_{k=1}^(n+1) k =((n+1)(n+2))/2 $ NON è ancora dimostrata, credo.
Avrei potuto supporre vera anche $ \sum_{k=1}^(n) k =3n $ e poi scrivere $ \sum_{k=1}^(n+1) k =3(n+1) $, svolgere i calcoli alla stessa maniera ma otterrei che $ \sum_{k=1}^(n+1) k - \sum_{k=1}^n k=3 $, il che è falso.
Dopo aver scritto il primo messaggio ci ho pensato ancora un po' (non troppo, giuro) e sono giunto alla conclusione che nella dimostrazione "alternativa" si usano esattamente le stesse identiche proposizioni vere della dimostrazione standard ma in ordine inverso: la formula vera per ipotesi e lo sviluppo della successione (cioè che la (sommatoria fino a n+1) è uguale alla (sommatoria fino a n) + (n+1)).
Detto questo ho un'altra domanda per voi: può succedere applicando un ragionamento di questo tipo (sottrarre ecc.) di arrivare a enunciati sempre veri o a loro volta da dimostrare? Giusto una curiosità eh. Pensavo a cose del tipo n>=-1, o altre equazioni dimostrabili per via induttiva (cioè spostare la dimostrazione su un'altra dimostrazione più semplice)...sinceramente non ho ben chiaro neppure io di cosa sto parlando.
"dissonance":Giusto, ho scritto un perché non sapevo dove farlo cominciare (0, 1...), ma giusto così deve essere per forza N.
Comunque, una precisazione:
un insieme ordinato NNon "un" insieme ordinato, deve per forza essere \( \mathbb N \), l'insieme dei numeri naturali. Per esempio, ovviamente, non vale su \( \mathbb R \), che pure è ordinato.
GRAZIE MILLE, questo forum è fantastico.
"IlToro":
Non c'è dubbio sul fatto che si tratti di due dimostrazioni equivalenti, se dimostrano la stessa cosa allora possono essere manipolate in modo da farle risultare equivalenti (La Palice insegna).
Equivalenti nel senso che una non è meglio rispetto all'altra.
"IlToro":
...sinceramente non ho ben chiaro neppure io di cosa sto parlando.
ehm... io nemmeno
Quando si dimostra qualcosa per induzione va dimostrato il caso base, e poi la verità dell'implicazione $P(n)\Rightarrow P(n+1)$. Ma la verità di una implicazione è altra cosa dalla verità dell'implicando (ad esempio, se $p$ è falsa, $p \Rightarrow q$ è vera per ogni q).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo