Il passo base deve essere sempre n = 1?

No. Parti dal primo valore a partire dal quale l'enunciato deve valere. La somma delle potenze di 2 parte da $n = 0$. L'enunciato $2^n > n^2$ è falso per $n = 2, 3, 4$ (per esempio $2^4 = 16 = 4^2$) ed è vero per ogni $n \ge 5$, quindi quella dimostrazione usa il passo base $n = 5$.

Il principio di induzione è la stessa cosa del ragionamento induttivo delle scienze?

No. Il ragionamento induttivo intuisce una regola generale dagli esempi e può sbagliare. Il principio di induzione è una dimostrazione deduttiva: una volta dimostrati il passo base e il passo induttivo, il risultato è certo.

Che cos'è l'induzione forte?

Nell'induzione forte l'ipotesi suppone che $P(1), P(2), \dots, P(k)$ siano tutti veri, non solo $P(k)$. È utile quando $P(k+1)$ dipende da più casi precedenti, per esempio nelle dimostrazioni sulla scomposizione in fattori primi.

Risorse per insegnanti

Principio di induzione

Q: Perché l'induzione dimostra davvero l'enunciato per OGNI n?

Il passo base dà $P(1)$. Il passo induttivo con $k = 1$ dà $P(2)$, con $k = 2$ dà $P(3)$, e così via. Ogni intero positivo viene raggiunto dopo un numero finito di passi, quindi nessun $n$ resta escluso.

Impara a dimostrare enunciati per ogni intero positivo con il principio di induzione: passo base, ipotesi induttiva, passo induttivo e conclusione.

Avanzato30 minLezione

Scheda da stampare

Definizione

Il principio di induzione è un metodo di dimostrazione per enunciati che riguardano ogni intero positivo

n

(oppure ogni intero a partire da un valore iniziale). Chiamiamo l'enunciato

P(n)

. Invece di controllare infiniti casi uno per uno, dimostri soltanto due cose:

1.Passo base: $P(1)$ è vero.
2.Passo induttivo: per ogni $k \ge 1$ , se $P(k)$ è vero, allora anche $P(k+1)$ è vero. La supposizione " $P(k)$ è vero" si chiama ipotesi induttiva.

Insieme danno la conclusione:

P(n)

è vero per ogni

n \ge 1

P(1) \ \text{e} \ \big(P(k) \Rightarrow P(k+1)\big) \ \Longrightarrow \ P(n) \text{ per ogni } n \ge 1

Immagina una fila infinita di tessere del domino. Il passo base fa cadere la prima tessera. Il passo induttivo garantisce che ogni tessera che cade fa cadere la successiva. Quindi cadono tutte le tessere:

P(1)

, poi

P(2)

, poi

P(3)

, e così via senza fine.

Prova subito

Quali due parti deve contenere ogni dimostrazione per induzione?

Esempi svolti

Dimostra che $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ per ogni $n \ge 1$ .

Passo base: verifica $n = 1$

Membro sinistro: $1$ . Membro destro: $\dfrac{1 \cdot 2}{2} = 1$ → $P(1)$ è vero

Ipotesi induttiva: supponi $P(k)$ per un certo $k \ge 1$

Supponiamo che $1 + 2 + \dots + k = \dfrac{k(k+1)}{2}$ → Possiamo usare questa uguaglianza

Passo induttivo: aggiungi il termine successivo $k+1$ a entrambi i membri

$1 + \dots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2}$ → $= \dfrac{(k+1)(k+2)}{2}$

Confronta con $P(k+1)$

$P(k+1)$ afferma che la somma è uguale a $\dfrac{(k+1)\big((k+1)+1\big)}{2} = \dfrac{(k+1)(k+2)}{2}$ → $P(k+1)$ è vero

Risposta: Per induzione, $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ per ogni $n \ge 1$ . Per esempio, $1 + 2 + \dots + 100 = \dfrac{100 \cdot 101}{2} = 5050$ .

Errori comuni

Saltare il passo base

Perché è sbagliato: Il passo induttivo da solo non dimostra nulla: dice solo che SE cade una tessera, cade anche la successiva. Esempio: l'affermazione falsa $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ ha un passo induttivo che funziona, ma per $n = 1$ il membro sinistro è $1$ e quello destro è $2$ .

Corretto: Verifica sempre il primo caso in modo esplicito. Senza una prima tessera che cade, non cade niente.

Supporre ciò che vuoi dimostrare

Perché è sbagliato: Scrivere "supponiamo $P(n)$ vero per ogni $n$ " oppure "supponiamo $P(k+1)$ " è un ragionamento circolare: si suppone la tesi.

Corretto: Supponi $P(k)$ per UN valore $k$ (l'ipotesi induttiva) e dimostra $P(k+1)$ a partire da essa.

Algebra sbagliata nel passo induttivo

Perché è sbagliato: Una svista frequente è aggiungere il termine successivo sbagliato, per esempio $2k - 1$ invece di $2k + 1$ nella somma dei dispari, oppure dimenticare di aggiungere il nuovo termine in un membro.

Corretto: Scrivi prima $P(k+1)$ per intero (sostituisci ogni $n$ con $k+1$ ), poi lavora per arrivare esattamente a quell'espressione.

Credere che controllare molti casi sia una dimostrazione

Perché è sbagliato: L'espressione $n^2 + n + 41$ dà numeri primi per $n = 0, 1, \dots, 39$ , ma per $n = 40$ dà $1681 = 41^2$ , che non è primo.

Corretto: Gli esempi aiutano a intuire una formula. Solo il passo base insieme al passo induttivo la dimostrano per ogni $n$ .

Visuale interattivo

Esploratore di successioni

Primo termine (a₁ = 1)

Differenza comune (d = 2)

11,

13,

, ...

Formula

a_n = 1 + 2(n - 1) = 2n - 1

Formula della somma: S_8 = 8/2 × (2×1 + 7×2) = 64

Somme parziali

S₁ = 1S₂ = 4S₃ = 9S₄ = 16S₅ = 25S₆ = 36S₇ = 49S₈ = 64

a_1

a_5

a_10

a_20

Esploratore di successioni

Primo termine (a₁ = 1)

Rapporto comune (r = 2)

16,

32,

64,

128

, ...

Formula

a_n = 1 × 2^(n-1)

Formula della somma: S_8 = 1 × (1 - 2^8) / (1 - 2) = 255

Somme parziali

S₁ = 1S₂ = 3S₃ = 7S₄ = 15S₅ = 31S₆ = 63S₇ = 127S₈ = 255

|r| ≥ 1: le somme parziali non si avvicinano a nessun valore, quindi la serie infinita non ha somma.

a_1

a_5

a_10

512

a_20

524.288

Sandbox interattivo

Calcolatrice di espressioni

Prova questi:

Cronologia

Ancora nessun calcolo

Esercizi pratici

18 esercizi

Problema 1 di 18

Facile

Quali due parti deve contenere ogni dimostrazione per induzione?

Perché è importante

L'induzione è lo strumento principale per dimostrare risultati su infiniti casi:

Formule delle somme: puoi dimostrare che $1 + 2 + \dots + 100 = 5050$ deriva da una formula generale e non dal caso
Informatica: i programmatori dimostrano che i cicli e le funzioni ricorsive danno il risultato giusto per ogni dimensione dell'input
Schemi che sembrano veri: uno schema valido in 40 casi può fallire al caso 41; l'induzione ti dice quando uno schema vale davvero per sempre
Rompicapi e giochi: la Torre di Hanoi, i problemi di pavimentazione e molti esercizi delle gare si risolvono per induzione
Matematica superiore: quasi ogni area della matematica usa l'induzione da qualche parte

Nelle lezioni precedenti hai imparato le dimostrazioni dirette. L'induzione aggiunge un'idea nuova e potente: dimostra un solo passo e lascia che si ripeta all'infinito.

Applicazioni nel mondo reale

Verificare i programmi per computer

I programmatori usano l'induzione per dimostrare che un ciclo dà la risposta giusta dopo qualsiasi numero di giri: se è giusta dopo $k$ giri, è giusta anche dopo $k+1$ giri.

Esempio:

Un ciclo aggiunge $1, 2, 3, \dots$ a un totale. L'induzione dimostra che dopo $n$ giri il totale è $\dfrac{n(n+1)}{2}$ .

1Provaci tu stesso

Un programma somma in un ciclo i numeri da $1$ a $100$ .

Quale totale stampa il programma?

Passo 1: Scrivi l'espressione matematica

Usa $\dfrac{n(n+1)}{2}$ con $n = 100$ :

La Torre di Hanoi

In questo rompicapo sposti una pila di dischi su un altro paletto, un disco alla volta, senza mai mettere un disco più grande sopra uno più piccolo. L'induzione dimostra che $n$ dischi richiedono $2^n - 1$ mosse.

Esempio:

Per spostare $k+1$ dischi, sposti via i $k$ dischi in alto, poi il disco più grande, poi rimetti sopra i $k$ dischi: $2(2^k - 1) + 1 = 2^{k+1} - 1$ mosse.

2Provaci tu stesso

Una torre ha $6$ dischi. Spostare $5$ dischi richiede $31$ mosse.

Quante mosse servono per $6$ dischi?

Passo 1: Scrivi l'espressione matematica

Usa mosse per 6 dischi $= 2 \cdot$ (mosse per 5 dischi) $+ 1$ :

I chicchi di riso sulla scacchiera

Un'antica leggenda: metti $1$ chicco di riso sulla prima casella, $2$ sulla seconda, $4$ sulla terza, raddoppiando ogni volta. La somma delle potenze di 2 ti dà il totale.

Esempio:

Sulle prime $3$ caselle ci sono $1 + 2 + 4 = 7 = 2^3 - 1$ chicchi.

3Provaci tu stesso

Riempi le prime $10$ caselle. La casella $10$ contiene $2^9$ chicchi.

Quanti chicchi ci sono in tutto sulle prime $10$ caselle?

Passo 1: Scrivi l'espressione matematica

Usa $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ con $n = 9$ :

Punti chiave

1Il principio di induzione dimostra un enunciato $P(n)$ per ogni intero $n$ a partire da un valore iniziale
2Passo base: mostra che il primo caso, di solito $P(1)$ , è vero
3Ipotesi induttiva: supponi che $P(k)$ sia vero per un $k$ qualsiasi
4Passo induttivo: usa l'ipotesi per dimostrare $P(k+1)$
5Conclusione: come in una fila di tessere del domino, l'enunciato è vero per ogni $n$
6Servono entrambe le parti: un passo induttivo senza passo base, o qualche caso verificato senza passo induttivo, non dimostrano niente

Domande frequenti

Il passo base dà

P(1)

. Il passo induttivo con

k = 1

dà

P(2)

, con

k = 2

dà

P(3)

, e così via. Ogni intero positivo viene raggiunto dopo un numero finito di passi, quindi nessun

n

resta escluso.

Glossario

Principio di induzione: Un metodo di dimostrazione che prova $P(n)$ per ogni intero $n$ a partire da un valore iniziale, con un passo base e un passo induttivo
Passo base: Il primo caso dell'enunciato, di solito $P(1)$ , verificato direttamente
Ipotesi induttiva: La supposizione che $P(k)$ sia vero per un intero $k$ qualsiasi
Passo induttivo: La dimostrazione che $P(k)$ implica $P(k+1)$ per ogni $k$ a partire dal valore iniziale
P(n): L'enunciato che vogliamo dimostrare, scritto in funzione dell'intero $n$
Conclusione: La frase finale di una dimostrazione per induzione: $P(n)$ è vero per ogni $n$ a partire dal valore iniziale

Scheda formule

Principio di induzione

P(1) \text{ e } \big(P(k) \Rightarrow P(k+1)\big) \Rightarrow P(n) \text{ per ogni } n \ge 1

Passo base più passo induttivo dimostrano l'enunciato per ogni $n$

Somma dei primi n interi

1 + 2 + \dots + n = \dfrac{n(n+1)}{2}

Per $n = 5$: $15$

Somma dei primi n dispari

1 + 3 + \dots + (2n-1) = n^2

Per $n = 5$: $25$

Somma delle potenze di 2

1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1

Per $n = 6$: $127$

Altro su questo argomento

Definizione

Esempi svolti

Errori comuni

Visuale interattivo

Esploratore di successioni

Formula

Somme parziali

Esploratore di successioni

Formula

Somme parziali

Sandbox interattivo

Calcolatrice di espressioni

Cronologia

Esercizi pratici

Perché è importante

Applicazioni nel mondo reale

Verificare i programmi per computer

La Torre di Hanoi

I chicchi di riso sulla scacchiera

Punti chiave

Domande frequenti

Glossario

Scheda formule

Principio di induzione

Somma dei primi n interi

Somma dei primi n dispari

Somma delle potenze di 2

Altro su questo argomento

Introduzione alle dimostrazioni matematiche

Dimostrazione diretta

Dimostrazioni a due colonne

Dimostrazioni discorsive