Dati due interi positivi $ n>k $, dimostrare che:
$ \[
\frac{1}{n+1} \cdot \frac{n^n}{k^k (n-k)^{n-k}} < \frac{n!}{k! (n-k)!} < \frac{n^n}{k^k(n-k)^{n-k}}
\] $
Disuguaglianza strana sugli interi
Bella approssimazione!
E per un problema non-standard (almeno per Algebra) vado con una soluzione non-standar (addio AM-GM!).
Intanto dimostro la RHS.
Voglio dimostrare che:
$ \displaystyle \frac{n!}{k!(n-k)!} < \frac{n^n}{k^k(n-k)^{n-k}} $
E decido di riscriverla così:
$ \displaystyle a^ab^b { a+b \choose a} < (a+b)^{a+b} $
A questo punto do un'interpretazione a ste formule.
La RHS conta chiaramente le funzioni da un insieme con (a+b) elementi in se stesso. Possiamo immaginare come un modo di colorare un quadrato di (a+b) x (a+b) quadratini, in modo che in ogni colonna ci sia esattamente un quadratino annerito.
La LHS la interpreto in questo modo: dalle (a+b) colonne, prima ne scelgo a. Poi, in ciascuna colonna di quelle scelte coloro una casella compresa tra la prima (dal basso) e la a-esima. Tra quelle non scelte, coloro una casella compresa tra la prima e la b-esima.
Vorrei dimostrare che le combinazioni che offre la LHS sono minori da quelle offerte dalla RHS. Ma questa interpretazione non risolve il problema. L'idea per risolverlo è interpretare la LHS in questo modo: prima scelgo a colonne, e in queste coloro una casella tra la prima e la a-esima. In ciascuna di quelle non scelte, coloro una casella tra la (a+1)-esima e la (a+b)-esima!
In questo modo, se una colonna è colorata in una posizione da 1 ad a, vuol dire che è una colonna scelta, se è colorata in una posizione da a+1 ad a+b, vuol dire che è una colonna non scelta. Ovvero: a ciascuna combinazione raggiunta dalla LHS (secondo la seconda interpretazione) associo in modo unica una funzione da (a+b) in (a+b). [nota: con (a+b) indico un generico insieme di a+b elementi. in effetti per come si definisce di solito i naturali, a+b = {0,1,2,a+b-1}]
Basta far vedere che la funzione non è suriettiva. Ma se in una funzione, (supponiamo a >= b) c'è un valore che viene assunto da almeno a+1 elementi, questo non sarà raggiunto da nessuna combinazione della LHS, perchè quegli elementi a cui associo lo stesso valore saranno o tutti "colonne scelte", o "colonne non scelte", che sono rispettivamente al più a o al più b, sempre minori di a+1.
La parte sinistra della disuguaglianza di Maria è più difficile... io avrei trovato un modo per dimostrarla (si tratta di usare a+b+1 copie di una qualche interpretazione di $ \displaystyle a^ab^b { a+b \choose a} $ per ricoprire tutte le funzioni da (a+b) in (a+b)), ma è abbastanza "artigianale" è bruttino...
quindi se qualcuno trova una dimostrazione decente la scriva
E per un problema non-standard (almeno per Algebra) vado con una soluzione non-standar (addio AM-GM!).
Intanto dimostro la RHS.
Voglio dimostrare che:
$ \displaystyle \frac{n!}{k!(n-k)!} < \frac{n^n}{k^k(n-k)^{n-k}} $
E decido di riscriverla così:
$ \displaystyle a^ab^b { a+b \choose a} < (a+b)^{a+b} $
A questo punto do un'interpretazione a ste formule.
La RHS conta chiaramente le funzioni da un insieme con (a+b) elementi in se stesso. Possiamo immaginare come un modo di colorare un quadrato di (a+b) x (a+b) quadratini, in modo che in ogni colonna ci sia esattamente un quadratino annerito.
La LHS la interpreto in questo modo: dalle (a+b) colonne, prima ne scelgo a. Poi, in ciascuna colonna di quelle scelte coloro una casella compresa tra la prima (dal basso) e la a-esima. Tra quelle non scelte, coloro una casella compresa tra la prima e la b-esima.
Vorrei dimostrare che le combinazioni che offre la LHS sono minori da quelle offerte dalla RHS. Ma questa interpretazione non risolve il problema. L'idea per risolverlo è interpretare la LHS in questo modo: prima scelgo a colonne, e in queste coloro una casella tra la prima e la a-esima. In ciascuna di quelle non scelte, coloro una casella tra la (a+1)-esima e la (a+b)-esima!
In questo modo, se una colonna è colorata in una posizione da 1 ad a, vuol dire che è una colonna scelta, se è colorata in una posizione da a+1 ad a+b, vuol dire che è una colonna non scelta. Ovvero: a ciascuna combinazione raggiunta dalla LHS (secondo la seconda interpretazione) associo in modo unica una funzione da (a+b) in (a+b). [nota: con (a+b) indico un generico insieme di a+b elementi. in effetti per come si definisce di solito i naturali, a+b = {0,1,2,a+b-1}]
Basta far vedere che la funzione non è suriettiva. Ma se in una funzione, (supponiamo a >= b) c'è un valore che viene assunto da almeno a+1 elementi, questo non sarà raggiunto da nessuna combinazione della LHS, perchè quegli elementi a cui associo lo stesso valore saranno o tutti "colonne scelte", o "colonne non scelte", che sono rispettivamente al più a o al più b, sempre minori di a+1.
La parte sinistra della disuguaglianza di Maria è più difficile... io avrei trovato un modo per dimostrarla (si tratta di usare a+b+1 copie di una qualche interpretazione di $ \displaystyle a^ab^b { a+b \choose a} $ per ricoprire tutte le funzioni da (a+b) in (a+b)), ma è abbastanza "artigianale" è bruttino...
quindi se qualcuno trova una dimostrazione decente la scriva
Stupenda la dimostrazione della seconda parte!!!!
Per la prima parte (ma anche questa dimostrazione non e' particolarmente bella) possiamo fare una specie di induzione improbabile:
prima dimostriamo il caso n=2k e n=(2k+1), e a quel punto facciamo un'induzione su k:
Prima parte a)
$ \frac{(2k)^{2k}}{(2k+1)k^{2k}}<\frac{(2k)!}{k!k!} $
$ 2^{k}k!2^{k}k!<(2k+1)! $
$ 2*4*...*(2k-2)*(2k)<3*5*...*(2k-1)*(2k+1) $
Prima parte b)
$ \frac{(2k+1)^{2k+1}}{(2k+2)k^{k}(k+1)^{k+1}}<\frac{(2k+1)!}{k!(k+1)!} $
Dividiamo a sinistra per il LHS di a) e a destra per il RHS di a) e troviamo una cosa che implica la tesi:
$ \frac{(2k+1)^{2k+2}k^k}{(2k+2)(k+1)^{k+1}(2k)^{2k}}<\frac{2k+1}{k+1} $
$ (2k+1)^{2k+1}<(2k)^{k}(2k+2)^{k+1} $
$ (1+\frac{1}{2k})^k<(1+\frac{1}{2k+1})^{k+1} $
$ (1+\frac{1}{2k})^{2k}<(1+\frac{1}{2k+1})^{2k+2} $
Ora per la crescenza di (1+1/a)^a abbiamo:
$ (1+\frac{1}{2k})^{2k}<(1+\frac{1}{2k+1})^{2k+1}<(1+\frac{1}{2k+1})^{2k+2} $
Seconda parte:
induciamo facendo crescere k (che nel passo base vale [n/2]). I valori di k<[n/2] sono veri per simmetria.
ipotesi induttiva:
$ \frac{n^n}{(n+1)k^{k}(n-k)^{n-k}}<\frac{n!}{k!(n-k)!} $
tesi:
$ \frac{n^n}{(n+1)(k+1)^{k+1}(n-k-1)^{n-k-1}}<\frac{n!}{(k+1)!(n-k-1)!} $
che e' implicata da (dividendo per l'ipotesi):
$ \frac{k^{k}(n-k)^{n-k}}{(k+1)^{k+1}(n-k-1)^{n-k-1}}\leq \frac{n-k}{k+1} $
$ (1+\frac{1}{n-k-1})^{n-k-1}\leq (1+\frac{1}{k})^k $
ovvero, sempre per la crescenza di (1+1/a)^a:
$ n-k-1\leq k $
$ n\leq 2k+1 $
Per la prima parte (ma anche questa dimostrazione non e' particolarmente bella) possiamo fare una specie di induzione improbabile:
prima dimostriamo il caso n=2k e n=(2k+1), e a quel punto facciamo un'induzione su k:
Prima parte a)
$ \frac{(2k)^{2k}}{(2k+1)k^{2k}}<\frac{(2k)!}{k!k!} $
$ 2^{k}k!2^{k}k!<(2k+1)! $
$ 2*4*...*(2k-2)*(2k)<3*5*...*(2k-1)*(2k+1) $
Prima parte b)
$ \frac{(2k+1)^{2k+1}}{(2k+2)k^{k}(k+1)^{k+1}}<\frac{(2k+1)!}{k!(k+1)!} $
Dividiamo a sinistra per il LHS di a) e a destra per il RHS di a) e troviamo una cosa che implica la tesi:
$ \frac{(2k+1)^{2k+2}k^k}{(2k+2)(k+1)^{k+1}(2k)^{2k}}<\frac{2k+1}{k+1} $
$ (2k+1)^{2k+1}<(2k)^{k}(2k+2)^{k+1} $
$ (1+\frac{1}{2k})^k<(1+\frac{1}{2k+1})^{k+1} $
$ (1+\frac{1}{2k})^{2k}<(1+\frac{1}{2k+1})^{2k+2} $
Ora per la crescenza di (1+1/a)^a abbiamo:
$ (1+\frac{1}{2k})^{2k}<(1+\frac{1}{2k+1})^{2k+1}<(1+\frac{1}{2k+1})^{2k+2} $
Seconda parte:
induciamo facendo crescere k (che nel passo base vale [n/2]). I valori di k<[n/2] sono veri per simmetria.
ipotesi induttiva:
$ \frac{n^n}{(n+1)k^{k}(n-k)^{n-k}}<\frac{n!}{k!(n-k)!} $
tesi:
$ \frac{n^n}{(n+1)(k+1)^{k+1}(n-k-1)^{n-k-1}}<\frac{n!}{(k+1)!(n-k-1)!} $
che e' implicata da (dividendo per l'ipotesi):
$ \frac{k^{k}(n-k)^{n-k}}{(k+1)^{k+1}(n-k-1)^{n-k-1}}\leq \frac{n-k}{k+1} $
$ (1+\frac{1}{n-k-1})^{n-k-1}\leq (1+\frac{1}{k})^k $
ovvero, sempre per la crescenza di (1+1/a)^a:
$ n-k-1\leq k $
$ n\leq 2k+1 $
"Sei la Barbara della situazione!" (Tap)
)... anch'io l'avevo fatto con un'induzione non-standard e sfruttando la crescenza di (1+1/x)^x, anche se in modo leggermente diverso...