Dimostrazione per induzione
Dimostrazione per induzione
Allora, sto seguendo il corso di logica matematica e devo fare alcuni esercizi sull'induzione.
la teoria la so, ma quando faccio gli esercizi non so proprio i passaggi da fare.
per esempio dimostriamo la forumula Sn=(n(n+1))/2
io dimostro prima il passo base, cioè n=0 e quindi sostituisco 0 alla n e mi esce 0.
poi devo dimostrare n+1 o n-1??
quindi devo sostituire n+1 o n-1 al posto della n e poi che passaggi devo fare, cioè che risultato devo fare uscire?
grazie
la teoria la so, ma quando faccio gli esercizi non so proprio i passaggi da fare.
per esempio dimostriamo la forumula Sn=(n(n+1))/2
io dimostro prima il passo base, cioè n=0 e quindi sostituisco 0 alla n e mi esce 0.
poi devo dimostrare n+1 o n-1??
quindi devo sostituire n+1 o n-1 al posto della n e poi che passaggi devo fare, cioè che risultato devo fare uscire?
grazie
-
- Messaggi: 741
- Iscritto il: 16 apr 2006, 11:34
- Località: La terra, il cui produr di rose, le dié piacevol nome in greche voci...
dunque, tu hai una tesi da dimostrare, diciamo $ P(n) $.
Se devi dimostrarla per tutti i numeri naturali maggiori o uguali ad un certo numero $ n_0 $ allora devi:
1) dimostrare $ P(n_0) $
2) dimostrare $ P(r) \rightarrow P(r+1) $ per un r generico maggiore o uguale a n_0.
se fai ciò sei a posto.
ovviamente ci sono altri tipi di induzione, che prevedono come primo passo il "crearsi una base" (n_0), e poi, ad esempio, dimostrare:
2a) $ P(r) \rightarrow P(2r) $
2b) $ P(r) \rightarrow P(r-1) $
per un r generico maggiore di n_0.
il passaggio 2a assicura che da n_0 in poi, tutti i numeri del tipo $ n_02^n $ soddisfano la P. Il 2b è fondamentale per estendere la P a tutti i numeri. Se ad es hai dimostrato che la tesi vale per 2 e per tutte le potenze di 2, allora la tesi vale anche per un qualsiasi numero n: infatti c'è sicuramente una potenza di 2 maggiore di n (le potenze sono infinite) e se la tesi vale per quella potenza, grazie al 2b) vale anche per il numero che la precede, e così via fino ad n.
Se devi dimostrarla per tutti i numeri naturali maggiori o uguali ad un certo numero $ n_0 $ allora devi:
1) dimostrare $ P(n_0) $
2) dimostrare $ P(r) \rightarrow P(r+1) $ per un r generico maggiore o uguale a n_0.
se fai ciò sei a posto.
ovviamente ci sono altri tipi di induzione, che prevedono come primo passo il "crearsi una base" (n_0), e poi, ad esempio, dimostrare:
2a) $ P(r) \rightarrow P(2r) $
2b) $ P(r) \rightarrow P(r-1) $
per un r generico maggiore di n_0.
il passaggio 2a assicura che da n_0 in poi, tutti i numeri del tipo $ n_02^n $ soddisfano la P. Il 2b è fondamentale per estendere la P a tutti i numeri. Se ad es hai dimostrato che la tesi vale per 2 e per tutte le potenze di 2, allora la tesi vale anche per un qualsiasi numero n: infatti c'è sicuramente una potenza di 2 maggiore di n (le potenze sono infinite) e se la tesi vale per quella potenza, grazie al 2b) vale anche per il numero che la precede, e così via fino ad n.
mi spiego meglio
allora, prendiamo come esempio quella formula Sn=[n(n+1)]/2
il passo base è per n=0 ed esce 0, e qui ci siamo
poi il passo induttivo è n+1
quindi sostituisco n+1 in tutte le n della formula giusto??
a questo punto che devo fare? cioè cosa devo fare uscire da quella formula in cui ho sostituito n+1 nella n??
cioè come faccio a capire quando è il risultato finale?
allora, prendiamo come esempio quella formula Sn=[n(n+1)]/2
il passo base è per n=0 ed esce 0, e qui ci siamo
poi il passo induttivo è n+1
quindi sostituisco n+1 in tutte le n della formula giusto??
a questo punto che devo fare? cioè cosa devo fare uscire da quella formula in cui ho sostituito n+1 nella n??
cioè come faccio a capire quando è il risultato finale?
Proverò ad essere chiaro:
1-dimostri che per $ n=0 $ (o $ n=1 $, se preferisci) è vera
2-dimostri che se ipotizziamo che è vera per $ n $, allora è vera anche per $ n+1 $; per fare questo prendi la formula con $ n $, ci aggiungi $ n+1 $ e, sviluppando le operazioni, noti che viene esattamente la stessa formula con $ n+1 $ al posto di $ n $
Cioè:$ \displaystyle {\frac{n(n+1)}2+n+1}={\frac{n^2+n+2n+2}{2}}={\frac{(n+1)(n+2)}{2}} $
EDIT:scusate ma non avevo visto che nel frattempo avevano risposto
1-dimostri che per $ n=0 $ (o $ n=1 $, se preferisci) è vera
2-dimostri che se ipotizziamo che è vera per $ n $, allora è vera anche per $ n+1 $; per fare questo prendi la formula con $ n $, ci aggiungi $ n+1 $ e, sviluppando le operazioni, noti che viene esattamente la stessa formula con $ n+1 $ al posto di $ n $
Cioè:$ \displaystyle {\frac{n(n+1)}2+n+1}={\frac{n^2+n+2n+2}{2}}={\frac{(n+1)(n+2)}{2}} $
EDIT:scusate ma non avevo visto che nel frattempo avevano risposto
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
allora, ancora non riesco a capire come funziona la dimostrazione per induzione
io ho una formula da dimostrare, dimostro che è vera per il passo base, per esempio n=0, sostituisco lo 0 nella formula e vedo se è verificata. poi devo dimostrare che è vera per n+1.
per dimostrare questo come si fa?? si sostituisce n+1 in tutte le n della formula e poi come si continua??
non so proprio continuare praticamente, non so i passaggi da fare
aiutatemi grazie
io ho una formula da dimostrare, dimostro che è vera per il passo base, per esempio n=0, sostituisco lo 0 nella formula e vedo se è verificata. poi devo dimostrare che è vera per n+1.
per dimostrare questo come si fa?? si sostituisce n+1 in tutte le n della formula e poi come si continua??
non so proprio continuare praticamente, non so i passaggi da fare
aiutatemi grazie
- Ponnamperuma
- Messaggi: 411
- Iscritto il: 10 lug 2006, 11:47
- Località: Torino
Prendendo il tuo esempio...
1) Mostri banalmente per sostituzione che con 0 la cosa è verificata
2) Supponi sia vera la tesi per n. Vuoi ora vedere se ciò implica che la tesi valga anche per n+1. In realtà la scelta di n non è fondamentale, potresti prendere la coppia n-1 e n, o n+1 e n+2, diciamo che si tende a scegliere i valori che danno meno problemi di calcolo...
3) Hai finora supposto che valga $ 1+2+...+n=\frac{n(n+1)}{2} $.
Sommi ad ambo i membri n+1... l'uguaglianza ovviamente resta verificata... inoltre a primo membro hai quello che dice la tesi... resta da vedere se ciò che c'è a secondo membro è la stessa cosa della tesi scritto in modo diverso... in questo caso fai denominatore comune e verifichi quello che volevi trovare...
Tirando le somme, hai dimostrato che se la tesi vale per un numero n, allora vale anche per n+1.
Sapendo che vale per un caso-base, 0, deduci che vale per 1, se vale per 1 vale per 2, se vale per 2 vale per 3, e così via per tutti gli interi positivi. C.V.D.
1) Mostri banalmente per sostituzione che con 0 la cosa è verificata
2) Supponi sia vera la tesi per n. Vuoi ora vedere se ciò implica che la tesi valga anche per n+1. In realtà la scelta di n non è fondamentale, potresti prendere la coppia n-1 e n, o n+1 e n+2, diciamo che si tende a scegliere i valori che danno meno problemi di calcolo...
3) Hai finora supposto che valga $ 1+2+...+n=\frac{n(n+1)}{2} $.
Sommi ad ambo i membri n+1... l'uguaglianza ovviamente resta verificata... inoltre a primo membro hai quello che dice la tesi... resta da vedere se ciò che c'è a secondo membro è la stessa cosa della tesi scritto in modo diverso... in questo caso fai denominatore comune e verifichi quello che volevi trovare...
Tirando le somme, hai dimostrato che se la tesi vale per un numero n, allora vale anche per n+1.
Sapendo che vale per un caso-base, 0, deduci che vale per 1, se vale per 1 vale per 2, se vale per 2 vale per 3, e così via per tutti gli interi positivi. C.V.D.
La grandezza dell'uomo si misura in base a quel che cerca e all'insistenza con cui egli resta alla ricerca. - Martin Heidegger
MIND torna!! :D
MIND torna!! :D