<enigma> ha scritto:PS. A te che piacciono queste cose: $ \displaystyle F(x):=\sum _{n \in \mathbb N} f(n) x^n=\prod _{n \in \mathbb N} \frac 1 {1-x^{2^n}} $.
E' la prima cosa che ho pensato, ma di fatto non sono riuscito a cavarci niente..
Nabir Albar ha scritto:Per ogni intero positivo $n$, sia $f(n)$ il numero di modi di rappresentarlo come somma di potenze di 2 con esponente naturale. Rappresentazioni che differiscono solo per l'ordine degli addendi sono considerate uguali. Per chiarire $f(4)=4$, essendo $4=2^2,2+2,2+1+1,1+1+1+1$.
Mostrare che $\forall n\ge 3\ \ 2^\frac {n^2}{4} < f(2^n) < 2^\frac {n^2}{2}$.
Elenchiamo per iniziare i primi valori di $ f(n) $:
$ f(1)=1 $
$ f(2)=f(3)=2 $
$ f(4)=f(5)=4 $
$ f(6)=f(7)=6 $
$ f(8)=f(9)=10 $...
E' immediato vedere che la funzione è crescente, e che:
- se $ n $ è dispari allora $ f(n)=f(n-1) $,poichè nella sua rappresentazione dovrà obbligatoriamente comparire almeno un 1;
- se $ n $ è pari allora $ \displaystyle f(n)=f(n-1)+f\left(\frac{n}{2}\right) $, data dalla somma del numero di combinazioni in cui compare almeno un 1 e da quelle in cui tutti i numeri della rappresentazione valgono almeno 2.
Da quanto detto possiamo quindi dedurre che:
$ \displaystyle f(2^{n+1})=f(2^{n+1}-1)+f(2^n)=f(2^{n+1}-2)+f(2^n)=f(2^{n+1}-3)+f(2^n-1)+f(2^n)=\ldots $ $ \displaystyle =\sum_{1\le i\le 2^n}{ f(i) } $.
In particolare:
$ f(16)=f(8)+2f(6)+2f(4)+2f(2)+f(1)=35 $
$ \displaystyle 2^{\frac{3^2}{4}}<f(2^3)=10<2^{\frac{3^2}{2}} $
$ \displaystyle 2^{\frac{4^2}{4}}<f(2^4)=35<2^{\frac{4^2}{2}} $
Dobbiamo quindi verificare la tesi per ogni $ n\ge 5 $:
1. Upper bound
Supponiamo che la tesi sia verificata per $ f(2^3), f(2^4), \ldots, f(2^n) $. Definiamo $ e(\cdot):\mathbb{Z}\to \{0,1\} $ tale che:
- $ e(x)=1 $ se $ x $ è dispari;
- $ e(x)=0 $ se $ x $ è pari.
Allora $ \displaystyle f(2^{n+1})=\sum_{1\le i\le 2^n}{ f(i) } < \sum_{1\le i\le 8}{ f(i) } +\sum_{4\le j\le n}{ f(2^j) 2^{j-1}}= $
$ \displaystyle =f(2^4)+\sum_{4\le j\le n}{ f(2^j) 2^{j-1}}< $
$ \displaystyle < 2^0+2^1+2^2+2^3+2^4+2^5+\sum_{4\le j\le n}{2^{\frac{(j+1)^2-3}{2}} }< $
$ \displaystyle < 2^0+2^1+2^2+2^3+2^4+2^5+\sum_{4\le j\le n}{2^{\frac{(j+1)^2-3+e(j)}{2}} }< $
$ \displaystyle <2^{\frac{(n+1)^2}{2}} $.
Infatti dati interi non negativi $ a_0<a_1<\ldots <a_k $ risulta sempre verificata $ \displaystyle \sum_{1\le i\le k}{2^{a_i}}\le 2^{a_k+1}-1<2^{a_k+1} $.
2. Lower bound
Supponiamo anche qui che la tesi sia verificata per $ f(2^3), f(2^4), f(2^5), \ldots, f(2^n) $. E osserviamo che per ogni intero $ k>0 $ vale la disuguaglianza:
$ f(2^n+2k)\ge f(2^n)+kf(2^{n-1}) $.
Per $ k=1 $ infatti otteniamo un'identità, e supposta che sia vera per un generico $ k>0 $ allora:
$ f(2^n+2k+2)=f(2^n+2k)+f(2^{n-1}+k+1) \ge f(2^n+2k)+f(2^{n-1}) \ge f(2^n)+(k+1)f(2^{n-1}) $.
Tornando alla tesi originale, abbiamo che:
$ \displaystyle f(2^{n+1})= \sum_{1\le i\le 2^n}{f(i)} > \sum_{2^{n-2}\le i\le 2^n}{ f(i) }= $
$ \displaystyle =f(2^n)+[f(2^n-1)+f(2^n-2)+\ldots+f(2^{n-1})]+[f(2^{n-1}-1)+f(2^{n-1}-2)+\ldots+f(2^{n-2})]> $
$ \displaystyle >f(2^n)+[2^{n-1}f(2^{n-1})+2f(2^{n-2})\sum_{1\le i\le 2^{n-2}-1}{i}]+2^{n-2}f(2^{n-2})> $
$ \displaystyle > 2^{\frac{n^2}{4}}+[2^{\frac{n^2+2n-3}{4}}+2^{n-2}(2^{n-2}-1)2^{\frac{(n-2)^2}{4}}]+2^{n-2}2^{\frac{(n-2)^2}{4}} $
$ \displaystyle > 2^{\frac{n^2}{4}}+2^{\frac{n^2+2n-3}{4}}+2^{\frac{n^2+4n-12}{4}}-2^{n-2}2^{\frac{(n-2)^2}{4}}+2^{n-2}2^{\frac{(n-2)^2}{4}}= $
$ \displaystyle = 2^{\frac{n^2}{4}}+2^{\frac{n^2+2n-3}{4}}+2^{\frac{n^2+4n-12}{4}}> $
$ \displaystyle >2^{\frac{(n+1)^2}{4}} $. []
Ps. Dove l'hai preso?
)
), anche se penso che la difficoltà non sia tanto trovare la relazione quanto darne una stima asintotica. I link rispondono alla tua domanda?
)
), possiamo scrivere (le uguaglianze sono da ritenersi approssimate e valide solo asintoticamente), fermandoci all'ordine di magnitudine $ (\log n )^2 $,