Skip to main content
fix errors
Source Link
András Salamon
  • 2.4k
  • 2
  • 18
  • 33

Expanding on my comments as requested, bounds similar to what you ask for are $2^{n^{i+1}/\log_2(i+1)} \le F(n,i) \le 2^{n^{i+1+1/(e\ln 2)}}$$2^{n^{i+1}/(i+1)} \le F(n,i) \le 2^{n^{i+1+1/(e\ln 2)}}$.

Let $S_i(n) = \sum_{k=1}^n k^i$. To prove the claim, first observe that $\log F(n,i) = \sum_{k=1}^n k^{i+\log\log k/\log k} \ge S_i(n)$, for logarithms of any fixed positive base. Moreover, $S_i(n) \ge n^{i+1}/(i+1)$ by Bernoulli's formula (it is true for small $n$$i$ and the sum of the less significant terms is positive for large $n$$i$). For the other side, $S_i(n) \le \sum_{k=1}^n n^i = n^{i+1}$. The maximum of $\log_b\log_b x/\log_b x$ is at $x=b^e$ and is $1/(e\ln b)$. Hence $\log_2 F(n,i) \le S_{i+1/(e\ln 2)}(n) \le n^{i+1/(e\ln 2)}$$\log_2 F(n,i) \le S_{i+1/(e\ln 2)}(n) \le n^{i+1+1/(e\ln 2)}$.

See also Steven Stadnicki's suggestion to directly use Euler-Maclaurin.

Expanding on my comments as requested, bounds similar to what you ask for are $2^{n^{i+1}/\log_2(i+1)} \le F(n,i) \le 2^{n^{i+1+1/(e\ln 2)}}$.

Let $S_i(n) = \sum_{k=1}^n k^i$. To prove the claim, first observe that $\log F(n,i) = \sum_{k=1}^n k^{i+\log\log k/\log k} \ge S_i(n)$, for logarithms of any fixed positive base. Moreover, $S_i(n) \ge n^{i+1}/(i+1)$ by Bernoulli's formula (it is true for small $n$ and the sum of the less significant terms is positive for large $n$). For the other side, $S_i(n) \le \sum_{k=1}^n n^i = n^{i+1}$. The maximum of $\log_b\log_b x/\log_b x$ is at $x=b^e$ and is $1/(e\ln b)$. Hence $\log_2 F(n,i) \le S_{i+1/(e\ln 2)}(n) \le n^{i+1/(e\ln 2)}$.

See also Steven Stadnicki's suggestion to directly use Euler-Maclaurin.

Expanding on my comments as requested, bounds similar to what you ask for are $2^{n^{i+1}/(i+1)} \le F(n,i) \le 2^{n^{i+1+1/(e\ln 2)}}$.

Let $S_i(n) = \sum_{k=1}^n k^i$. To prove the claim, first observe that $\log F(n,i) = \sum_{k=1}^n k^{i+\log\log k/\log k} \ge S_i(n)$, for logarithms of any fixed positive base. Moreover, $S_i(n) \ge n^{i+1}/(i+1)$ by Bernoulli's formula (it is true for small $i$ and the sum of the less significant terms is positive for large $i$). For the other side, $S_i(n) \le \sum_{k=1}^n n^i = n^{i+1}$. The maximum of $\log_b\log_b x/\log_b x$ is at $x=b^e$ and is $1/(e\ln b)$. Hence $\log_2 F(n,i) \le S_{i+1/(e\ln 2)}(n) \le n^{i+1+1/(e\ln 2)}$.

See also Steven Stadnicki's suggestion to directly use Euler-Maclaurin.

Source Link
András Salamon
  • 2.4k
  • 2
  • 18
  • 33

Expanding on my comments as requested, bounds similar to what you ask for are $2^{n^{i+1}/\log_2(i+1)} \le F(n,i) \le 2^{n^{i+1+1/(e\ln 2)}}$.

Let $S_i(n) = \sum_{k=1}^n k^i$. To prove the claim, first observe that $\log F(n,i) = \sum_{k=1}^n k^{i+\log\log k/\log k} \ge S_i(n)$, for logarithms of any fixed positive base. Moreover, $S_i(n) \ge n^{i+1}/(i+1)$ by Bernoulli's formula (it is true for small $n$ and the sum of the less significant terms is positive for large $n$). For the other side, $S_i(n) \le \sum_{k=1}^n n^i = n^{i+1}$. The maximum of $\log_b\log_b x/\log_b x$ is at $x=b^e$ and is $1/(e\ln b)$. Hence $\log_2 F(n,i) \le S_{i+1/(e\ln 2)}(n) \le n^{i+1/(e\ln 2)}$.

See also Steven Stadnicki's suggestion to directly use Euler-Maclaurin.

Post Made Community Wiki by András Salamon