Il principio di induzione

Insiemi numerici N, Z, Q, R, Principio di induzione

Home » Il principio di induzione

Il principio di induzione è un concetto fondamentale della Matematica.

Esso può essere paragonato alle tessere del domino: per assicurarsi che cadano tutte, basta spingere la prima (detto passo base) ed essere certi che, assumendo che una generica tessera cada, tale caduta implichi la caduta della successiva (detto passo induttivo).

In maniera analoga, per verificare che una proprietà sia valida per ogni numero naturale basta assicurarsi che lo $0$ , il primo numero naturale, ne goda (passo base) e che, assumendo la proprietà vera per un generico numero $n$ , ciò implichi la validità della proprietà per il numero successivo $n+1$ (passo induttivo).

Questo semplice e potente strumento consente di affrontare numerosi problemi dell’aritmetica.

In questo articolo presentiamo la forma semplice, generalizzata e forte del principio di induzione e ci dedichiamo soprattutto all’analisi di esempi applicativi: la formula per la somma dei primi numeri naturali, il rompicapo della torre di Hanoi, la disuguaglianza di Bernoulli e il Teorema Fondamentale dell’Aritmetica.

Se desideri approfondire la conoscenza di questo fondamentale strumento della Matematica, continua pure la lettura!

Autori e revisori

Leggi...

Autore: Daniele Fakhoury

Revisore: Valerio Brunetti.

Principio 1 (induzione). Sia $P(n)$ una proposizione sui numeri naturali, se

$P(0)$ è verificata (passo base);
$\forall n\in \mathbb{N}, \; P(n) \Rightarrow P(n+1)$ (passo induttivo).

allora $P(n)$ è vera $\forall n \in \mathbb{N}$ .

In altri termini, per dimostrare che una certa proposizione sui numeri naturali sempre è vera ( $P(n)$ è vera $\forall n \in \mathbb{N}$ ) è sufficiente dimostrare che

la proposizione è vera se poniamo $n = 0$ (il passo base);
data per vera $P(n)$ (ipotesi induttiva), riusciamo a dimostrare che la proposizione è vera anche per $n+1$ .

Per ricordare questo principio è utile pensare alla metafora di una infinità di tessere del domino disposte lungo una fila. La proposizione $P(n)$ in questo caso può essere formulata come “l’ennesima tessere del domino cade”. Invece di controllare ad una ad una se le tessere del domino cascano o meno (cosa che non possiamo fare perché sono infinite) ci basta osservare

se la prima tessera del domino è caduta (passo base);
e se (per ogni $n$ ) l’ $n$ -esima tessera cade (ipotesi induttiva), questa fa cadere l’ $(n+1)$ -esima tessera del domino.

Se queste due condizioni sono verificate, possiamo star certi che cadranno tutte le tessere del domino e possiamo dormire sereni senza doverle controllare tutte. Infatti, osservando che la prima cade (passo base), per ipotesi induttiva, sappiamo che la seconda cade (sappiamo che $P(n) \Rightarrow P(n+1)$ ), ma se la seconda cade allora…

Ma cosa succede se la prima tessera del domino non cade (non vale il passo base per $n=0$ )? Magari è incollata al pavimento, o magari le prime $5$ tessere sono troppo distanziate tra di loro e non è vero che far cadere la terza tessera fa cadere la quarta tessera. D’altro canto dalla quinta tessera in poi tutto funziona liscio come l’olio. Per questo motivo possiamo generalizzare il nostro principio facendo partire il nostro passo base da qualche $n_0$ che non sia necessariamente $1$ . Formalmente

Principio 2 (induzione generalizzato). Sia $P(n)$ una proposizione sui numeri naturali, se

$\exists n_0$ tale che $P(n_0)$ verificata (passo base);
$\forall n\in \mathbb{N},\; n\geq n_0 \; P(n) \Rightarrow P(n+1)$ (passo induttivo)

allora $P(n)$ è vera $\forall n \in \mathbb{N}, \; n\geq n_0$ .

In sostanza stiamo dicendo che non è necessario partire proprio dalla prima tessera del domino, ma se riusciamo a dimostrare che

se la $n_0-$ esima tessera del domino è caduta (passo base):
e se (per ogni $n \geq n_0$ ) l’ $n$ -esima tessera cade (ipotesi induttiva), questa fa cadere l’ $(n+1)$ -esima tessera del domino .

allora possiamo star certi che cadono tutte le tessere dalla $n_0$ -esima in poi. Sensato, vero?

Passiamo a qualche esempio più pratico, dando per un attimo per buone le operazioni tra numeri naturali che ci sono familiari da sempre e che andremo a formalizzare nella prossima sezione. Partiamo da un esempio classico, la dimostrazione per induzione della formula della somma dei primi $n$ numeri naturali. La leggenda vuole che il primo a trovare questa formula sia stato il principe dei Matematici, Gauss. Durante i suoi anni di scuola, si racconta, si trovò alle prese con un maestro sfaticato, che non avendo voglia di insegnare, chiese ai suoi alunni di calcolare la somma dei primi cento numeri naturali

$\sum_{i=1}^{100} i = 1 + 2 + 3 + \dots + 100$

Si dice che Gauss non solo riuscì a risolvere il problema in brevissimo tempo, ma riuscì a generalizzarlo per la somma dei primi $n$ numeri naturali, qualunque sia $n$ , e dunque non solo per $n=100$ .
L’idea è estremamente semplice ed elegante: basta notare che la somma del primo e dell’ultimo numero è $1 +100 =101$ (in generale $n+1$ ), ma anche sommando il secondo con il penultimo si ha $2 + 99 = 101$ (in generale n+1), e che accoppiando in questo modo, abbiamo esattamente 50 (n/2) somme, tutte pari a $101$ . Allora

$1 + 2 + 3 + \dots + 100 = \underbrace{101 + \dots + 101}_{\text{50 termini}} = 50(101).$

Assumendo per il momento che $n$ sia pari

$1 + 2 + 3 + \dots + n = \underbrace{(n+1) + \dots + (n+1) }_{\text{$n/2$ termini}}= \frac{n}{2}(n+1)= \frac{n(n+1) }{2}.$

Se $n$ è dispari, la dimostrazione delineata sopra si può facilmente adattare. Il procedimento presentato serve solo per prendere familiarità con il problema, ma non ha niente a che vedere con il principio di induzione, proviamo ora a ridimostrare questa proposizione utilizzando il principio di induzione.

Esercizio 3 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar).$ Dimostrare che la somma dei primi $n$ numeri naturali è $\dfrac{n(n+1)}{2}.$

Dimostrazione.

In questo esempio la proposizione $P(n)$ è

$\sum_{k=1}^n k = \frac{n(n+1) }{2}.$

come prima cosa possiamo provare a caso dei valori di $n$ per familiarizzarci con la proposizione e verificare che la formula è vera almeno per questi $n$ ; per esempio per $n=3$ abbiamo:

$1 +2 + 3 = \frac{3(3+1) }{2}.$

che è vero (6 = 6).

Passo base: A questo punto mostriamo che la proposizione è vera per $n_0=1$ (la prima tessera del domino cade):
$P(1): \sum_{k=1}^1 k = \frac{1(1+1) }{2}$

che è come dire che $1 = \frac{1(1+1) }{2} = 1$ è ovviamente verificata.
Passo induttivo:Assumiamo (ipotesi induttiva) che $P(n)$ sia vera cioè che
$\sum_{k=1}^n k = 1 + 2 + \dots + n = \frac{n(n+1) }{2}.$

e vogliamo dimostrare che $P(n + 1)$ è vera (cioè sostituendo $n+1$ al posto di $n$ )

$\sum_{k=1}^{n+1} k = 1 + 2 + \dots + n + (n+1) = \frac{(n + 1)(n+2) }{2}.$

D’altro canto $1 + 2 + \dots + n + (n+ 1) = (1 + 2 + \dots + n) + (n+1)$ e per ipotesi induttiva $1 + 2 + \dots + n = \frac{n(n+1) }{2}$ , allora:

$\begin{aligned} \sum_{k=1}^{n+1} k & = 1 + 2 + \dots + n + (n+1) = (1 + 2 + \dots + n) + (n+1) = \\ &= \frac{n(n+1) }{2} + n+1 = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n + 1)(n+2) }{2} \end{aligned}$

dove nell’ultimo passaggio abbiamo raccolto $(n+1)$ , concludendo la dimostrazione.

Come abbiamo visto l’idea fondamentale è

verificare il caso base;
partendo dal caso $n+1$ (quello che dobbiamo dimostrare), cercare di riscrivere $P(n+1)$ in termini di $P(n)$ , usare l’ipotesi induttiva, cioè la conoscenza di $P(n)$
concludere con dei calcoli.

Un altro esercizio interessante riguarda il rompicapo della torre di Hanoi che consiste nello spostare un certo numero di dischi di grandezza crescente su tre pioli. Il gioco inizia con tutti i dischi incolonnati su un paletto in ordine decrescente, in modo da formare un cono. Lo scopo del gioco è portare tutti i dischi su un paletto diverso, potendo spostare solo un disco alla volta e potendo mettere un disco solo su un altro disco più grande, mai su uno più piccolo.

Rendered by QuickLaTeX.com

Il gioco fu inventato nel 1883 dal matematico francese Édouard Lucas che diffuse il gioco sotto lo pseudonimo di N. Claus de Siam, mandarino del collegio di Li-Sou-Stian. La leggenda secondo la quale in un tempio indù alcuni monaci sono costantemente impegnati a spostare su tre colonne di diamante 64 dischi d’oro secondo le regole della Torre di Hanoi (a volte chiamata Torre di Brahmā), è stata inventata dalla ditta che per prima ha messo in commercio il rompicapo. La leggenda narra che quando i monaci completeranno il lavoro, il mondo finirà.

Per prendere confidenza con il gioco, nella Figura 1 possiamo vedere il gioco risolto per due dischi. Notiamo che il numero di mosse necessario è 3.
Nel prossimo esercizio dimostriamo che se la torre di Hanoi ha $n$ dischi il numero di mosse necessario per risolverlo è $2^n -1$ e che, in qualche senso, i leggendari monaci del tempio indù non avevano tutti i torti, la legge che descrive il numero di mosse necessarie a risolvere il rompicapo è esponenziale nel numero di dischi. Supponendo che siano monaci estremamente forzuti e che siano inverosimilmente in grado di spostare il massiccio disco d’oro da un paletto ad un altro in un secondo, per finire il gioco hanno bisogno
$(2^{64} - 1) \text{ s} \sim 2^{64} \text{ s} = 1.8446744 \cdot 10^{19}\text{ s} = 58494241501775744$ secoli.

Esercizio 4 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar).$ Il numero minimo di mosse per per risolvere la torre di Hanoi con $n$ dischi è

$2^n -1.$

Dimostrazione.

La dimostrazione è veramente semplice. Abbiamo gia verificato che per $n = 2$ ci vogliono veramente $2^2 -1 = 3$ mosse, prendendo confidenza con la formula.

Passo base: Anche in questo caso possiamo partire da $n_0 = 1$ ; per risolvere questo caso banale, basta spostare (con un unica mossa) l’unico disco a nostra disposizione in una qualunque altro paletto. Infatti per $n=1$ abbiamo $2^1 - 1 = 1$ .
Passo induttivo: Supponiamo ci vogliano almeno $2^n -1$ mosse per risolvere il problema con $n$ dischi e dimostriamo (sostituendo $n+1$ ) che ci vogliano $2^{n+1} -1$ mosse per risolvere il rompicapo con $n+1$ dischi.In effetti per risolvere il problema con $n+1$ dischi dobbiamo prima spostare $n$ dischi lasciando solo il disco più grande al suo posto. Una volta fatto questo basterà spostare il disco più grande su un nuovo paletto e finire rispostando i primi $n$ dischi più piccoli sopra di lui. In totale $2^n - 1$ mosse per spostare gli $n$ dischi tranne quello grande, 1 mossa per spostare quello grande su un nuovo paletto, e altre $2^n - 1$ mosse per spostare tutti i dischi sopra al disco grande.
$2^n - 1 + 1 + 2^n -1 = 2(2^n) - 1 = 2^{n+1} -1$

come volevasi dimostrare.

In alcuni casi non basta $P(n)$ per dimostrare $P(n+1)$ , ma abbiamo bisogno di dare per vera (ipotesi induttiva forte) che $P(h)$ sia vera per tutti gli $h$ più piccoli di $n$ . In altre parole, usando la metafora del domino, in alcuni casi non mi basta sapere che la precedente è caduta per poter dimostrare che l’ennesima tessera sia caduta, ma ho bisogno di sapere che tutte le precedenti siano cadute.
In questo caso ci viene in aiuto il principio di induzione forte:

Principio 5 (induzione forte generalizzato). Sia $P(n)$ una proposizione sui numeri naturali, se

$\exists n_0$ tale che $P(n_0)$ verificata (passo base):
$\forall h\in \mathbb{N},\; n_0 \leq h \leq n, \; \{P(h)\}_h \Rightarrow P(n+1)$ (passo induttivo)

allora $P(n)$ è vera $\forall n \in \mathbb{N}, \; n\geq n_0$ .

Come applicazione del principio di induzione forte diamo una dimostrazione del teorema fondamentale dell’aritmetica che tutti diamo per buono: ogni numero naturale maggiore di 2 può essere scritto come prodotto di numeri primi in maniera unica a meno dell’ordine dei fattori. Qui non dimostreremo l’unicità.

Esercizio 6 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$ (teorema fondamentale dell’aritmetica (esistenza)). Per ogni numero naturale $n\geq 2$ , esistono numeri primi $p_1, p_2, \dots, p_{d_n}$ tali che

$n = p_1 \cdot p_2 \cdots p_{d_n}.$

Dimostrazione.

Facciamo questa dimostrazione per induzione.

Passo base: il caso base è ovvio perché 2 stesso è un numero primo 2 = 2.
Passo induttivo: Assumiamo che tutti i numeri $h$ con $2 \leq h \leq n$ si scrivano come prodotto di numeri primi. Vogliamo dimostrare che $n+1$ si scrive come prodotto di numeri primi. Se $n+1$ è un numero primo, così come nel passo base, non c’è nulla da dimostrare; $n+1= n+1$ è la fattorizzazione di $n+1$ in numeri primi. Nel caso $n+1$ non sia primo allora deve esistere un numero primo $p$ che lo divide: sia $h = \frac{n+1}{p}$ . Ovviamente $2\leq h \leq n$ per cui per $h$ vale l’ipotesi induttiva e dunque si scriverà come prodotto di numeri primi
$h = p_1 \cdot p_2 \cdots p_{d_h}$

a questo punto abbiamo concluso. Infatti

$n + 1 = p \cdot h = p \cdot p_1 \cdot p_2 \cdots p_{d_h}$

in altri termini grazie ad $h$ siamo riusciti a scrivere $n$ come prodotto di numeri primi.

Di seguito una serie di esercizi per prendere manualità nella tecnica di dimostrazione tramite principio di induzione.

Esercizio 7 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar)$ (disuguaglianza di Bernoulli). Dimostrare che

$\begin{equation*} (1+x)^n\geq 1+nx\qquad\forall\,n\geq 0,\,x>-1. \end{equation*}$

Dimostrazione.

Passo base: Per $n=0$
$(1+x)^0=1\geq 1+0\cdot x$
Passo induttivo: Riscriviamo per semplicità l’ipotesi induttiva

(1) $\begin{equation*} (1+x)^n\geq 1+nx \end{equation*}$

Allora

$\begin{equation*} \begin{split} (1+x)^{n+1}&=(1+x)^n\cdot (1+x)\geq(1+nx)\cdot(1+x)=\\&=1+x+nx+nx^2\geq\\&\geq 1+x+nx=1+(n+1)x \end{split} \end{equation*}$

dove l’ultima disuguaglianza è verificata perché $nx^2\geq 0$ .

Definizione 8. Si chiama fattoriale di un numero naturale $n$ la quantità

$\begin{equation*} n!= \begin{cases} 1&\text{ se } n=0;\\ n(n-1)!&\text{ se } n\neq 0. \end{cases} \end{equation*}$

Osservazione 9. Dalla definizione ricorsiva di fattoriale

$\begin{equation*} n!=n\cdot (n-1)\cdot...\cdot 2\cdot 1 \end{equation*}$

ovvero è il prodotto del numero per tutti i suoi antecedenti.

Scarica la teoria

Ottieni il documento contenente la teoria del principio di induzione.

Esercizio 10 $(\bigstar\largewhitestar\largewhitestar\largewhitestar\largewhitestar).$ Dimostrare che

$\begin{equation*} 2^{n-1}\leq n!\qquad\forall\,n\geq 1. \end{equation*}$

Dimostrazione.

Passo base: per $n=1$
$\begin{equation*} 2^{1-1}=1= 1!. \end{equation*}$
Passo induttivo: Supponiamo vera l’ipotesi per $n$

(2) $\begin{equation*} 2^{n-1}\leq n! \end{equation*}$

e dimostriamo l’asserto per $n+1$ .

$\begin{equation*} 2^{n}=2^{n-1}\cdot 2\leq n!\cdot2\leq n!\cdot (n+1)=(n+1)! \end{equation*}$

dove l’ultima disuguaglianza è verificata per $n\geq 1$ .

Definzione 11. Siano $n$ e $k$ due numeri naturali tale che $k\leq n$ . Il textbf{coefficiente binomiale} è

$\begin{equation*} \binom{n}{k}=\frac{n!}{(n-k)!k!} \end{equation*}$

e si legge “coefficiente binomiale $n$ su $k$ ” oppure, quando evidente dal contesto, semplicemente “ $n$ su $k$ ”.

L’esercizio seguente è un risultato centrale nella teoria combinatoria.

Esercizio 12 $(\bigstar\bigstar\bigstar\largewhitestar\largewhitestar)$ (binomio di Newton). Dimostrare

$\begin{equation*} (a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k. \end{equation*}$

Dimostrazione.

Passo base: Per $n=0$
$\begin{equation*} (a+b)^0=1=\binom{0}{0}a^0b^0=1 \end{equation*}$
Passo induttivo: Supponiamo vera l’ipotesi per $n$

(3) $\begin{equation*} (a+b)^n=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k \end{equation*}$

e dimostriamo l’asserto per $n+1$ :

$\begin{equation*} \begin{split} (a+b)^{n+1}&=(a+b)^n\cdot(a+b)=\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k(a+b)=\\&=a\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k+b\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k=\\&=\sum_{k=0}^{n}\binom{n}{k}a^{n-k+1}b^k+\sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k+1} \end{split} \end{equation*}$

Osservazione 13.

Dalla prima sommatoria è possibile isolare il primo termine (per $k=0$ )

$\begin{equation*} \sum_{k=0}^{n}\binom{n}{k}a^{n-k+1}b^k=\binom{n}{0}a^{n+1}+\sum_{k=1}^{n}\binom{n}{k}a^{n-k+1}b^k=a^{n+1}+\sum_{k=1}^{n}\binom{n}{k}a^{n-k+1}b^k \end{equation*}$

Mentre la seconda può essere riscritta come

$\begin{equation*} \begin{split} \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k+1}&=\sum_{k=1}^{n+1}\binom{n}{k-1}a^{n-k+1}b^{k}=\sum_{k=1}^{n}\binom{n}{k-1}a^{n-k+1}b^{k}+\binom{n}{n}b^{n+1}=\\&=\sum_{k=1}^{n}\binom{n}{k-1}a^{n-k+1}b^{k}+b^{n+1}. \end{split} \end{equation*}$

Osservazione 14.

Vale la seguente relazione

(4) $\begin{equation*} \binom{n}{k}+\binom{n}{k-1}=\binom{n+1}{k} \end{equation*}$

per $1\leq k\leq n$ . Infatti, dopo una diretta applicazione della definizione questo equivale a verificare che

$\begin{equation*} \frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}=\frac{(n+1)!}{k!(n-k+1)!}. \end{equation*}$

Sviluppiamo la somma a sinistra sfruttando le fattorizzazioni $k!=k(k-1)!$ e $(n-k+1)!=(n-k+1)(n-k)!$ . Otteniamo

$\frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}=\frac{(n-k+1)n!+kn!}{k!(n-k+1)!}=\frac{(n-\cancel{k}+1+\cancel{k})n!}{k!(n-k+1)!}=\frac{(n+1)!}{k!(n-k+1)!}.$

In conclusione

$\begin{equation*} \begin{split} (a+b)^{n+1}&=a^{n+1}+\sum_{k=1}^{n}\binom{n}{k}a^{n-k+1}b^k+\sum_{k=1}^{n}\binom{n}{k-1}a^{n-k+1}b^{k}+b^{n+1}=\\&=a^{n+1}+\sum_{k=1}^{n}\left(\binom{n}{k}+\binom{n}{k-1}\right)a^{n-k+1}b^{k}+b^{n+1}=\\&=a^{n+1}\sum_{k=1}^{n}\binom{n+1}{k}a^{n+1-k}b^{k}+b^{n+1}=\sum_{k=0}^{n+1}\binom{n+1}{k}a^{n+1-k}b^k \end{split} \end{equation*}$

che è esattamente la tesi per $n+1$ .

Esercizio 15 $(\bigstar\bigstar\largewhitestar\largewhitestar\largewhitestar).$ Dimostrare che un insieme $X$ di $n$ elementi possiede $2^n$ sottoinsiemi.

Dimostrazione.

Passo base: Per $n=1$ abbiamo $X=\{x\}$
$\begin{equation*} \mathcal{P}(X)=\{\emptyset,\{x\}\}\Rightarrow |\mathcal{P}(X)|=2. \end{equation*}$
Passo induttivo: Supponiamo $P(X)$ vera per ogni $k\leq n$ ovvero che ogni insieme di $k$ elementi abbia $2^k$ sottoinsiemi. Sia $Y$ un insieme di $k+1$ elementi e $y\in Y$ , allora $X:=Y\setminus\{y\}$ è un insieme con $k$ elementi. Pertanto i sottoinsiemi di $Y$ che non contengono $y$ sono $2^k$ . I sottoinsiemi di $Y$ che contengono l’elemento su cui abbiamo fissato l’attenzione sono della forma $\{y\}\cup A$ al variare di $A\subseteq X$ . In totale ci sono
$\begin{equation*} 2^k+2^k=2^k(1+1)=2^{k+1} \end{equation*}$

sottoinsiemi.

Il principio di induzione ci permette di concludere che la proposizione è vera per ogni $n\geq 1$ .

Quando si applica il principio di induzione bisogna stare particolarmente attenti. Di seguito mostriamo un’applicazione sbagliata del principio di induzione, che porta chiaramente a dimostrare un enunciato falso.

Esercizio 16 $(\bigstar\bigstar\bigstar\largewhitestar\largewhitestar).$ Dimostrare che $\forall n \in \mathbb{N}$ in un insieme di $n$ cavalli tutti hanno lo stesso colore.

Dimostrazione.

Partiamo subito dal caso base.

Passo base: per $n=1$ abbiamo un insieme composto da un unico cavallo. È ovvio che tutti i cavalli dell’insieme abbiano lo stesso colore.
Passo induttivo: assumiamo come ipotesi induttiva $P(n)$ , cioè assumiamo vero che se ho un insieme di $n$ cavalli questi devono avere tutti lo stesso colore. Cerchiamo di dimostrare che vale $P(n+1)$ cioè che anche per gli insiemi di $n+1$ cavalli, questi devono avere tutti lo stesso colore. Infatti dato un insieme di $n+1$ cavalli escludiamone uno a caso. Il sottoinsieme $A$ così generato è composto da $n$ cavalli e devono avere tutti lo stesso colore (per esempio sono tutti neri). Quindi sappiamo che tutti i cavalli tranne uno sono neri. Adesso partendo dal nostro sottoinsieme $A$ di cavalli (tutti dello stesso colore), creiamo un altro sottoinsieme $B$ togliendo un cavallo a caso da $A$ e rimettendo l’unico scartato in precedenza. Anche $B$ è un insieme di $n$ elementi con la maggior parte dei cavalli (quelli che erano sia in A che in B) neri.

Quindi tutti i cavalli devono essere neri in particolare anche quello che avevamo scartato in precedenza. Questo dimostra che tutti gli $n+1$ cavalli hanno lo stesso colore.

L’errore nella dimostrazione precedente è credere che esista sempre almeno un cavallo in $A \cap B$ infatti se $(n+1)=2$ i due insiemi sono creati sono formati da un solo cavallo e hanno intersezione vuota. Quindi non possiamo “trasferire” il colore di $A$ anche all’insieme $B$ . Infatti per il principio di induzione, nel passo induttivo, dobbiamo dimostrare che $P(n) \Rightarrow P(n+1)$ a prescindere dal valore di $n$ . Qui invece la dimostrazione perde di significato per $P(1) \Rightarrow P(2)$ .

Fonti: G.M. Piacentini Cattaneo, ALGEBRA, un approccio algoritmico, Decibel Zanichelli (1996).

Tutta la teoria di analisi matematica

Leggi...

Tutte le cartelle di Analisi Matematica

Leggi...

Tutti gli esercizi di geometria

In questa sezione vengono raccolti molti altri esercizi che coprono tutti gli argomenti di geometria proposti all’interno del sito con lo scopo di offrire al lettore la possibilità di approfondire e rinforzare le proprie competenze inerenti a tali argomenti.

Strutture algebriche.

Algebra lineare.

Geometria analitica.

Geometria differenziale.

Risorse didattiche aggiuntive per approfondire la matematica

Leggi...

Math Stack Exchange – Parte della rete Stack Exchange, questo sito è un forum di domande e risposte specificamente dedicato alla matematica. È una delle piattaforme più popolari per discutere e risolvere problemi matematici di vario livello, dall’elementare all’avanzato.
Art of Problem Solving (AoPS) – Questo sito è molto noto tra gli studenti di matematica di livello avanzato e i partecipanti a competizioni matematiche. Offre forum, corsi online, e risorse educative su una vasta gamma di argomenti.
MathOverflow – Questo sito è destinato a matematici professionisti e ricercatori. È una piattaforma per domande di ricerca avanzata in matematica. È strettamente legato a Math Stack Exchange ma è orientato a un pubblico con una formazione più avanzata.
PlanetMath – Una comunità collaborativa di matematici che crea e cura articoli enciclopedici e altre risorse di matematica. È simile a Wikipedia, ma focalizzata esclusivamente sulla matematica.
Wolfram MathWorld – Una delle risorse online più complete per la matematica. Contiene migliaia di articoli su argomenti di matematica, creati e curati da esperti. Sebbene non sia un forum, è una risorsa eccellente per la teoria matematica.
The Math Forum – Un sito storico che offre un’ampia gamma di risorse, inclusi forum di discussione, articoli e risorse educative. Sebbene alcune parti del sito siano state integrate con altri servizi, come NCTM, rimane una risorsa preziosa per la comunità educativa.
Stack Overflow (sezione matematica) – Sebbene Stack Overflow sia principalmente noto per la programmazione, ci sono anche discussioni rilevanti di matematica applicata, specialmente nel contesto della scienza dei dati, statistica, e algoritmi.
Reddit (r/Math) – Un subreddit popolare dove si possono trovare discussioni su una vasta gamma di argomenti matematici. È meno formale rispetto ai siti di domande e risposte come Math Stack Exchange, ma ha una comunità attiva e molte discussioni interessanti.
Brilliant.org – Offre corsi interattivi e problemi di matematica e scienza. È particolarmente utile per chi vuole allenare le proprie capacità di problem solving in matematica.
Khan Academy – Una risorsa educativa globale con lezioni video, esercizi interattivi e articoli su una vasta gamma di argomenti di matematica, dalla scuola elementare all’università.

Document

Menu

Chiudi

Il principio di induzione

Autori e revisori

Leggi...

Dimostrazione.

Dimostrazione.

Dimostrazione.

Dimostrazione.

Scarica la teoria

Dimostrazione.

Dimostrazione.

Osservazione 13.

Osservazione 14.

Dimostrazione.

Dimostrazione.

Tutta la teoria di analisi matematica

Leggi...

Tutte le cartelle di Analisi Matematica

Leggi...

Tutti gli esercizi di geometria

Strutture algebriche.

Algebra lineare.

Geometria analitica.

Geometria differenziale.

Risorse didattiche aggiuntive per approfondire la matematica

Leggi...

Suggerimenti, refusi ed errori

Cosa dicono di noi