OliForum Matematico

Siano $a,b$ numeri naturali coprimi tali che
$$\frac ab = \frac 21+\frac {2^2}2+\frac {2^3}3+\cdots+\frac {2^{10^9-1}}{10^9-1}+\frac {2^{10^9}}{10^9}$$
Dimostrate che $2^{10^9}\mid a$. Sapete dire quanti fattori $2$ ha esattamente $a$?

Definendo $ \displaystyle a_n=a_{n-1}+\frac{2^n}{n} $ e $ a_0=0 $ ho trovato che l'ogf della sequenza è $ \displaystyle \frac{1}{x}+\frac{1}{1-2x} $ ma da qui non so più come procedere , c'è verso di trovare una formula chiusa o è solo un vicolo cieco?

@luca95 potresti dirmi come hai fatto a trovare la generatrice di quella sequenza?

https://www.math.upenn.edu/~wilf/gfologyLinked2.pdf nelle prime pagine viene spiegato il metodo

Non mi pare che quella da te scritta sia la corretta funzione.
Quella giusta dovrebbe essere tipo $\frac{\ln(1-2x)}{x-1}$.

Comunque, la speranza di trovare una "formula chiusa" non so se sia ben riposta (ma non escludo che ci sia una forma (chiusa o meno) che renda esplicita la richiesta del problema).

Il problema è difficile e vorrei dare un hint sensato se ne fossi munito. La soluzione che conosco io non è olimpica, ma credo e spero ce ne possa essere anche una olimpica. In ogni caso vi scrivo un hint che serve per la soluzione che conosco e forse può servire anche in una più elementare: Ripeto però l'invito a provare a cercare una soluzione olimpica (che magari non usa l'hint) perché di sicuro ce ne sarà una!

Non saprei…intanto posto questo…
Sia $c={{10}^{9}}$. Moltiplichiamo ambo i membri per $c!$ (fattoriale).
$(c!)\cdot \frac{a}{b}=(c!)\cdot \left( \frac{2}{1}+\frac{{{2}^{2}}}{2}+\frac{{{2}^{3}}}{3}+\cdots +\frac{{{2}^{{{10}^{9}}-1}}}{{{10}^{9}}-1}+\frac{{{2}^{{{10}^{9}}}}}{{{10}^{9}}} \right)$ (*)
Il RHS di (*) è sicuramente un numero naturale. Ma allora LHS deve essere naturale.
Poiché $a$ e $b$ sono coprimi dovrà essere $b/\left( c! \right)$.
Fatto(1): La massima potenza $e$ di 2 che divide $c!$ è data dalla formula di Legendre (de Polignac?) $n!=\prod\limits_{p\le n}{{{p}^{\sum\limits_{k=1}^{\infty }{\left\lfloor n/{{p}^{k}} \right\rfloor }}}}$ , ossia $e=\sum\limits_{k=1}^{\infty }{\left\lfloor c/{{2}^{k}} \right\rfloor }$ , dove le quadre sono la Floor function.
Il Fatto (1) ci dice che ${{2}^{e}}/(c!){{,2}^{e+1}}||(c!)$ .
Indichiamo con ${{e}_{i}}$ gli addendi di $e=\sum\limits_{k=1}^{\infty }{\left\lfloor c/{{2}^{k}} \right\rfloor }=\sum\limits_{k=1}^{m}{{{e}_{i}}}$. Ossia ${{e}_{m}}=\left\lfloor c/{{2}^{m}} \right\rfloor \Rightarrow {{2}^{m+1}}||c$.
La “successione” ${{({{e}_{i}})}_{i=1...m}}$ è debolmente decrescente e ${{2}^{{{e}_{i}}}}\le c,\forall i=1...m$ (perché “aumentano” i denominatori).
Analizziamo meglio gli addendi al RHS di (*).
Sono della forma ${{2}^{j}}\cdot \frac{c!}{j}\ ,\ j=1...c$: Contiamo le potenze di 2 in ogni addendo.
Poiché compare un denominatore $j$ , tutte le volte in cui $j={{2}^{r}}\cdot q\ ,\ (q,2)=1\ ,\ \ q\ge 1\ ,\ 0\le r\le m$ avrò $e-r+j$ potenze di 2 al numeratore. Ma per Bernoulli, $e-r+j=e+j-r\ge e+1$.
Allora ogni addendo di RHS di (*) ha almeno $e+1$ potenze di 2!!
Ma LHS di (*) ha potenze di 2 come massimo $e$, nel fattore $\frac{c!}{b}$.
Se il termine $b$ fosse pari, le altre potenze di 2 fino ad $e$devono essere generate dal termine $a$ di LHS. Ma $a$ e $b$ sono coprimi. Allora tutte le potenze di 2 fino a $e+1$ sono generate dal termine $a$ di LHS.
In sintesi, il termine $b$ deve essere formato da tutti i fattori dispari di $c!$.
Tutto ciò premesso, dobbiamo dimostrare che il numero totale di potenze di 2 è pari a ${{2}^{c}}$.
Con la notazione utilizzata sappiamo già che ${{e}_{m}}=\left\lfloor c/{{2}^{m}} \right\rfloor \Rightarrow {{2}^{m+1}}||c\xrightarrow{Bernoulli}m+1\le {{2}^{m}}\le c.$

ho trovato questa identità curiosando qua e là..ma qui mi fermo

${{\sum\limits_{k=0}^{n}{\left( \begin{align}
& n \\
& k \\
\end{align} \right)}}^{-1}}=\frac{n+1}{{{2}^{n+1}}}\sum\limits_{k=1}^{n+1}{\frac{{{2}^{k}}}{k}}$

Mentre il tuo primo post dubito sia d'aiuto, l'identità che hai trovato secondo me porta agilmente a concludere con un goccio di furbizia

Prova a mostrare che l'LHS è un numero razionale il cui denominatore ha "pochi" fattori 2... da questo prova a dedurre la tesi... magari guardando ad una somma ancora più lunga di quella considerata nel testo...

p.s. comunque anche dimostrare tale identità potrebbe essere un bell'esercizio!

Quest'ultima frase di dario2994 mi dà il terribile dubbio di essermi perso per un mese (!) in un bicchier d'acqua, dopo aver trovato quasi per caso una bella identità con denominatori TUTTI DISPARI! La metto in caso possa servire a qualcuno (io, ripeto, non ho trovato idee sensate per continuare e questa via l'ho scartata, ma magari...); l'ho trovata con metodi rozzi e leggermente MNE, ma forse si dimostra con belle idee combinatoriche che vengono solo se si è bravi sul serio.

pensieri di inizio luglio ha scritto:Allora, il $10^9$ non sembra essere così rilevante ai fini del problema, quindi intanto lo sostituisco con un generico $n$ e definisco inoltre (per ogni $n$) $A_n= \sum_{k=1}^n \frac{2^k}{k}$. Un primo passo dovrebbe essere riscrivere decentemente la nostra sommatoria

Lemma della somma: Dimostriamo innanzitutto che si ha:
$$A_n=2\sum_{k \textrm{ dispari}}^n\frac{{n\choose k}}{k}$$

Dim: Per ogni $x$ diverso da $1$ (e forse $0$? Qui sono un po' mah, ma l'identità che trovo alla fine sembra vera quindi spero di no... forse un minimo si aggiusta integrando tra un numero $\varepsilon$ appena appena maggiore di $0$ per avere meno casini come $0^0$ ) si ha
$$\frac{1-x^n}{1-x}=\sum_{k=0}^{n-1} x^k$$
Integrando entrambi i membri rispetto ad $x$ tra $0$ e $2$ ottengo dunque l'uguaglianza
$$\int_{0}^2 \frac{1-x^n}{1-x}\textrm{d}x=\left[\sum_{k=0}^{n-1} \frac{x^{k+1}}{k+1}\right]_0^2=\sum_{k=1}^n \frac{2^k}{k}-\sum_{k=1}^n \frac{0^k}{k}=A_n$$
Dunque, visto che al RHS compare proprio $A_n$, cerchiamo di trovare il valore del LHS in un altro modo. L'idea giusta è procedere per sostituzione, ponendo $t=1-x$ (da cui $\textrm{d}t=-\textrm{d}x$):
$$A_n=\int_{0}^2 \frac{1-x^n}{1-x}\textrm{d}x=\int_{1}^{-1}\frac{1-(1-t)^n}{t}\cdot(-\textrm{d}t)=\int_{-1}^1\frac{1-(1-t)^n}{t}\textrm{d}t $$
Adesso sviluppiamo con il teorema binomiale, ottenendo
$$A_n=\int_{-1}^1\frac{1-\sum_{k=0}^n {n\choose k}\cdot(-t)^k\cdot(1)^{n-k}}{t}\textrm{d}t=\int_{-1}^1 \sum_{k=1}^n{n\choose k}\cdot(-t)^{k-1}\textrm{d}t$$
Portando la sommatoria fuori dall'integrale (i suoi termini sono costanti in $t$) si ha dunque
$$A_n=\sum_{k=1}^n {n\choose k}\cdot \int_{1}^{-1} (-t)^{k-1}\cdot (- \textrm{d}t)=\sum_{k=1}^n {n\choose k}\cdot\left[\frac{(-t)^k}{k}\right]_{1}^{-1}=\sum_{k=1}^n {n\choose k}\cdot \left[\frac{(1)^k-(-1)^k}{k}\right]$$
Ed è evidente che per $k$ pari l'espressione fra parentesi si annulla, mentre per $k$ dispari si ottiene un fattore $2/k$, da cui
$$A_n=\sum_{k \textrm{ dispari}}^n {n\choose k}\cdot \frac{2}{k}=2\sum_{k \textrm{ dispari}}^n\frac{{n\choose k}}{k} $$
E quindi la tesi del lemma è dimostrata $\blacksquare$

Purtroppo l'identità che hai trovato, pur essendo abbastanza inaspettata, non mi sembra sia comoda quanto quella di gpzes. Infatti la sua ha quel meraviglioso fattore $2^{n+1}$ che torna molto comodo!
Indipendentemente dalla sua "utilità", la dimostrazione della tua identità è molto elegante

Non posso negare che sospettavo una cosa del genere (se avessi trovato una qualche continuazione avrei postato prima)... della procedura che ho usato mi è piaciuto soprattutto il fatto che non sapevo dove sarei arrivato e che la scrittura relativamente compatta finale è frutto del caso più che di una mia premeditazione! Comunque le cose che ho scritto sullo $0$ sono posticce, le ho aggiunte adesso in una condizione psicofisica non proprio ottimale (è mezzanotte passata ) quindi non so se hanno veramente senso, in caso qualcuno lo scriva. Il problema sembra molto bello in sé, comunque, ci ho pensato a lungo senza cavarci nulla e sicuramente sarà istruttivo, visto che di problemi simili non ne ho visti molti (nessuno?).

PS: almeno UN fattore due l'ho trovato

ho editato formula perchè piccolo typo ...non lo crederà nessuno ma anche io avevo pensato come il buon Lasker ...chiaramente bisogna aver visto un po' di Integrali...l'unica cosa bisogna stare attenti ad integrali impropri..come in questo caso...bisognerebbe vedere convergenza in 1 da destra e sinistra..ma okk..anche graficamente devono tornare conti
Ad ogni modo ci ho passato la nottata a cercare quella formula ufff ..fra integrali immediati e somma di coefficienti binomiali qualcosa doveva esserci ..per non parlare di espansioni 2-adiche ufff...
Comunque ci sono tante formule che non sono direttamente riconducibili a metodi combinatoriali semplici..spesso sono risultati d'integrazione e posteriormente si trovano collegamenti...ci fanno tanto ricerca

I problemi più difficili ma sicuramente più belli sono casi particolari di risultati avanzati e cercare una soluzione "elementare" è forse ancor più affascinante
Magari metto uno dei miei soliti link..ma non so ..ai più intimi magari