Principio di induzione forte
 

Principio di Induzione



Il principio di induzione verifica se un'affermazione goduta (apparentemente) da alcuni numeri naturali sia una proprietà valida in realtà per tutti i numeri naturali.


Principio di induzione



Il principio di induzione è uno strumento potente di dimostrazione di un'affermazione sui numeri naturali, in quanto stabilisce la verità di una proposizione per tutti i numeri naturali senza doverla verificare effettivamente per ogni numero naturale.


Il principio di induzione è equivalente al fatto che, dato un numero naturale qualunque , i suoi precedenti sono in un numero finito, quindi posso tornare a 0 in un numero finito di passi.


Data un'affermazione A su alcuni numeri naturali, il principio di induzione consta di due fasi:


  • Passo base: si controlla che l'affermazione A sia verificata per 0.


  • Passo induttivo: la proposizione A è vera per n implica che A sia vera per n + 1.


Se tali condizioni sono soddisfatte allora l'affermazione A è vera per qualunque numero naturale.



Vediamo esempi per discernere l'applicabilità del principio di induzione.


Esempio

Gli esempi sono visibili solo per gli utenti registrati
 
 
Registrati per vedere gli esempi »


Esempio

Gli esempi sono visibili solo per gli utenti registrati
 
 
Registrati per vedere gli esempi »


Mostriamo un esempio in cui verifichiamo per induzione.


Esempio

Gli esempi sono visibili solo per gli utenti registrati
 
 
Registrati per vedere gli esempi »


Principio di induzione forte



Prima di proseguire con altri esempi notiamo che vi sono affermazioni coinvolgenti non tutti i numeri naturali, ma che hanno significato da un certo numero naturale in poi e che quindi la versione che abbiamo esposto prima del principio di induzione ne è un caso particolare ().


In più in certe dimostrazioni si utilizzano spesso affermazioni vere intermedie necessarie alla verifica del passo induttivo, quindi - anche se appare più restrittivo - è comodo assumere al passo induttivo che un' affermazione sia vera anche per tutti i naturali precedenti a quello considerato.


Il principio di induzione in questa versione è equivalente al fatto che, dato un numero naturale qualunque, i suoi precedenti fino a sono in un numero finito, quindi posso tornare a in un numero finito di passi.


Il principio di induzione consta di due fasi:


  • Passo base: si controlla che l'affermazione A sia verificata per .


  • Passo induttivo: la proposizione A è vera per tutti i naturali implica che A sia vera per n + 1.


Se tali condizioni sono soddisfatte allora l'affermazione A è vera per qualunque numero naturale maggiore di



Vediamo alcuni esempi.


Esempio

Gli esempi sono visibili solo per gli utenti registrati
 
 
Registrati per vedere gli esempi »


Esempio

Gli esempi sono visibili solo per gli utenti registrati
 
 
Registrati per vedere gli esempi »


Principio di induzione per serie



Date due successioni , è possibile verificare se la seconda è la successione delle somme parziali della prima - chiamata anche ridotta n-esima - (il termine generale della seconda successione è la somma dei primi n termini della prima, ovvero ) applicando il principio di induzione.


  • Passo base: verificare che


  • Passo induttivo: si deve avere che


Vediamo un esempio.


Esempio

Gli esempi sono visibili solo per gli utenti registrati
 
 
Registrati per vedere gli esempi »

redattore del materiale didattico: Giuseppe Biasin