Disuguaglianza con coefficienti binomiali

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
Gottinger95
Messaggi: 481
Iscritto il: 01 lug 2011, 22:52

Re: Disuguaglianza con coefficienti binomiali

Messaggio da Gottinger95 » 19 giu 2014, 18:35

Vogliamo dimostrare che per induzione su \(n\) che, fissato \(d\), \( \binom{n}{d} > 2(d-1)(n-d-1)\), oppure che ho sbagliato.
Caso base: \(n=d+2\). Si ha
\[ \frac{(d+2)(d+1)}{2} \stackrel{?}{>} 2(d-1) \ \ \Leftrightarrow \ \ \ d^2 -d+6 \stackrel{?}{>} 0 \]
Il \(\Delta\) è negativo e il coefficiente di \(d^2\) è positivo, quindi sì, è sempre positiva.
Passo induttivo: \(n \rightarrow n+1\)
Vogliamo dimostrare che, detto \(LHS(n) = \binom{n}{d}, RHS(n) = 2(d-1)(n-d-1)\), si ha
\[ \frac{LHS(n+1)}{LHS(n)} > \frac{RHS(n+1)}{RHS(n)} \ \ (*) \]
che moltiplicata per l'ipotesi induttiva \(LHS(n) > RHS(n)\) dà \(LHS(n+1) >RHS(n+1)\). Dimostriamo (*):
\[ \frac{ \binom{n+1}{d} }{\binom{n}{d} } = \frac{(n+1) \cdot \ldots \cdot (n+2-d)}{n \cdot \ldots \cdot (n+1-d)} = \frac{(n+1)}{n+1-d} \stackrel{?}{>} \frac{n-d}{n-d-1}= \frac{ 2(d-1)(n-d)}{2(d-1)(n-d-1) }\]
che si trasforma in:
\[ (n+1)(n-d-1) \stackrel{?}{>} (n-d)(n-d+1) \ \ \ \Leftrightarrow \ \ \ -dn -1 \stackrel{?}{>} (-2d+1)n -d(1-d) \ \ \ \Leftrightarrow \ \ \ n(d-1) \stackrel{?}{>}1+d(d-1)\]
D'altronde \(n(d-1) > (d+1)(d-1) = d(d-1) + (d-1) \ge d(d-1)+1 \), usando il fatto che \( 2 \le d < n-1\).
Con questo si conclude la dimostrazione.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe

scambret
Messaggi: 713
Iscritto il: 23 mag 2012, 20:49
Località: Acquarica del Capo

Re: Disuguaglianza con coefficienti binomiali

Messaggio da scambret » 20 giu 2014, 11:13

Bon, avevo pensato ad un altro approccio.
Riscriviamo questa disuguaglianza come $$\binom{n}{x+1} > 2x(n-2-x)$$ con $0<x<n-2$

Banalmente $x \geq 1$, dunque $n-2>x \geq 1$ significa $n \geq 4$.

Per AM-GM abbiamo che $\displaystyle 2x(n-2-x) \leq 2 \left ( \frac{(x)+(n-2-x)}{2} \right )^2 = \frac{(n-2)^2}{2}$

Ora la funzione $\displaystyle f(x)=\binom{n}{x+1}$ (con $1 \leq x \leq n-3$), ha minimo negli estremi (questo è noto), dunque $\displaystyle \binom{n}{x+1} \geq \binom{n}{2} = \frac{n^2-n}{2}$

Dunque dobbiamo vedere se per ogni $n \geq 4$ abbiamo $\displaystyle \frac{n^2-n}{2} > \frac{n^2-4n+4}{2}$ e questa è vera per ogni $n >2$.

Edit: modificato un segno
Ultima modifica di scambret il 05 lug 2014, 11:33, modificato 1 volta in totale.

Avatar utente
Drago96
Messaggi: 1145
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Disuguaglianza con coefficienti binomiali

Messaggio da Drago96 » 20 giu 2014, 16:53

Carina! Occhio però a un typo in amgm ;)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: Disuguaglianza con coefficienti binomiali

Messaggio da Triarii » 07 lug 2014, 17:46

Intanto metto l'idea della dimostrazione.
1) Si fanno a mano i casi $d=2$ e $d=n-1$ (tanto sono delle disequazioni di secondo grado)
2) Con AM-GM si mostra che $RHS\le \dfrac {(n-2)^2} {2}$. Portando a destra $-n$ e usando la maggiorazione appena trovata, otteniamo $\binom {n} {d}>\dfrac {n^2-2} {2}$. Si noti che la quantità a destra è indipendente da $d$
3) Sfruttiamo il fatto noto che il binomiale assume valore minimo agli estremi, quindi per $d=3$ e $d=n-3$. Se riusciamo a mostrare che la disequazione è valida per $d=3$, allora sarà valida anche per gli altri $n$, dato che la quantità a destra è solo funzione di $n$.
4)Se $d=3$ otteniamo un terzo grado, che si può smontare o con induzione e ragionamenti sulla crescenza, oppure con le derivate.
"We' Inge!"
LTE4LYF

Rispondi