Esercizio 5

Esercizio 5   Si dimostri che ${n \choose \frac{n}{2}} = O(2^n)$.

Visto che $n$ deve essere pari, possiamo scrivere direttamente $n= 2m.$

Prima soluzione: abbiamo

$${2m \choose m} = \frac{(2m)!}{m! m!} = \frac{2m}{m} \frac{2m-1}{m} \frac{2m-2}{m-1} \frac{2m-3}{m-1} \ldots \frac{2}{1} \frac{1}{1}.$$

Si vede chiaramente che nessuna delle $2m$ frazioni qui moltiplicate supera due.

Seconda soluzione. Secondo la formula di Stirling $k! = [1+ \Theta(k^{-1})] \sqrt{2 \pi k} \left( \frac{k}{e} \right)^k$ da cui

$${2m \choose m} = \frac{(2m)!}{m! m!} =[1+ \Theta(m^{-1})] \sqrt{\frac{1}{\pi m}} 2^{2m}.$$

Terza soluzione: i coefficienti della riga $k$-esima del triangolo di Tartaglia sommano a $2^k:$

$$\sum_{j=0}^{k} {k \choose j} = 2^k.$$

Questo si dimostra o per induzione o considerando lo sviluppo del binomio $(1+1)^k.$ Allora ${2m \choose m},$ essendo uno solo degli $m+1$ coefficienti della riga $2m$-esima, non può superare $2^{2m}.$

Tra l'altro, ricordiamo che ${2m \choose m}$ è il più grande dei coefficienti della riga $2m$-esima, in quanto i coefficienti binomiali crescono muovendosi dai lati verso il centro. Questo si può vedere facilmente scrivendo

$${k \choose j} = \frac{k}{1} \frac{k-1}{2} \ldots \frac{k-j+2}{j-1} \frac{k-j+1}{j}$$

e vedendo quando i fattori cominciano a diventare minori di uno. Questa semplice osservazione ci permette di stabilire che

$${2m \choose m} \geq \frac{2^{2m}}{m+1}.$$

Quindi, con semplici osservazioni sul triangolo di Tartaglia, abbiamo scoperto che ${2m \choose m} \in O(2^{2m})$ e che

${2m \choose m} \in \Omega(2^{2m} m^{-1}).$ Il risultato che si ottiene con Stirling, ${2m \choose m} \in \Theta(2^{2m} m^{-1/2}),$ ci dice che la verità sta proprio nel mezzo.