La somma di $2^k/k$ è molto divisibile per 2

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

La somma di $2^k/k$ è molto divisibile per 2

Messaggio da dario2994 »

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$?
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Avatar utente
luca95
Messaggi: 65
Iscritto il: 09 set 2014, 19:19
Località: Firenze, Udine

Re: La somma di $2^k/k$ è molto divisibile per 2

Messaggio da luca95 »

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 :oops:, c'è verso di trovare una formula chiusa o è solo un vicolo cieco?
wall98
Messaggi: 167
Iscritto il: 27 mar 2013, 11:23
Località: Roma

Re: La somma di $2^k/k$ è molto divisibile per 2

Messaggio da wall98 »

@luca95 potresti dirmi come hai fatto a trovare la generatrice di quella sequenza?
Il problema non è il problema, il problema sei tu.
Avatar utente
luca95
Messaggi: 65
Iscritto il: 09 set 2014, 19:19
Località: Firenze, Udine

Re: La somma di $2^k/k$ è molto divisibile per 2

Messaggio da luca95 »

https://www.math.upenn.edu/~wilf/gfologyLinked2.pdf nelle prime pagine viene spiegato il metodo
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: La somma di $2^k/k$ è molto divisibile per 2

Messaggio da dario2994 »

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:
Testo nascosto:
Se avesse un senso (magari modulo $2, 4,\dots$ ce l'ha) di sicuro varrebbe
$\ln(1-2)=\ln(-1)=0$
Ripeto però l'invito a provare a cercare una soluzione olimpica (che magari non usa l'hint) perché di sicuro ce ne sarà una!
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: La somma di $2^k/k$ è molto divisibile per 2

Messaggio da gpzes »

:oops: :oops:
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.$
Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: La somma di $2^k/k$ è molto divisibile per 2

Messaggio da gpzes »

:oops: 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}}$
Ultima modifica di gpzes il 11 ago 2015, 00:33, modificato 1 volta in totale.
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: La somma di $2^k/k$ è molto divisibile per 2

Messaggio da dario2994 »

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 :o 8)

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!
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: La somma di $2^k/k$ è molto divisibile per 2

Messaggio da Lasker »

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$
Ultima modifica di Lasker il 11 ago 2015, 00:10, modificato 1 volta in totale.
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!
dario2994
Messaggi: 1428
Iscritto il: 10 dic 2008, 21:30

Re: La somma di $2^k/k$ è molto divisibile per 2

Messaggio da dario2994 »

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 :D
...tristezza ed ottimismo... ed ironia...
Io ti racconto lo squallore di una vita vissuta a ore di gente che non sa più far l'amore...
"Allora impara a fare meno il ruffiano. Io non lo faccio mai e guarda come sono ganzo" Tibor Gallai
Avatar utente
Lasker
Messaggi: 440
Iscritto il: 02 mag 2013, 20:47
Località: Udine

Re: La somma di $2^k/k$ è molto divisibile per 2

Messaggio da Lasker »

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 :lol: ) 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 :lol:
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)

"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)

Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?

PRIMA FILA TUTTI SBIRRI!
Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: La somma di $2^k/k$ è molto divisibile per 2

Messaggio da gpzes »

:oops: ho editato formula perchè piccolo typo :oops: ...non lo crederà nessuno ma anche io avevo pensato come il buon Lasker :wink: ...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 :wink:
Ad ogni modo ci ho passato la nottata a cercare quella formula ufff :mrgreen: ..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 :shock:

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