Esercizio 12binomio di Newton per induzione

---

Impostazione

$p(n)$: "$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}$", da dimostrare per ogni $n \ge n_0 = 0$.

Passo base: $p(0)$

A sinistra $(a + b)^0 = 1$ (lecito perché $a + b \ne 0$Ogni numero non nullo elevato a $0$ vale $1$, mentre $0^0$ non è definito.Funzioni potenza →). A destra la somma ha il solo termine $k = 0$: $\binom{0}{0}$Coefficiente binomiale $\frac{n!}{k!\,(n-k)!}$; poiché $0! = 1$, vale $\binom{0}{0} = 1$.Fattoriale e coefficienti binomiali → $a^0 b^0 = 1 \cdot 1 \cdot 1 = 1$. Uguali ✓.

Passo induttivo: $p(n) \Rightarrow p(n+1)$

Ipotesi induttivaSi suppone vera $p(n)$ per un $n$ fissato e la si usa per dedurre $p(n+1)$.Principio di induzione →: $(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^k b^{n-k}$.

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

1. Usare l'ipotesi induttiva

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

2. Linearità: distribuire $(a+b)$

Moltiplicare per $(a + b)$ significa moltiplicare per $a$ e per $b$ e sommare. Portando $a$ (e poi $b$) dentro la sommatoria (è una costante rispetto a $k$Linearità: un fattore che non dipende dall'indice si può portare dentro o fuori dalla sommatoria.Sommatorie →):

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

(nella prima $a \cdot a^k = a^{k+1}$Proprietà delle potenze: $a^m \cdot a^n = a^{m+n}$, qui con $m = 1$.Funzioni potenza →; nella seconda $b \cdot b^{n-k} = b^{n+1-k}$).

Obiettivo da qui in poi: far comparire in entrambe le somme lo stesso termine $a^k b^{n+1-k}$, per poterle unire. La seconda va già bene; nella prima c'è $a^{k+1}$, quindi trasliamo l'indice.

3. Traslazione dell'indice nella prima somma

Poniamo $h = k + 1$Traslazione dell'indice: cambiando variabile si aggiornano insieme il termine generale ed entrambi gli estremi.Sommatorie → (cioè $k = h - 1$): quando $k = 0$, $h = 1$; quando $k = n$, $h = n + 1$. Sostituendo $k = h - 1$:

• $\binom{n}{k}$ diventa $\binom{n}{h-1}$;
• $a^{k+1}$ diventa $a^h$;
• $b^{n-k}$ diventa $b^{n-(h-1)} = b^{n+1-h}$.

$$\sum_{k=0}^{n} \binom{n}{k} a^{k+1} b^{n-k} = \sum_{h=1}^{n+1} \binom{n}{h-1} a^h b^{n+1-h} = \sum_{k=1}^{n+1} \binom{n}{k-1} a^k b^{n+1-k}$$

(nell'ultimo passaggio l'indice è mutoIl nome dell'indice non conta: chiamarlo $h$ o $k$ non cambia il valore della somma.Sommatorie →: lo richiamiamo $k$).

Ora abbiamo

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

Le due somme hanno lo stesso termine generale, ma estremi diversi: la prima va da $1$ a $n+1$, la seconda da $0$ a $n$.

4. Additività: staccare i termini "in più"

Per avere entrambe da $1$ a $n$:

• dalla prima stacchiamo l'ultimo termineAdditività: la somma da $1$ a $n+1$ è la somma da $1$ a $n$ più il termine con $k = n+1$.Sommatorie →, $k = n + 1$: $\binom{n}{n} a^{n+1} b^0 = a^{n+1}$ (perché $\binom{n}{n} = 1$C'è un solo modo di scegliere tutti gli $n$ elementi; analogamente $\binom{n}{0} = 1$.Fattoriale e coefficienti binomiali →);
• dalla seconda stacchiamo il primo termine, $k = 0$: $\binom{n}{0} a^0 b^{n+1} = b^{n+1}$ (perché $\binom{n}{0} = 1$).

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

5. Linearità al contrario: unire le due somme

Ora hanno gli stessi estremi e lo stesso $a^k b^{n+1-k}$, che si raccoglieLinearità al contrario: due somme con gli stessi estremi diventano una sola, sommando i termini con lo stesso $k$.Sommatorie →:

$$= a^{n+1} + \sum_{k=1}^{n} \left[ \binom{n}{k-1} + \binom{n}{k} \right] a^k b^{n+1-k} + b^{n+1}$$

6. Formula di Stifel

Per $1 \le k \le n$ (cioè $0 < k < n + 1$), la formula di Stifel$\binom{m}{k} = \binom{m-1}{k-1} + \binom{m-1}{k}$ per $0 < k < m$: nel triangolo di Tartaglia ogni numero è la somma dei due sopra.Fattoriale e coefficienti binomiali → con $n + 1$ al posto di $n$ dice

$$\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k}$$

Quindi

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

7. Riassorbire i due termini staccati

I due termini isolati sono proprio i termini mancanti della somma da $0$ a $n+1$:

• $a^{n+1} = \binom{n+1}{n+1} a^{n+1} b^0$ è il termine $k = n + 1$;
• $b^{n+1} = \binom{n+1}{0} a^0 b^{n+1}$ è il termine $k = 0$.

(usando $\binom{n+1}{n+1} = \binom{n+1}{0} = 1$). Rimettendoli dentroAdditività al contrario: aggiungendo i termini $k = 0$ e $k = n+1$ la somma da $1$ a $n$ diventa la somma da $0$ a $n+1$.Sommatorie →:

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

che è la tesi ✓.

---

Conclusione

Per il principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →, il binomio di NewtonLa formula per sviluppare (a+b)^n con i coefficienti binomiali.Binomio di Newton → vale per ogni $n \in \mathbb{N}$ ∎.

Riepilogo degli strumenti usati

Controllo su un caso piccolo

Da $n = 2$ a $n = 3$: $(a+b)^3 = (a+b)(b^2 + 2ab + a^2)$. I coefficienti della riga $3$Righe del triangolo di Tartaglia: la riga $n$ contiene $\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}$.Fattoriale e coefficienti binomiali → si ottengono sommando coppie vicine della riga $2$ ($1, 2, 1$): $1, \ 1+2, \ 2+1, \ 1 = 1, 3, 3, 1$. È esattamente ciò che fanno i passi 4–6: Stifel in mezzo, gli $1$ ai bordi.