Stimare somma di binomiali

Allora :-D

Magari sarà una stupidata (nel quale caso chiuderò io stesso questa discussione), ma è da un giorno intero che mi struggo su una certa disuguaglianza che ora ho risolto tramite mathoverflow (mitico). Però è rimasta una cosa in qualche modo in sospeso. Condivido con voi questa cosa perché la ritengo curiosa. Poi magari è una banalità, non so.

Definiamo [tex]f(n,k) := \sum_{i=1}^k {n \choose i}[/tex]. Volevo dimostrare che se [tex]n[/tex] è abbastanza grande allora [tex]f(n,[n/3]) \leq {n \choose [n/3]+1}[/tex] (le quadre indicano la parte intera), e, a meno che non abbia preso cantonate, l'ho dimostrato usando le considerazioni che ho trovato qui (gratitudine :D ).

Ma nel mio struggimento mi sono anche chiesto un'altra cosa. Dato un numero reale [tex]t \geq 2[/tex], chiamiamo [tex]P(t)[/tex] la proposizione "esiste [tex]N \in \mathbb{N}[/tex] tale che [tex]f(n,[n/t]) \leq {n \choose [n/t]+1}[/tex] per ogni [tex]n \geq N[/tex]". Qual è l'inf dei [tex]t[/tex] per cui [tex]P(t)[/tex] è vera? Mi sono detto, questo inf dev'essere compreso tra 2 e 3, dato che [tex]P(2)[/tex] è falsa e [tex]P(3)[/tex] è vera. Mi sono detto, siccome nel comportamento asintotico dei fattoriali (Stirling) compare [tex]e[/tex], e [tex]2 < e < 3[/tex], vuoi vedere che questo inf è [tex]e[/tex]? :D

E invece no: computazionalmente questo inf sembra essere proprio [tex]3[/tex] (sembra infatti che [tex]P(2.999)[/tex] sia falsa :D ). Come dimostrereste che questo inf è proprio [tex]3[/tex]?

A me tutto ciò sembra curioso, ma forse è solo ingenuità.

Risposte
theras
Ciao,Martino!
Parto dalla premessa che ho preso per buono come P(2) sia falsa,
guardandomi bene dal provare ad immaginare il ragionamento da te seguito partendo dalle considerazioni che hai trovato nel sito linkato
(in merito ho una mia ipotesi di lavoro,collegata ad una stima asintotica di $2^n$,ma nel caso ne riparliamo altrove..);
ho poi dato per scontato senza verificarlo che,$AAkinNN$,
il coefficente mediano di posto $k+1$ dello sviluppo di $(a+b)^(2k)$ sia maggiore rispetto a tutti gli altri:
questo dovrebbe essere più facile da dimostrare,
forse per induzione o con qualche pratica interpretazione combinatoria "furba",
ma anche quì se ne riparlassimo dopo proverei nei tuoi confronti $text{gratitudine}^text{gratitudine}>$$>text{gratitudine}$ :D :wink:..
Ciò detto ho supposto per assurdo che $EEoverline(t)in(2,3),EEn_(overline(t))inNN$ t.c. $f(n,[n/(overline(t))])<=((n),([n/(overline(t))]+1))$ $AAn>=n_(overline(t))$,
e per comodità di notazione ne ho intanto dedotto che
$EEoverline(u)in(1,2),EEn_(overline(u))inNN$ t.c. $f(n,[n/(overline(u))])<=((n),([n/(overline(u))]+1))$ $AAn>=n_(overline(u))$;
a quel punto ho innanzitutto scelto a piacere un $overline(m)in2NN$ t.c. $overline(m)>=n_(overline(u))$,ed ho poi osservato che $overline(u)in(1,2)rArr1/2<1/(overline(u))rArr(overline(m))/2<(overline(m))/(overline(u))rArr[(overline(m))/2]<=[(overline(m))/(overline(u))]$:
a quel punto la ovvia "non decrescenza" in k della f(una volta fissato n,intendo chiaramente..)permetterà di dire che
$f(overline(m),[(overline(m))/2])<=f(overline(m),[(overline(m))/(overline(u))])$ e ciò,
congiuntamente all'ipotesi assurda ed alla mia iniziale "forzatura" sul "massimo" dei coefficenti dello sviluppo di Newton,
porterà ad affermare intanto che $f(overline(m),[(overline(m))/2])<=((overline(m)),([(overline(m))/2]+1))$.
Per tutti i valori di $n$$inNN$ che siano maggiori di $overline(m)$ mi sembra che,
a meno di mie gravi castronerie delle quali chiedo eventualmente venia,
si potrebbe giungere alla medesima conclusione con traccia di ragionamento analoga;
se ho ragione pure in questo P(2) sarebbe vera,e dunque due sarebbero le cose:
o mi fidavo meno di te
(e mi sà tanto che non ne avrei proprio motivo,
anche se è bene tu sappia che mangio ogni tipo di carne in commercio :P ),
oppure siamo rientrati in contraddizione e pertanto 3 è addirittura minimo assoluto del tuo insieme..
Pant,pant,che scarpinata:
m'asciugo il sudore e ti porgo i miei
saluti dal web.

Ciao! :D

Purtroppo capisco davvero poco di quello che dici, non capisco l'idea, e ti devo un po' disilludere:
"theras":
per comodità di notazione ne ho intanto dedotto che
$EEoverline(u)in(1,2),EEn_(overline(u))inNN$ t.c. $f(n,[n/(overline(u))])<=((n),([n/(overline(u))]+1))$ $AAn>=n_(overline(u))$;
Questo è falso, perché se fosse vero allora P(2) sarebbe vera, ma P(2) è falsa.

Il motivo per cui P(2) è falsa non farmelo scrivere dai, è abbastanza evidente :)

Ah, ora ho capito l'idea. Ma scusa perché mi rispondi in privato? Rispondi qui, altrimenti devo saltare di qua a là, insomma perché non rispondi qui? :)

Sarà solo una mia impressione, ma mi sembra che ti sei speso in tante parole per delle cosiddette "banalità" ma hai dato per scontato il passaggio principale (qui [tex]\overline{u}=\overline{t}-1[/tex] vero?):
"theras":
ho supposto per assurdo che $EEoverline(t)in(2,3),EEn_(overline(t))inNN$ t.c. $f(n,[n/(overline(t))])<=((n),([n/(overline(t))]+1))$ $AAn>=n_(overline(t))$,
e per comodità di notazione ne ho intanto dedotto che
$EEoverline(u)in(1,2),EEn_(overline(u))inNN$ t.c. $f(n,[n/(overline(u))])<=((n),([n/(overline(u))]+1))$ $AAn>=n_(overline(u))$;
Non mi sembra che dall'esistenza di [tex]n_{\overline{t}}[/tex] tu possa dedurre l'esistenza di [tex]n_{\overline{u}}[/tex]. Anzi direi che non puoi proprio: se tu potessi fare un ragionamento del genere allora potresti dedurre che P(2) è vera dal fatto che P(3) è vera usando solo il fatto che [tex]2=3-1[/tex]. Ma P(2) è falsa.

Se mi vuoi rispondere ti prego cerca di essere sintetico e concentrarti sulla sostanza :) se no diventa complicato selezionare il contenuto matematico di quello che dici.

theras
..rieccomi,Martino,
sperando di non aver violato il regolamento con questa sorta di cross-posting tra pubblico e privato che ho effettuato per l'ultima volta:
comportamento anomalo,certo,ma che non mi pare gravissimo!
Andiamo a noi,ora:
ma se metti caso il $overline(t)$ della mia ipotesi assurda fosse il tuo 2.999 :P,
ed il corrispondente $n_(overline(t))$ fosse 6000000,
perchè non potrei porre $overline(u)=1.999$ e $n_(overline(u))=6000000$?
Cosa scappa alla mia intuizione?
Per quanto riguarda il tuo ultimo appunto direi che se avessi notizie certe solo sul fatto che P(3) è vera ma non sapessi nulla su P(2),ed accettassi per assurdo che quest'ultima è falsa,
dovrei ricadere legittimamente in qualche contraddizione prima di poter affermare che P(t) è vera per t=2;
mi sà però che sarebbe impossibile arrivare ad una tale contraddizione con ragionamenti leciti,
proprio perchè P(2) è falsa,
ma ciò non toglie a priori la possibilità di poter provare a ragionare per assurdo sulla veridicità di P(t) per un ipotetico valore $overline(t)$$in(2,3)$:
possibile poi che io sia troppo arruginito,
e non veda che il mio errore stà proprio in questo passaggio logico alla base del mio ragionamento..
Ne riparliamo,se vorrai,
anche perchè rileggendomi m'è venuto piuttosto il dubbio che ieri ho avuto troppa fretta nelle conclusioni:
saluti dal web.

Ti ho risposto in privato, ma lo scrivo anche qui.

E' interessante leggerti, ma purtroppo in quello che dici di matematica ce n'è poca (scuserai questo mio fare diretto, ma lo preferisco a casuali tentativi di addolcire le pillole).

Non c'è nessuna ragione per cui se il risultato vale per [tex]t[/tex] allora dovrebbe valere per [tex]t-1[/tex]. Non sei legittimato a scegliere [tex]n_u = n_t[/tex]. Cioè, sei simpatico quando dici "scelgo [tex]n_u=n_t[/tex]", il problema è che non funziona questa scelta! Se mi vuoi convincere del contrario argomenta. Un'altra cosa che non capisco è perché insisti a dare per scontata la cosa più cruciale di tutto il tuo ragionamento.

Ripeto, se il tuo ragionamento funzionasse allora non c'è ragione per cui non dovrebbe funzionare quando [tex]t=3[/tex], e come ripeto [tex]P(3)[/tex] è vera mentre [tex]P(2)=P(3-1)[/tex] è falsa.

Mi ri-scuserai per la franchezza, ma ti prego di riflettere un po' prima di insistere con la tua linea. Mi dispiacerebbe smettere di risponderti, ma anch'io come tutti ho il tempo contato e mi serve :)

Ciao.

theras
Ritengo garbo e franchezza valori civili importanti,
sopratutto in un momento storico come questo in cui a forza d'urlare e non parlare chiaro stiamo tutti perdendo
buona parte delle virtù che c'hanno reso un grande Paese;
valori civili,dicevo,ancor più che aspetti della buona educazione indispensabili nei comportamenti costruttivi tra estranei:
tu li hai palesati entrambi,con me e pure altri utenti,
ed io come potrei sentire d'aver subito un torto solo perchè non sei d'accordo su quanto ho scritto?
Chiarito questo OT,che ritenevo doveroso con una persona d'evidenti valori,andiamo al pratico:
và bene che sono colpevolmente fuori forma,
ma credo almeno d'essermi messo nella mia verifica in condizioni che non mi permettano di compiere
l'ingenuità di far una sorta di "riduzione agli step precedenti" la quale,chiaramente,
sarebbe insensata nell'intervallo dei numeri reali strettamente compresi tra 2 e 3..
Mi spiego meglio:
io ho preso per buono quanto da te detto a proposito di P(2) e P(3),
e poi ho indagato per $t$$in(2,3)$.
Nel farlo ho ammesso per assurdo l'esistenza d'un $overline(t)=2,c_1c_2cdotsc_ncdots$
(con la successione di cifre decimali ovviamente diverse da quelle di termine generale 0 o 9..)
per il quale $P(overline(t))$ fosse vera;
su quell'ipotesi assurda,
la cui validità non a caso ho esteso solo internamente all'intervallo della cui frontiera abbiamo notizie certe,
ho poi proseguito con maggiorazioni direi lecite,
fin quando non son riuscito a provare che a partire da un certo indice indice sarebbe definitivamente vero che
$f(n,[n/2])<=((n),([n/2]+1))$(1):
questo contrasterebbe il fatto che P(2) è falsa,
e ciò mi confermerebbe che un siffatto $overline(t)$ non può esistere..
Quell'indice l'ho chiamato $n_(overline(u))$,
per risparmiarmi di scrivere troppo spesso $[n/(overline(t)-1)]$ nei coefficenti binomiali;
ma se proprio non ti piace,per motivi che non mi son chiari,lo chiamo $n_(overline(t))$:
quel che conta,in fondo,è che in corrispondenza a $overline(t)$ si riesce a trovare un indice a partire dal quale la (1) è vera definitivamente..
Infine,con franchezza,mi chiedo perchè mi sottoponi il vizio logico nel mio ragionamento da te espresso più volte:
nella mia ipotesi assurda non può essere considerato il caso $t=3!in(2,3)$,
anche perchè altrimenti non sarebbe tanto assurda..
La mia verifica è insomma nata dalla ricerca del motivo per il quale,
assunto per vero quanto da te detto su P(2) e P(3),
non potesse esser vera la P(t) per il valore t=2.999 da te suggerito inizialmente:
ho poi "solo" esteso il ragionamento su quel valore di t,realizzato per assurdo perchè avevo pochi mezzi,
a tutti gli altri punti interni a [2,3]..
Piutosto,ti dicevo,nutro il dubbio che l'avverbio definitivamente sia stato troppo frettoloso;
ci ragionerò e,se sarai ancora interessato,ti farò sapere appena possibile:
da una dozzina di giorni è finito un periodo di sosta forzata e,pur essendo sempre un piacere farlo,
diventa anche per me sempre più dura trovare il tempo per questo eccellente forum che avete tirato sù
(ma và trovato quanto quello per due capolavori che stò rileggendo d'un chimico torinese il quale,
nel periodo più oscuro della recente storia umana,
è riuscito a salvarsi e testimoniare anche grazie alla bontà dei suoi studi.. )!
Saluti dal web.

Ciao :)

Non mi sembra che tu stia dando molto credito alla mia capacità di capire quello che dici. Infatti qui sopra non hai fatto altro che ripetere cose che avevi già detto :)

Ho capito come procedi, e ti ho fatto osservare che il punto in cui sbagli è quando dici che esiste quel [tex]n_{\overline{u}}[/tex] deducendolo dall'esistenza di [tex]n_{\overline{t}}[/tex]. Non c'è nessuna ragione per cui questo [tex]n_{\overline{u}}[/tex] dovrebbe esistere. Comunque tu lo chiami.

In altre parole, chiamo [tex]P(n,t)[/tex] la proposizione seguente: "[tex]f(n,[n/t]) \leq \binom{n}{[n/t]+1}[/tex]".

Tu dici: se esistono [tex]t \in (2,3)[/tex] e [tex]n_t \in \mathbb{N}[/tex] tali che [tex]P(n,t)[/tex] è vera per ogni [tex]n \geq n_t[/tex], allora detto [tex]u := t-1[/tex] esiste [tex]n_u \in \mathbb{N}[/tex] tale che [tex]P(n,u)[/tex] è vera per ogni [tex]n \geq n_u[/tex]. E' questo che dici, giusto? Come dimostri questa cosa?

theras
Eccola la castroneria dietro l'angolo :oops: !!
Ne avevo chiesto venia inizialmente,ed a maggior ragione lo faccio ora:
a te,in primis,ma pure a me stesso,
dato che abbiamo perso tanto tempo per nulla..
Per sintesi ti dico che ho sbagliato ad invertire i versi quando,senza scriverlo,ho fatto questo ragionamento
(formalizzato poi con l'introduzione di $overline(u)$ solo per risparmiarmi,come ti dicevo,di scrivere sempre $overline(t)-1$):
$overline(t)-1 Maledetta fretta :evil: :evil: :
a quel punto insistevo perchè,scartando a priori la possibilità d'un erroraccio del genere,
non capivo perchè le mie maggiorazioni non ti filassero dritte e perchè continuavi ad addebitare al mio ragionamento un vizio logico che,per come tu lo esprimevi,non mi pareva ci fosse..
Va beh,almeno l'arcano incantatore ora è chiarito;
appena termino "Se questo è un uomo" dò un'occhiata più attenta al link da te suggerito,
e se traggo ispirazioni ti faccio sapere:
se riuscissi,tranquillo,rileggerei con attenzione ogni passaggio prima di pubblicartelo :wink:
Grazie per la pazienza
(su quanto ti dicevo all'inizio del mio precedente post è inutile tornare a farlo..):
saluti dal web.

Ah ok :)
"theras":
appena termino "Se questo è un uomo" [...]
Libro bellissimo! Ti consiglio di leggere anche "La tregua" (vedi la mia firma).

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.