OliForum Matematico

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

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

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.

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?

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

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.

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

ok

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

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è?

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

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.