Principio di induzione
Ciao, chiedo aiuto per il suddetto teorema, oltre che da un punto di vista teorico anche da quello pratico perché non lo capisco e, di consequenza, proprio non lo so applicare.
Allora, il teorema cosa dice:
detto così sembra facile, ma tecnicamente non mi trovo: se è vera la seconda non stiamo già dicendo che P(n) è vera per ogni $n \ge n0$ ?? Infatti affinché si verifichi la seconda è necessario dimostrare che qualunque n scelgo P(n) sia vera ... quindi non mi spiego che c'entra la condizione P(n0) e P(n+1)... tanto più che essendo i numeri infiniti io non riuscirò mai a esplorare tutti i P(n) e P(n+1)...può darsi che arrivo fino a 100000 e funziona, che ne so che a 100001 non va più?
e poi l'applicazione pratica...ok dimostro la formula per P(n0), ma per dimostrare la seconda condizione come faccio??Insomma sto impazzendoT_T
Allora, il teorema cosa dice:
Sia $n_0 \ge 0$ un intero e sia P(n)
un predicato definito per ogni intero $n \ge n0$.
Supponiamo che siano veri cate le
seguenti due condizioni:
i) P(n0) è vero;
ii) per ogni $n \ge n_0$, se P(n) è vero allora P(n + 1) è vero.
Allora P(n) è vero per ogni $n \ge n0$.
detto così sembra facile, ma tecnicamente non mi trovo: se è vera la seconda non stiamo già dicendo che P(n) è vera per ogni $n \ge n0$ ?? Infatti affinché si verifichi la seconda è necessario dimostrare che qualunque n scelgo P(n) sia vera ... quindi non mi spiego che c'entra la condizione P(n0) e P(n+1)... tanto più che essendo i numeri infiniti io non riuscirò mai a esplorare tutti i P(n) e P(n+1)...può darsi che arrivo fino a 100000 e funziona, che ne so che a 100001 non va più?
e poi l'applicazione pratica...ok dimostro la formula per P(n0), ma per dimostrare la seconda condizione come faccio??Insomma sto impazzendoT_T
Risposte
[ Troppe 'o' nel titolo... non c'è bisogno di fare tutto 'sto chiasso 
]
Non so come mai, ma il principio di induzione sembra creare enormi difficoltà a chi lo affronta per la prima volta... eppure se leggi bene la definizione che hai dato, è semplicissimo. Hai una proposizione $P$:
- verifichi (o dimostri) che vale per un certo numero iniziale $n0$ (usualmente 0 o 1, ma qualunque numero ti serva e/o ti si richieda);
- poi, ipotizzando che valga per un qualunque numero $k>=n0$, dimostri che vale per il suo successivo $k+1$;
e in questo modo dimostri che vale per ogni numero maggiore od uguale a $n0$.
Trovi numerosi esempi sul web, per dirne uno
http://www.batmath.it/matematica/a_induz/induz.htm
]Non so come mai, ma il principio di induzione sembra creare enormi difficoltà a chi lo affronta per la prima volta... eppure se leggi bene la definizione che hai dato, è semplicissimo. Hai una proposizione $P$:
- verifichi (o dimostri) che vale per un certo numero iniziale $n0$ (usualmente 0 o 1, ma qualunque numero ti serva e/o ti si richieda);
- poi, ipotizzando che valga per un qualunque numero $k>=n0$, dimostri che vale per il suo successivo $k+1$;
e in questo modo dimostri che vale per ogni numero maggiore od uguale a $n0$.
Trovi numerosi esempi sul web, per dirne uno
http://www.batmath.it/matematica/a_induz/induz.htm
Grazie per aver risposto, davvero molto utile quel link anche se non del tutto chiarificatore...ti spiego il mio dubbio!
Lo spunto me lo da il tuo stesso link, nell'esercizio 2...viene dapprima dimostrato il passo induttivo e infatti si nota che, assumendo vera P(k), anche la proposizione P(k+1) è vera, subito dopo però viene dimostrato che per k=1 la proposizione non è più vera quindi la proposizione P non è vera per ogni n.
Viene detto che entrambi i passi devono essere fatti però ecco, mettiamo che ho un'altra generica proposizione da dimostrare!
Questa proposizione ad esempio è falsa se scelgo un n<5, da 5 in poi invece vale sempre.
Ora, io o perché voglio faticare o perché lo estraggo da un cappello, scelgo $n_0 = 6$!
Per questo valore la proposizione viene dimostrata, quindi passo al passo induttivo scegliendo un k qualsiasi maggiore di 6...e funziona!
Quindi concludo che per ogni n la proposizione è vera...FALSO!
Cosa c'è che non va nel mio esempio?Eppure è assolutamente lecito...
Inoltre eliminamo il generico k, voglio usare i numeri...supponiamo una proposizione vera per k= 3,4,5,6 falsa per gli altri n,
Scelgo $n_0 = 3$, vale. Scelgo un numero a caso maggiore di 3...5!Assumo sia vera, passo a 6...è vera...quindi posso dire che è vera per ogni n, FALSO ANCORA!
insomma ho l'impressione che il principio funzioni "azzeccando" i numeri giusti...
Lo spunto me lo da il tuo stesso link, nell'esercizio 2...viene dapprima dimostrato il passo induttivo e infatti si nota che, assumendo vera P(k), anche la proposizione P(k+1) è vera, subito dopo però viene dimostrato che per k=1 la proposizione non è più vera quindi la proposizione P non è vera per ogni n.
Viene detto che entrambi i passi devono essere fatti però ecco, mettiamo che ho un'altra generica proposizione da dimostrare!
Questa proposizione ad esempio è falsa se scelgo un n<5, da 5 in poi invece vale sempre.
Ora, io o perché voglio faticare o perché lo estraggo da un cappello, scelgo $n_0 = 6$!
Per questo valore la proposizione viene dimostrata, quindi passo al passo induttivo scegliendo un k qualsiasi maggiore di 6...e funziona!
Quindi concludo che per ogni n la proposizione è vera...FALSO!
Cosa c'è che non va nel mio esempio?Eppure è assolutamente lecito...
Inoltre eliminamo il generico k, voglio usare i numeri...supponiamo una proposizione vera per k= 3,4,5,6 falsa per gli altri n,
Scelgo $n_0 = 3$, vale. Scelgo un numero a caso maggiore di 3...5!Assumo sia vera, passo a 6...è vera...quindi posso dire che è vera per ogni n, FALSO ANCORA!
insomma ho l'impressione che il principio funzioni "azzeccando" i numeri giusti...
Sono il responsabile del link citato. Mi pare che l'esempio 2 preso dal mio sito sia ben chiarificatore di cosa sia il principio di induzione: solo se verifichi entrambi i passi, puoi concludere. Non è detto che il primo passo debba corrispondere a n=1: se parti da un valore più alto, vorrà dire che la proprietà è vera solo da quel valore in poi. Se guardi l'immagine che compare sulla prima pagina della sezione dedicata all'induzione vedrai che le caselline del domino cadono solo dalla terza in poi.
Spero che questo ti aiuti a capire questo principio fondamentale.
Caio e buono studio.
Luciano Battaia
Spero che questo ti aiuti a capire questo principio fondamentale.
Caio e buono studio.
Luciano Battaia
[OT]
@batmath: Se sei davvero il webmater di batmath, ti faccio i miei complimenti.
Alcune parti del vostro sito sono davvero ben fatte ed utili per gli studenti.
[/OT]
@batmath: Se sei davvero il webmater di batmath, ti faccio i miei complimenti.
Alcune parti del vostro sito sono davvero ben fatte ed utili per gli studenti.
[/OT]
prendendo spunto da questo thread, siccome ho problemi con l'induzione anche io ho dato una sbirciata :
non riesco a capire questo passaggio dell'esercizio 2 del sito batmath :
$ 1 + 2 .... + k + (k + 1) < 1/8 * (2k+1)^2 + (k+1) $
quì aggiunge $ (k+1) $ a primo e secondo membro, giusto ?
il passaggio successivo non riesco a capirlo :
$ 1/8 * (2k+3)^2 $
bhe ovviamente non riesco a capire neanche il successivo :
$ 1/8 * (2 (k+1) + 1)^2 $
mi fate capire un attimino ?
Da dove esce quel +3 ? e il k+1 dov'è finito?
non riesco a capire questo passaggio dell'esercizio 2 del sito batmath :
$ 1 + 2 .... + k + (k + 1) < 1/8 * (2k+1)^2 + (k+1) $
quì aggiunge $ (k+1) $ a primo e secondo membro, giusto ?
il passaggio successivo non riesco a capirlo :
$ 1/8 * (2k+3)^2 $
bhe ovviamente non riesco a capire neanche il successivo :
$ 1/8 * (2 (k+1) + 1)^2 $
mi fate capire un attimino ?
Da dove esce quel +3 ? e il k+1 dov'è finito?
$2(k+1)+1=2k+2+1=2k+3$.
Ah ecco, quindi se $n_0 != 0$ la proposizione è vera solo da quell' $n_0$ in poi...ok ora è tutto chiarissimo, grazie mille a entrambi! In effetti non era poi tanto difficile da capire 
Rispondo bene io a gamer, in effetti quella parte non è fatta molto chiara sul sito...allora tu devi dimostrare che vale
$1+2+...n \lt \frac{1}{8}*(2n+1)^2$ giusto?
Lo provi per 1 e funziona, passo iniziale verificato.
Per ipotesi induttiva
$1+2+...k \lt \frac{1}{8}*(2k+1)^2$ diciamo che è vera, dobbiamo provare per k+1, quindi abbiamo
$(1+2+...k) +(k+1) \lt \frac{1}{8}*(2(k+1)+1)^2$
(non aggiungiamo niente da entrambe le parti, semplicemente a sinistra consideriamo la somma di k+1 termini e a destra al posto di k mettiamo k+1)
Adesso bisogna ragionare un po...se $1+2+...k \lt \frac{1}{8}*(2k+1)^2$ è vera, allora a maggior ragione $(1+2+...k) +(k+1) \lt \frac{1}{8}*(2(k+1)+1)^2$ sarà vera perché a sinistra noi sommiamo $k+1$...ma a destra lo eleviamo al quadrato! Il termine di sinistra per aggiunte di k sale linearmente, ma quello a destra sale quadraticamente..molto più velocemente!
Se ancora non ti è chiaro per esempio considera
$3 \lt (2^2)=4$ differenza tra i 2 termini: 1
a sinistra sommi 1, a destra elevi (ciò che c'è + 1) per 2..se lo fai una volta
$(3+1)=4 \lt ((2+1)^2)=9$ differenza tra i 2 termini: 5
se lo fai 2 volte
$(3+1+1)=5 \lt (2+1+1)^2=16$ differenza tra i 2 termini: 11
insomma è ovvio che quello a destra diventa immensamente grande, mentre quello a sinsitra sale poco a poco...spero sia chiaro:)
Rispondo bene io a gamer, in effetti quella parte non è fatta molto chiara sul sito...allora tu devi dimostrare che vale
$1+2+...n \lt \frac{1}{8}*(2n+1)^2$ giusto?
Lo provi per 1 e funziona, passo iniziale verificato.
Per ipotesi induttiva
$1+2+...k \lt \frac{1}{8}*(2k+1)^2$ diciamo che è vera, dobbiamo provare per k+1, quindi abbiamo
$(1+2+...k) +(k+1) \lt \frac{1}{8}*(2(k+1)+1)^2$
(non aggiungiamo niente da entrambe le parti, semplicemente a sinistra consideriamo la somma di k+1 termini e a destra al posto di k mettiamo k+1)
Adesso bisogna ragionare un po...se $1+2+...k \lt \frac{1}{8}*(2k+1)^2$ è vera, allora a maggior ragione $(1+2+...k) +(k+1) \lt \frac{1}{8}*(2(k+1)+1)^2$ sarà vera perché a sinistra noi sommiamo $k+1$...ma a destra lo eleviamo al quadrato! Il termine di sinistra per aggiunte di k sale linearmente, ma quello a destra sale quadraticamente..molto più velocemente!
Se ancora non ti è chiaro per esempio considera
$3 \lt (2^2)=4$ differenza tra i 2 termini: 1
a sinistra sommi 1, a destra elevi (ciò che c'è + 1) per 2..se lo fai una volta
$(3+1)=4 \lt ((2+1)^2)=9$ differenza tra i 2 termini: 5
se lo fai 2 volte
$(3+1+1)=5 \lt (2+1+1)^2=16$ differenza tra i 2 termini: 11
insomma è ovvio che quello a destra diventa immensamente grande, mentre quello a sinsitra sale poco a poco...spero sia chiaro:)
"chester92":
Adesso bisogna ragionare un po...se $1+2+...+n \lt 1/8*(2n+1)^2$ è vera, allora a maggior ragione $(1+2+...+n) +(n+1) \lt 1/8*(2(n+1)+1)^2$ sarà vera perché a sinistra noi sommiamo $n+1$... ma a destra lo eleviamo al quadrato! Il termine di sinistra per aggiunte di $n$ sale linearmente, ma quello a destra sale quadraticamente... molto più velocemente!
Quando si applica il principio d'induzione non si ragiona asintoticamente, quindi considerazioni come quella evidenziata in grassetto non sono lecite in generale.
Quando si applica l'induzione, generalmente, si deve usare l'ipotesi induttiva (e qualche volta anche la base dell'induzione) per fare esplicitamente i calcoli.
Ad esempio in questo caso dobbiamo provare che sia vera la disuguaglianza:
(ITh) [tex]$\sum_{k=1}^{n+1} k \leq \frac{1}{8}\ [2(n+1)+1]^2$[/tex],
supponendo che sia vera la disuguaglianza:
(IHp) [tex]$\sum_{k=1}^{n} k \leq \frac{1}{8}\ [2n+1]^2$[/tex].
Come detto già da chester92, partiamo riscrivendo il primo membro di (ITh) come segue:
(1) [tex]$\sum_{k=1}^{n+1} k =\left( \sum_{k=1}^n k \right)+ (n+1)$[/tex]
(insomma, portiamo l'ultimo addendo fuori dalla sommatoria); per (IHp) possiamo maggiorare il secondo membro di (1) come segue:
(2) [tex]$\left( \sum_{k=1}^n k \right)+ (n+1) \leq \frac{1}{8}\ (2n+1)^2 + (n+1)$[/tex]
e poi facciamo un po' di conti sul secondo membro di (2) cercando di ottenere qualcosa di buono: ad esempio, facciamo un m.c.m. ed otteniamo:
[tex]$\frac{1}{8}\ (2n+1)^2 + (n+1) =\frac{1}{8}\ \left[ (2n+1)^2 +8(n+1)\right]^2 =\frac{1}{8}\ (4n^2+12n+9) =\frac{1}{8}\ (2n+3)^2$[/tex]
ossia:
(3) [tex]$\frac{1}{8}\ (2n+1)^2 + (n+1)=\frac{1}{8}\ [2(n+1)+1]^2$[/tex].
Mettendo insieme le (1), (2) e (3) abbiamo:
[tex]$\sum_{k=1}^{n+1} k \leq \frac{1}{8}\ [2(n+1)+1]^2$[/tex]
che è proprio la (ITh).
Ciao, grazie per avermi segnalato l'errore...in pratica non posso ragionare asintoticamente perché così "coprirei" i termini all'infinito ma non necessariamente quelli più piccoli giusto?
Cmq ottima spiegazione ^^
Cmq ottima spiegazione ^^
"chester92":
Ciao, grazie per avermi segnalato l'errore...in pratica non posso ragionare asintoticamente perché così "coprirei" i termini all'infinito ma non necessariamente quelli più piccoli giusto?
Esattamundo.
L'implicazione (IHp) [tex]$\Rightarrow$[/tex] (ITh) va verificata per ogni [tex]$n$[/tex] (a partire dal numero [tex]$n_0$[/tex] che per primo verifica la base dell'induzione) e non solo per [tex]$n$[/tex] "grandi".
"chester92":
Cmq ottima spiegazione ^^
Grazie.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo