Esempio guidato sul principio di induzione

Ciao a tutti . Sto cercando di capire il principio di induzione seguendo un esempio già svolto, ma non riesco ad arrivare fino alla fine. Questo è l'esercizio e ciò che ho capito fin'ora.

Testo: dimostriamo per induzione che per ogni n≥0.

Procedimento:

1) individuo

2) individuo l'affermazione

3) passo base: verifico se è vera -> -> vera dato che

4) passo induttivo: supponendo che sia vera, è vera anche

Fino a qui ci sono. Poi, il testo fa un passaggio che, leggendo la lezione presente su questo stesso sito, dovrebbe scrivere A(k+1) come A(k) + qualcosa, ma non riesco a capire i passaggi. Questa è la soluzione proposta:

.

Grazie in anticipo per un'eventuale risposta.

Ciao Narsil

Utilizzando il principio di induzione dobbiamo dimostrare che:

Seguiamo lo schema proposto dalla lezione di cui al link

(1) Base di induzione

Sostituiamo il valore iniziale all'interno della proprietà da verificare e vediamo cosa ne vien fuori:

, ed essendo la proprietà è verificata

Passo induttivo

Supponiamo che sia vera , cioè che valga e dimostriamo che sia vera anche (ottenuta sostituendo n+1 al posto di n nella nostra proprietà) cioè che vale:

Abbiamo così scritto . Cerchiamo ora di scrivere come più, meno, per, diviso "qualcosa"

Utilizzando le proprietà delle potenze:

Obiettivo raggiunto! Applichiamo ora l'ipotesi induttiva, per cui ed avremo:

Avendo così la tesi, in quanto siamo arrivati a dire che

cioè a dimostrare che è vera

Ora è chiaro? Se hai dubbi siamo qui

Innanzitutto grazie per la risposta .

Quando dici "applichiamo ora l'ipotesi induttiva", intendi che bisogna sostituire P(n) in P(n+1) scritto nella forma P(n) più, meno, per, diviso "qualcosa", giusto? Di conseguenza avremo:

fino a qui è corretto?

Non capisco come si arriva ad ottenere , che operazione hai fatto tra il passaggio precedente e questo?

Prova a rileggere con più calma e attenzione l'articolo che ti ho linkato

L'ipotesi induttiva in questo caso è:

quindi non appena trovo la vado ad applicare, proprio come hai fatto, anche se non è elegante scriverlo come lo hai scritto (fra quadre)

Per il resto mi sembra ovvio che

Stiamo aggiungendo una costante a due quantità: una e l'altra , quindi ai fini della maggiorazione non conta. Ora, fra e , con n che varia nei naturali, quale dei due è più grande?

Ho un dubbio su questo passaggio:

Una volta trovato che . E come se noi avessimo molteplicato .

Per questo si molteplica ?

Grazie!

Ciao Sabas

Mi raccomando a non perdere mai di vista cosa afferma il principio di induzione (a tal riguardo puoi leggere la lezione che trovi linkata nella mia prima risposta).

Ricapitolando:

dobbiamo dimostrare (per induzione su n) che:

Dopo aver dimostrato la proposizione per n=0 (base di induzione) ed aver supposto che sia vera (ipotesi induttiva), ovvero che valga:

dobbiamo dimostrare che sia vera anche , cioè che valga:

(ottenuta sostituendo in al posto di )

Come si fa?

Partiamo dalla prima parte della proposizione che dobbiamo dimostrare, ovvero da e dobbiamo cercare, in qualche modo, di far comparire un in modo da poter poi applicare l'ipotesi induttiva e cercare di giungere alla tesi.

In questo caso, ovviamente, per le proprietà delle potenze

Ed ecco che è venuto fuori, in questo modo, un che, per ipotesi induttiva sappiamo essere maggiore o uguale a . Ragion per cui possiamo scrivere:

Tutto qui