Principio di induzione

Per dimostrare che una proprietà vale per tutti i numeri naturali serve uno schema in due passi — base e passo induttivo — reso vivido dalla metafora del domino infinito. Applichiamo il principio a somme notevoli e alla disuguaglianza di Bernoulli, e vediamo come un’induzione mal impostata possa “dimostrare” affermazioni false.

• Il principio di induzione
• Il domino infinito
• Somma dei primi n naturali
• Somma dei primi n quadrati
• Disuguaglianza di Bernoulli
• Un’induzione sbagliata, i cavalli

To prove that a property holds for all natural numbers we need a two-step scheme — base and inductive step — made vivid by the metaphor of the infinite domino. We apply the principle to notable sums and to Bernoulli’s inequality, and we see how a badly set-up induction can “prove” false statements.

• The principle of induction
• The infinite domino
• Sum of the first n naturals
• Sum of the first n squares
• Bernoulli’s inequality
• A faulty induction, the horses

Quando vogliamo dimostrare che una proprietà $P(n)$ vale per tutti i numeri naturali $n\ge n_0$ non possiamo verificarla uno a uno: i naturali sono infiniti. Il principio di induzione fornisce uno schema in due passi che “chiude” la dimostrazione in un colpo solo.

Teorema — Principio di induzione matematica

Sia $P(n)$ una proposizione definita per ogni $n\in\mathbb{N}$, $n\ge n_0$. Se:

• (base) $P(n_0)$ è vera;
• (passo induttivo) per ogni $k\ge n_0$, $P(k)\Rightarrow P(k+1)$,

allora $P(n)$ è vera per ogni $n\ge n_0$.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Numeri naturali · Principio di induzione
Metodi: Induzione
Competenze: Dimostrare

When we want to prove that a property $P(n)$ holds for all natural numbers $n\ge n_0$ we cannot check it one by one: the naturals are infinite. The principle of induction provides a two-step scheme that “closes” the proof in one stroke.

Theorem — Principle of mathematical induction

Let $P(n)$ be a statement defined for every $n\in\mathbb{N}$, $n\ge n_0$. If:

• (base) $P(n_0)$ is true;
• (inductive step) for every $k\ge n_0$, $P(k)\Rightarrow P(k+1)$,

then $P(n)$ is true for every $n\ge n_0$.

Links

Topics: Set theory
Concepts: Natural numbers · Principle of induction
Methods: Induction
Skills: Proving

Osservazione — Il domino infinito

Pensa a una fila infinita di tessere del domino: la base dice “la prima cade”; il passo induttivo dice “se cade la $k$-esima, fa cadere anche la successiva”. Dunque cadono tutte.

L’induzione è la formalizzazione di questa intuizione, ed è valida proprio perché i naturali sono ben fondati (ogni sottoinsieme non vuoto ha un minimo). La metafora del domino come “trasporto” del valore di verità da $P(k)$ a $P(k+1)$ è discussa da Esty (cap. 5) come rilettura linguistica del condizionale “per ogni $k$, se… allora…”.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Principio di induzione
Metodi: Induzione

Observation — The infinite domino

Think of an infinite row of domino tiles: the base says “the first one falls”; the inductive step says “if the $k$-th one falls, it makes the next one fall too”. Hence they all fall.

Induction is the formalisation of this intuition, and it is valid precisely because the naturals are well-founded (every non-empty subset has a minimum). The domino metaphor as the “transport” of the truth value from $P(k)$ to $P(k+1)$ is discussed by Esty (ch. 5) as a linguistic reinterpretation of the conditional “for every $k$, if… then…”.

Links

Topics: Set theory
Concepts: Principle of induction
Methods: Induction

Esempio — Somma dei primi $n$ naturali

Dimostriamo che, per ogni $n\ge 1$, $P(n)\colon\quad 1+2+\cdots+n = \frac{n(n+1)}{2}.$ Base ($n=1$): $1=\dfrac{1\cdot 2}{2}$. Vero.

Passo: supponiamo vera $P(k)$, ossia $1+\cdots+k=\dfrac{k(k+1)}{2}$. Allora $1+\cdots+k+(k+1) = \frac{k(k+1)}{2}+(k+1) = (k+1)\frac{k+2}{2} = \frac{(k+1)(k+2)}{2},$ che è esattamente $P(k+1)$. Per induzione, la formula vale per ogni $n\ge 1$. ∎

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Principio di induzione
Metodi: Induzione
Competenze: Dimostrare

Example — Sum of the first $n$ naturals

We prove that, for every $n\ge 1$, $P(n)\colon\quad 1+2+\cdots+n = \frac{n(n+1)}{2}.$ Base ($n=1$): $1=\dfrac{1\cdot 2}{2}$. True.

Step: suppose $P(k)$ is true, that is $1+\cdots+k=\dfrac{k(k+1)}{2}$. Then $1+\cdots+k+(k+1) = \frac{k(k+1)}{2}+(k+1) = (k+1)\frac{k+2}{2} = \frac{(k+1)(k+2)}{2},$ which is exactly $P(k+1)$. By induction, the formula holds for every $n\ge 1$. ∎

Links

Topics: Set theory
Concepts: Principle of induction
Methods: Induction
Skills: Proving

Esempio — Somma dei primi $n$ quadrati

$P(n)\colon\quad 1^2+2^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}.$ Base: $n=1$: $1=\dfrac{1\cdot 2\cdot 3}{6}$. Vero.

Passo: assumiamo $P(k)$ e sommiamo $(k+1)^2$: $\frac{k(k+1)(2k+1)}{6}+(k+1)^2 = \frac{(k+1)\bigl[k(2k+1)+6(k+1)\bigr]}{6} = \frac{(k+1)(2k^2+7k+6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6},$ che è $P(k+1)$. ∎

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Principio di induzione
Metodi: Induzione
Competenze: Dimostrare

Example — Sum of the first $n$ squares

$P(n)\colon\quad 1^2+2^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}.$ Base: $n=1$: $1=\dfrac{1\cdot 2\cdot 3}{6}$. True.

Step: we assume $P(k)$ and add $(k+1)^2$: $\frac{k(k+1)(2k+1)}{6}+(k+1)^2 = \frac{(k+1)\bigl[k(2k+1)+6(k+1)\bigr]}{6} = \frac{(k+1)(2k^2+7k+6)}{6} = \frac{(k+1)(k+2)(2k+3)}{6},$ which is $P(k+1)$. ∎

Links

Topics: Set theory
Concepts: Principle of induction
Methods: Induction
Skills: Proving

Esempio — Disuguaglianza di Bernoulli

Per $x>-1$ e $n\in\mathbb{N}$, $(1+x)^n \ge 1+nx.$ Base ($n=0$): $1\ge 1$. Vero.

Passo: moltiplichiamo l’ipotesi per $(1+x)>0$: $(1+x)^{k+1}=(1+x)^k(1+x)\ge(1+kx)(1+x)=1+(k+1)x+kx^2\ge 1+(k+1)x,$ perché $kx^2\ge 0$. ∎

Si userà in Quinta per dimostrare che $\left(1+\dfrac{1}{n}\right)^n$ è limitata.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Principio di induzione
Metodi: Induzione
Competenze: Dimostrare
Persone: Jacob Bernoulli

Example — Bernoulli's inequality

For $x>-1$ and $n\in\mathbb{N}$, $(1+x)^n \ge 1+nx.$ Base ($n=0$): $1\ge 1$. True.

Step: we multiply the hypothesis by $(1+x)>0$: $(1+x)^{k+1}=(1+x)^k(1+x)\ge(1+kx)(1+x)=1+(k+1)x+kx^2\ge 1+(k+1)x,$ because $kx^2\ge 0$. ∎

It will be used in Year 5 to prove that $\left(1+\dfrac{1}{n}\right)^n$ is bounded.

Links

Topics: Set theory
Concepts: Principle of induction
Methods: Induction
Skills: Proving
People: Jacob Bernoulli

Osservazione — Errore tipico: "dimostrazione" sbagliata di un'affermazione falsa

Si racconta la famosa “dimostrazione” che in ogni gruppo di $n$ cavalli i cavalli hanno tutti lo stesso colore. La base ($n=1$) è ovvia; il passo induttivo prende un gruppo di $k+1$ cavalli, ne toglie uno per ottenere $k$ (stesso colore), poi lo rimette a posto e ne toglie un altro, confrontandolo con i restanti $k$.

La falla è che il passaggio richiede che i due sottogruppi di $k$ cavalli si intersechino, cosa che fallisce per $k=1$: l’induzione richiede che la catena $P(1)\to P(2)\to P(3)\to\ldots$ sia continua, non basta un passo aritmetico.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Principio di induzione
Metodi: Induzione

Observation — Typical error: a faulty "proof" of a false statement

There is the famous “proof” that in every group of $n$ horses the horses all have the same colour. The base ($n=1$) is obvious; the inductive step takes a group of $k+1$ horses, removes one to obtain $k$ (same colour), then puts it back and removes another, comparing it with the remaining $k$.

The flaw is that the argument requires the two subgroups of $k$ horses to intersect, which fails for $k=1$: induction requires the chain $P(1)\to P(2)\to P(3)\to\ldots$ to be unbroken, a single arithmetic step is not enough.

Links

Topics: Set theory
Concepts: Principle of induction
Methods: Induction