Dimostrazioni per induzione
Immagina una fila infinita di tessere del domino. Se la prima cade e ogni tessera, cadendo, fa cadere la successiva, allora cadono tutte. Come si può essere sicuri che una formula valga per tutti i numeri naturali, se ne possiamo controllare solo qualcuno? Il principio di induzione risponde proprio a questa domanda.
L'idea: il domino
Considera la somma dei primi numeri dispari: $1 = 1$, $1+3 = 4$, $1+3+5 = 9$, $1+3+5+7=16$. Sembra che la somma dei primi $n$ dispari sia $n^2$. Ma controllare a mano non basta: ci sono infiniti valori di $n$.
Perché funziona: $P(n_0)$ è vera per il passo base; per il passo induttivo è vera $P(n_0+1)$, quindi $P(n_0+2)$, e così via, senza fine.
Verifica che la proposizione $P(n)$: «$2^n > n$» è vera per $n = 1, 2, 3$ e dimostrala per induzione per ogni $n \ge 1$.
Verifica che la proposizione $P(n)$: «$2^n > n$» è vera per $n = 1, 2, 3$ e dimostrala per induzione per ogni $n \ge 1$.
Dimostrare una formula per le somme
Il metodo ha sempre tre mosse: base, ipotesi induttiva, passo induttivo. Nel passo induttivo si parte dal lato di $P(n+1)$ e si usa l'ipotesi per ricondursi a $P(n)$.
Dimostra per induzione che, per ogni $n \ge 1$, vale: $1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$
Dimostra per induzione che, per ogni $n \ge 1$, vale:
$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$
Dimostra per induzione che, per ogni $n \ge 1$, vale: $1 + 3 + 5 + \dots + (2n-1) = n^2$
Dimostra per induzione che, per ogni $n \ge 1$, vale:
$1 + 3 + 5 + \dots + (2n-1) = n^2$
Dimostra per induzione che, per ogni $n \ge 1$: $1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$
Dimostra per induzione che, per ogni $n \ge 1$:
$1^2 + 2^2 + 3^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}$
Divisibilità e successioni per ricorrenza
L'induzione serve anche per la divisibilità. Il trucco: nel passo induttivo scrivi l'espressione per $n+1$ come «espressione per $n$ + un multiplo del divisore».
Per le successioni definite per ricorrenza si procede in due tempi: si calcolano i primi termini, si congettura una formula, poi la si dimostra per induzione.
Se la ricorrenza usa due termini precedenti ($a_{n+2}$ in funzione di $a_{n+1}$ e $a_n$), servono due passi base (due termini iniziali) e un'ipotesi induttiva su $P(n)$ e $P(n+1)$ insieme.
Dimostra per induzione che, per ogni $n \ge 1$, il numero $7^n - 1$ è divisibile per 6.
Dimostra per induzione che, per ogni $n \ge 1$, il numero $7^n - 1$ è divisibile per 6.
Una successione è definita per ricorrenza da $a_1 = 2$, $a_{n+1} = a_n + 2n + 2$. a) Calcola i primi cinque termini. b) Congettura una formula per $a_n$ e dimostrala per…
Una successione è definita per ricorrenza da $a_1 = 2$, $a_{n+1} = a_n + 2n + 2$.
- a) Calcola i primi cinque termini.
- b) Congettura una formula per $a_n$ e dimostrala per induzione.
Sia $a_n$ la successione definita da $a_1 = 1$, $a_2 = 3$, $a_{n+2} = 3a_{n+1} - 2a_n$. a) Calcola $a_3, a_4, a_5$. b) Dimostra per induzione (con ipotesi su due passi…
Sia $a_n$ la successione definita da $a_1 = 1$, $a_2 = 3$, $a_{n+2} = 3a_{n+1} - 2a_n$.
- a) Calcola $a_3, a_4, a_5$.
- b) Dimostra per induzione (con ipotesi su due passi precedenti) che $a_n = 2^n - 1$ per ogni $n \ge 1$.
Disuguaglianze e base diversa da 1
Con le disuguaglianze il passo induttivo richiede una catena di maggiorazioni. Inoltre il passo base può non essere $n=1$.
Prova ora $2^n>n^2$: per $n=1$ è vera ($2>1$), per $n=2$ è falsa ($4>4$ no), per $n=3$ è falsa ($8>9$ no), per $n=4$ è falsa ($16>16$ no), per $n=5$ è vera ($32>25$). Il passo base giusto è allora $n_0=5$, e il passo induttivo deve valere solo per $n\ge5$.
Dimostra per induzione che, per ogni $n \ge 5$, vale $2^n > n^2$. Spiega perché la proposizione è falsa per $n = 3$ e per $n = 4$ e perché il passo base deve essere…
Dimostra per induzione che, per ogni $n \ge 5$, vale $2^n > n^2$. Spiega perché la proposizione è falsa per $n = 3$ e per $n = 4$ e perché il passo base deve essere $n = 5$.
Dimostra per induzione la disuguaglianza di Bernoulli: per ogni numero reale $x \ge -1$ e per ogni intero $n \ge 1$, $(1+x)^n \ge 1 + nx$. Indica esplicitamente dove nel…
Dimostra per induzione la disuguaglianza di Bernoulli: per ogni numero reale $x \ge -1$ e per ogni intero $n \ge 1$,
$(1+x)^n \ge 1 + nx$.
Indica esplicitamente dove nel passo induttivo si usa l'ipotesi $x \ge -1$.
In sintesi
-
Per dimostrare $P(n)$ per ogni $n\ge n_0$: passo base ($P(n_0)$ vera) e passo induttivo ($P(n)\Rightarrow P(n+1)$).
-
Nel passo induttivo si parte da un membro di $P(n+1)$, si usa l'ipotesi induttiva e si arriva all'altro membro.
-
Per la divisibilità si scrive l'espressione per $n+1$ come espressione per $n$ più un multiplo del divisore.
-
Per le ricorrenze: prima i primi termini e la congettura, poi la dimostrazione; con due termini precedenti servono due passi base.
-
Il passo base può partire da un $n_0>1$; nelle disuguaglianze attenzione al segno dei fattori.
Vuoi tornare al domino iniziale? Base = la prima tessera cade; passo induttivo = ogni tessera fa cadere la successiva; conclusione = cadono tutte.