La somma di $2^k/k$ è molto divisibile per 2
La somma di $2^k/k$ è molto divisibile per 2
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$?
$$\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
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
Re: La somma di $2^k/k$ è molto divisibile per 2
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?
Re: La somma di $2^k/k$ è molto divisibile per 2
@luca95 potresti dirmi come hai fatto a trovare la generatrice di quella sequenza?
Il problema non è il problema, il problema sei tu.
Re: La somma di $2^k/k$ è molto divisibile per 2
https://www.math.upenn.edu/~wilf/gfologyLinked2.pdf nelle prime pagine viene spiegato il metodo
Re: La somma di $2^k/k$ è molto divisibile per 2
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!
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:
...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
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
Re: La somma di $2^k/k$ è molto divisibile per 2
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.$
Re: La somma di $2^k/k$ è molto divisibile per 2
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}}$
${{\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.
Re: La somma di $2^k/k$ è molto divisibile per 2
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!
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
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
Re: La somma di $2^k/k$ è molto divisibile per 2
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!
"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!
Re: La somma di $2^k/k$ è molto divisibile per 2
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
Indipendentemente dalla sua "utilità", la dimostrazione della tua identità è molto elegante
...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
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
Re: La somma di $2^k/k$ è molto divisibile per 2
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
PS: almeno UN fattore due l'ho trovato
"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!
"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!
Re: La somma di $2^k/k$ è molto divisibile per 2
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
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