Guida per l'insegnante: Principio di induzione

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

Presenta lezioneVisualizza pagina studente

Usa questa lezione in classe

Gratis, senza account per gli studenti.

Condividi con gli studenti

Gli studenti aprono la lezione e si esercitano con correzione immediata.

Scheda da stampare

Tutti gli esercizi su carta, con le soluzioni a parte.

Scheda di esercizi Soluzioni

Quiz di classe

10 domande su Dimostrazioni matematiche. Gli studenti partecipano con un nome, tu vedi tutti i punteggi.

Per gli insegnanti

Obiettivi di apprendimento

Spiegare l'idea del domino alla base del principio di induzione
Scrivere passo base, ipotesi induttiva, passo induttivo e conclusione di una dimostrazione per induzione
Dimostrare per induzione formule delle somme, proprietà di divisibilità e disuguaglianze
Trovare e correggere gli errori in dimostrazioni per induzione sbagliate

Prerequisiti

• Introduzione alle dimostrazioni matematiche: che cos'è una dimostrazione
• Dimostrazione diretta: dimostrare enunciati a partire dalle definizioni
• Sviluppare e scomporre espressioni come $(k+1)^2$ e $(k+1)^3$
• Calcolare con le potenze, per esempio $2 \cdot 2^k = 2^{k+1}$

Spunti di discussione

1. Se sai che la prima tessera cade e che ogni tessera fa cadere la successiva, come sai che cade la tessera numero 1000?
2. Perché non basta controllare una formula per i primi 40 valori di n?
3. Che cosa andrebbe storto se saltassimo il passo base?
4. Ti viene in mente una situazione della vita quotidiana in cui un passo porta sempre al successivo?

Idee sbagliate comuni

Supporre $P(k)$ significa supporre ciò che vogliamo dimostrare

Rimedio: Sottolinea che supponiamo $P(k)$ solo per UN valore, per mostrare il collegamento tra $k$ e $k+1$ . È il passo base che fa partire la catena. Usa il domino: supponiamo che una tessera cada solo per controllare che colpisca la successiva.

Il passo base è una formalità che si può saltare

Rimedio: Mostra l'affermazione falsa $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ . Il suo passo induttivo funziona perfettamente, ma il passo base fallisce, quindi l'affermazione è falsa per ogni $n$ .

Controllare diversi valori dimostra una formula

Rimedio: Usa $n^2 + n + 41$ , che è primo per $n$ da $0$ a $39$ ma vale $41^2$ per $n = 40$ . Gli schemi suggeriscono una formula, solo una dimostrazione la conferma.

Idee di differenziazione

Per studenti in difficoltà:

• Dare uno schema con quattro riquadri: passo base, ipotesi, passo induttivo, conclusione
• Prima dell'algebra, verificare $P(k)$ e $P(k+1)$ con i numeri, per esempio $k = 4$
• Cominciare solo con le formule delle somme, dove il termine successivo è facile da vedere

Per studenti a livello:

• Dimostrare la somma dei dispari e la somma delle potenze di 2 senza schema
• Trovare l'errore in tre dimostrazioni per induzione sbagliate
• Dimostrare che $n^3 - n$ è divisibile per $3$

Per studenti avanzati:

• Dimostrare $2^n > n^2$ per $n \ge 5$ e spiegare perché il passo base è $5$
• Dimostrare $1^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$
• Conoscere l'induzione forte e dimostrare che ogni intero $n \ge 2$ è un prodotto di numeri primi

Allineamento agli standard

MP3 (CCSS.MATH.PRACTICE.MP3)
Costruire argomentazioni valide e criticare il ragionamento degli altri
HSA-APR.C.4 (CCSS.MATH.CONTENT.HSA.APR.C.4)
Dimostrare identità polinomiali e usarle per descrivere relazioni numeriche
HSA-SSE.B.4 (CCSS.MATH.CONTENT.HSA.SSE.B.4)
Ricavare la formula della somma di una progressione geometrica finita e usarla per risolvere problemi

Risorse della lezione

visualVisualizzatore di successioni
Imposta il primo termine a 1 e la ragione a 2: la riga della somma mostra che i primi 8 numeri dispari danno 64, cioè 8 al quadrato
activityDimostrazione con il domino
Gli studenti dispongono una fila di tessere e provano cosa succede senza la prima spinta o con un buco nella fila
worksheetCompleta la dimostrazione per induzione
Cinque dimostrazioni per induzione a cui mancano passi base, ipotesi e passaggi algebrici

Contenuto della lezione

Tutto ciò che vedono gli studenti: definizione, esempi, errori comuni, applicazioni. Tocca per aprire.

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.

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$ .

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

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.

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.

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

Guida per l'insegnante: Principio di induzione

Usa questa lezione in classe

Per gli insegnanti

Per studenti in difficoltà:

Per studenti a livello:

Per studenti avanzati:

Contenuto della lezione

Definizione

Esempi svolti

Errori comuni

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