Dimostrazione per induzione

Joker87 · Messaggio da **Joker87** » 01 dic 2006, 15:08

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

pic88 · Messaggio da **pic88** » 01 dic 2006, 15:21

http://olimpiadi.ing.unipi.it/oliForum/ ... php?t=5702

Joker87 · Messaggio da **Joker87** » 01 dic 2006, 15:29

non sono stato chiaro. la dimostrazione la conosco, vorrei solo sapere se per tutte le dimostrazione per induzione ci sono dei passi da seguire.

per esempio, una volta sostituito n+1 in n, cosa devo fare uscire dall'espressione??
ci sono dei passi standard da seguire?

grazie

pic88 · Messaggio da **pic88** » 01 dic 2006, 15:56

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.

Joker87 · Messaggio da **Joker87** » 01 dic 2006, 16:12

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?

pic88 · Messaggio da **pic88** » 01 dic 2006, 16:33

deve uscire S(n+1)=(n+1)(n+2)/2
che, guarda caso, è la formula con n+1 al posto di n.

Joker87 · Messaggio da **Joker87** » 01 dic 2006, 16:34

ma per fare uscire quello che dici tu basta sostituire n+1 al posto della n.

però su internet e anche sui libri ho visto che fanno anche alcuni passsaggi.

pic88 · Messaggio da **pic88** » 01 dic 2006, 16:57

ti rispondo in mp, così evitiamo di intasare il forum

Joker87 · Messaggio da **Joker87** » 01 dic 2006, 16:59

salva90 · Messaggio da **salva90** » 01 dic 2006, 17:03

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

Joker87 · Messaggio da **Joker87** » 01 dic 2006, 17:07

ancora piu confuso.

ma io quando devo dimostrare che è vera per n+1 devo sostituire n+1 nella n oppure devo semplicemente aggiungerlo alla formula??

tu per esempio l'hai aggiunto.

e poi un altra cosa, queste regole sono sempre valide oppure ogni caso è un caso a sè?

Joker87 · Messaggio da **Joker87** » 04 dic 2006, 11:15

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

Ponnamperuma · Messaggio da **Ponnamperuma** » 04 dic 2006, 14:05

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.