Induzione e Calcolo Combinatorio

Il principio di induzione matematica è una tecnica dimostrativa fondamentale. Data una proprietà $P(n)$ definita per $n\in\mathbb{N}$, per dimostrare che $P(n)$ vale per ogni $n$:

1. Base induttiva: si dimostra $P(1)$ (o $P(0)$, a seconda della definizione di $\mathbb{N}$).
2. Passo induttivo: si assume $P(k)$ (ipotesi induttiva) e si dimostra $P(k+1)$.

Esempio — somma dei primi $n$ naturali: dimostriamo $1+2+\cdots+n = n(n+1)/2$.

• Base $n=1$: $1 = 1(1+1)/2 = 1$, vero.
• Passo: supponiamo $1+\cdots+k = k(k+1)/2$ (ip. induttiva). Allora $1+\cdots+k+(k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1)+2(k+1)}{2} = \frac{(k+1)(k+2)}{2}$, che è la formula per $n=k+1$. Quindi la formula vale per ogni $n$.

Disuguaglianza di Bernoulli: $(1+x)^n \geq 1+nx$ per $x>-1$ e $n\in\mathbb{N}$. Base $n=1$: $1+x\geq1+x$. Passo: $(1+x)^{k+1} = (1+x)^k(1+x) \geq (1+kx)(1+x) = 1+(k+1)x+kx^2 \geq 1+(k+1)x$.

Il coefficiente binomiale $C(n,k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$ conta i modi di scegliere $k$ oggetti da un insieme di $n$ (senza ordine e senza ripetizione).

Proprietà fondamentali:

• $\binom{n}{0} = \binom{n}{n} = 1$
• $\binom{n}{k} = \binom{n}{n-k}$ (simmetria)
• $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$ (identità di Pascal — base del triangolo di Tartaglia)

Triangolo di Tartaglia (Pascal): disposizione triangolare dove ogni numero è la somma dei due soprastanti. La riga $n$ contiene $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$.

Formula del binomio di Newton: per ogni $a,b\in\mathbb{R}$ e $n\in\mathbb{N}$:

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

Il coefficiente di $a^{n-k}b^k$ è esattamente $\binom{n}{k}$. Esempio: $(x+1)^4 = x^4 + 4x^3 + 6x^2 + 4x + 1$.

Proprietà delle sommatorie: $\sum_{k=1}^n (a_k\pm b_k) = \sum a_k \pm \sum b_k$, $\sum_{k=1}^n c\,a_k = c\sum a_k$, $\sum_{k=1}^n c = nc$.

Progressione aritmetica: successione del tipo $a_k = a_1 + (k-1)d$. Somma dei primi $n$ termini:

$$S_n = \sum_{k=1}^n a_k = \frac{n(a_1+a_n)}{2} = \frac{n[2a_1+(n-1)d]}{2}.$$

Progressione geometrica: successione del tipo $a_k = a_1 q^{k-1}$. Somma dei primi $n$ termini (per $q\neq1$):

$$S_n = \sum_{k=1}^n a_1 q^{k-1} = a_1\frac{1-q^n}{1-q}.$$

Serie geometrica: $\sum_{k=0}^\infty q^k = 1/(1-q)$ per $|q|<1$. Questo è il primo esempio fondamentale di serie convergente.