3
votes
1answer
72 views

Divisor function asymptotics

Define $\tau_{r}(n) = \sum_{d_1...d_r = n}1$. One exercise in a book on sieve theory asked for an elementary proof by induction of the fact that $$\sum_{n\le x}\tau_r(n) = \frac{1}{(r - 1)!}x(\ln ...
1
vote
0answers
28 views

Question about finite sums and integer recursions.

Let $n$ be a positive integer and let $g(n)$ be a given strictly increasing integer function such that $0<g(n)<n$ for all $n$. Also the sequence $ |g(n) - n|$ is unbounded as $n$ grows. Let ...
0
votes
1answer
47 views

Upper bound for the sum $ \sum_{k=1}^N \frac{1}{\varphi(k)}$

Is there an upper bound for the sum $$ \sum_{k=1}^N \frac{1}{\varphi^{\alpha}(k)} $$ where $\varphi(n)$ is the Euler totient function and $\alpha\geq 1$ a real constant? In particular, I'm interested ...
3
votes
1answer
77 views

Asymptotic of a sum evaluation as $ x \to \infty $

Let be the sum $$ \sum_{n\le x}[x/n]=g(x) $$ where $ [x] $ means floor function. My best try for asymptotic is $ g(x) \sim x\log (x)+\gamma x +1$ where I have used the asymptotic $ [x] \sim x $ ...
0
votes
1answer
67 views

Understanding Recurrence Relation

as i ask question and answered by some Clever people at this topic: Recurrence Relation Solving Problem i try to learn new thing with new question very similar to get familiar with recurrence ...
3
votes
1answer
34 views

Asymptotic approximation of a certain sum

During calculations of an expectation of some random variable, I have encountered the following sum: \begin{equation} \sum_{t=2}^{n+1} \frac{t(t-1) \cdot n!}{(n-t+1)!\cdot n^t} \end{equation} I ...
1
vote
1answer
33 views

How to find an asymptotic formula for $f(n)=\sum_{k=1620}^{n}(\log\log\log k)^{2}$?

How to find an asymptotic formula for function given below. $$f(n)=\sum_{k=1620}^{n}(\log\log\log k)^{2}$$
1
vote
1answer
62 views

Bound summation of successive square roots

What is a tight upper bound for $f(n)$ where $f(n) = f(\sqrt{n}) + \frac{1}{n}$. One can easily find the following upper bound $O(\lg \lg n)$, however I'm interested in a tight bound. Regards.
2
votes
1answer
50 views

Compute summation with a relative error of O(n^-2)

$a(n) = \sum_{i \geq 0} a_i n^{-i}$, how can we compute the value of $a(n)^n$ with a relative error of $O(n^{-2})$?
0
votes
1answer
38 views

Find beginning of the asymptotic expansion of the sum

Find beginning of the asymptotic expansion of the sum: $$ (n!)^{-1}\sum^{n}_{k=1}k! $$ against the function $n^{-i}$, for $i\geq0$ to the nearest $\mathcal{O}(n^{-5})$.
0
votes
1answer
87 views

Calculating run times of programs with asymptotic notation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ...
2
votes
1answer
71 views

Help Obtaining an Asymptotic for $\sum_{n=1}^{m-1}\ln(n)\ln(m-n)$

How can I obtain an asymptotic for this partial sum, with an error term of at most $O(m^{1/2}\ln(m))$: $$\sum_{n=1}^{m-1}\ln(n)\ln(m-n)$$ I tried flipping the order of summation half way through to ...
4
votes
0answers
59 views

prime zeta function when $0<s<1$ [duplicate]

I would like to know if there is a good estimate for the sum which concerns all primes not exceeding $x$: $$\sum\limits_{p\leq x}\frac{1}{p^s}$$$$0<s<1$$. Only this. Thanks in advance!
1
vote
1answer
100 views

Mysterious subleading corrections to sums with internal dependence on limit

Is there a standard method for finding expansions in $N$ of sums like $$S(N)=\sum_{n=0}^N \sqrt{N^2-n^2}$$ beyond the first term? It is easy to compute here that $$S(N)=N^2 \int_0 ^1 \sqrt{1-x^2} ...
6
votes
3answers
96 views

Show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$

In this question we are asked to show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$ What I did: $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \sum_{k=2012}^{n} 2^k*1^{n-k}\binom{n}{k} \leq ...
7
votes
3answers
270 views

How to evaluate $\sum\limits_{k=0}^{n} \sqrt{\binom{n}{k}} $

Can we find $$ \sum_{k=0}^{n} \sqrt{\binom{n}{k}} \quad$$ This problem asked me my friend about a year ago, but I didn't know how to attack problem. Now, I am interesting in solution. Any suggestion? ...
0
votes
0answers
46 views

Proving a Certain Inequality that Involves the Sinc Function

Could someone kindly show me how to rigorously prove that there exists a constant $ C > 0 $ such that $$ \forall N \in \mathbb{N}: \quad \sup_{x \in \mathbb{R}} \sum_{\substack{k \in \mathbb{Z} \\ ...
3
votes
1answer
198 views

Asymptotic approximation of sum $\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$

I need to find the asymptotic approximation of this sum $$\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$$ Can you please share a link to theory or hint how it can be solved? Here is my attempt $n ...
0
votes
1answer
202 views

Is this true or false: $\sum_{i=1}^{n} \log(i)$ is the $ \Omega (n\log n)$?

I'm determining if $\sum_{i=1}^{n} \log(i)$ is the $ \Omega (n\log n)$. The summation of the above,$$\sum_{i=1}^{n} \log(i)= \log n!\approx n\log n$$ And checking with big omega $$n\log n \geq c ...
3
votes
1answer
128 views

Asymptotics for sums involving factorials

This question is rather general, but I have recently encountered the following situation in a variety of different settings. Let us suppose that we are given a complicated sum involving factorials ...
7
votes
1answer
94 views

Help proving $\sum_{n\le x}{\ln{n}}=x\ln{x}-x+O(\ln{x})$

Just learning a bit about big O notation and have come across this exercise. The notation used is $$\sum_{n\le x}{\ln{n}}=x\ln{x}-x+O(\ln{x})$$ and I am assuming that is equivalent to ...
0
votes
1answer
95 views

Which form of Euler-Maclaurin formula to use?

This question may be rather elementary, but I am sort of confused about various forms of the Euler-Maclaurin summation formula and their use. For instance, let us suppose that we want to approximate ...
0
votes
2answers
572 views

Big O notation for summation

Consider the summation $$S(n)=1^c+2^c+3^c+...+n^c,$$ where c is some fixed positive integer. (a) Show that $S(n)$ is $O(n^{c+1})$ I did this part the following way, $S(n)$ is $O(n^{c+1})$ because ...
3
votes
2answers
143 views

On proving the convergence of $1/n^2\sum_{1\le k\le n}\varphi(k)$

Let $$\Phi_n=\frac{1}{n^2}\sum_{k=1}^n\varphi(k).$$ How one can show that $\Phi_n$ is convergent sequence? (Here, $\varphi$ denotes the Euler's totient function.) And please, without any monster ...
10
votes
3answers
266 views

Closed form of $\sum\limits_{i=1}^n k^{1/i}$ or asymptotic equivalent when $n\to\infty$

Is there a "closed form" for $\displaystyle S_n=\sum_{i=1}^n k^{1/i}$ ? (I don't think so) If not, can we find a function that is asymptotically equivalent to $S_n$ as $n\to\infty$ ?
3
votes
0answers
61 views

Limit of a sum (no probabilities)

Show that $$\lim_{n\to+\infty}\left(\frac{2}{3}\right)^n\sum_{k=0}^{[n/3]}\binom{n}{k}2^{-k}=\frac{1}{2}$$ without using probabilities. $[\;\cdot\;]$ denotes the integer part.
3
votes
1answer
173 views

Asymptotics of a summation over real valued functions

Let $f$ and $g$ be integrable in $[0,1]$ and $(-\infty, \infty)$ respectively. Let $a_k$ be a divergent series of positive terms and $S_k = a_1 + a_2 + \ldots + a_k$ such that the following ...
3
votes
2answers
153 views

Prove or disprove: $\sum\limits_{i=1}^n i^2 = O(n^2) $

Prove or disprove: $$\sum_{i=1}^n i^2 = O(n^2) $$ If we want to prove this, find some summation that we know the $ O(n)$ runtime for, and is $ O(n^2) $ or smaller. Otherwise, we could disprove ...
7
votes
4answers
265 views

Sum of kth roots ($\sum\sqrt[k]{m}$)

I'm trying to find an asymptotic to $$S(n) = \sum_{k=1}^n\sqrt[k]{m}$$ From computational tests, it seems to grow nearly as slowly as $n$. However even $$\sum_{k=1}^\infty\sqrt[k]{m}-1$$ diverges (for ...
12
votes
2answers
341 views

Asymptotics of the sum of squares of binomial coefficients

We are trying to estimate the cardinality $K(n,p)$ of so-called Kuratowski monoid with $p$ positive and $n$ negative linearly ordered idempotent generators. In particular, we are interesting in the ...
19
votes
7answers
1k views

Is there a formula for $\sum_{n=1}^{k} \frac1{n^3}$?

I am searching for the value of $$\sum_{n=k+1}^{\infty} \frac1{n^3} \stackrel{?}{=} \sum_{n = 1}^{\infty} \frac1{n^3} - \sum_{n=1}^{k} \frac1{n^3} = \zeta(3) - \sum_{n=1}^{k} \frac1{n^3}$$ For which ...
1
vote
1answer
242 views

Sum of the first k binomial coefficients for fixed n

I am reading Remarks on a Ramsey theory for trees by Janos Pach, Jozsef Solymosi and Gabor Tardos. Let $k, d, n \geq 2$ be integers. Somethig interesting happens when $$2^{n/k} > \sum_{i=0}^{d-1} ...
0
votes
1answer
46 views

Questions concerning $\Omega$ and $\Theta$

How do I solve this: $\displaystyle\sum_{k = 1}^n \frac{k}{3}$ is $\Omega(n^2)$? I know that the summation would be $\displaystyle\sum\limits_{k=1}^n \dfrac{n^2+n}{6}$, but how do I solve ...
1
vote
0answers
81 views

Bounding the product of a sequence

I am trying to find an upper bound for the following sequence: $$(1-p_1)(1-(p_1+p_2))\cdots(1-(p_1+\cdots+p_n))$$ with $n$ groups to multiply. I have written it like this: $$\prod_{i=1}^n \left({1 ...
0
votes
1answer
62 views

Finding the limit of a summation in order to find Asymptotic Comlexity [duplicate]

I havent done this in a while so I was hoping someone can remind me how to do this, I need to find the limit of this summation: $$\lim_{n \to \infty}{\displaystyle\sum_{k=1}^{n} \frac{1}{k^2}} $$ ...
1
vote
1answer
111 views

Is the sum always bigger than $n^2$?

Let $s(n)$ an arithmetical function defined as $$s(n)=(p_1+1)^{e_1} (p_2+1)^{e_2} \cdots (p_m+1)^{e_m}$$ where prime factorization of $n$ is $n=p_1^ {e_1} p_2 ^{e_2} \cdots p_m^{e_m}$. (For example, ...
7
votes
3answers
444 views

How to calculate $\sum \limits_{x=0}^{n} \frac{n!}{(n-x)!\,n^x}\left(1-\frac{x(x-1)}{n(n-1)}\right)$

What are the asymptotics of the following sum as $n$ goes to infinity? $$ S =\sum\limits_{x=0}^{n} \frac{n!}{(n-x)!\,n^x}\left(1-\frac{x(x-1)}{n(n-1)}\right) $$ The sum comes from Probability of ...
1
vote
1answer
272 views

Is this why this summation is equivalent to this Theta notation?

So I'm not sure if I misunderstood the lesson or not. $$T(n) =\sum_{j=2}^{n}\Theta(j) = \Theta(n^2) $$ Are these equivalent because: $$ \sum_{j=2}^{n}\Theta(j) = \frac{n(n-1)}2 - \frac{1(1 - 1)}{2} = ...
-1
votes
2answers
2k views

What is the derivative of a summation with respect to it's upper limit?

For the moment, consider the corresponding problem involving integration. Let $s(x)$ be the explicit solution to the following integral. $ \displaystyle s(x)=\int_a^x f(t) \, dt $ The function ...
3
votes
1answer
125 views

Asymptotics of $\sum\limits_{j_1,\ldots, j_{2k}\neq n}\frac{1}{(n-j_1)(n-j_2)\cdots(n-j_{2k-1})(n-j_{2k})}$

How to estimate the following sum in terms of $n$? $$ \sum_{j_1,\ldots, j_{2k}\neq n}\frac{1}{(n-j_1)(n-j_2)\cdots(n-j_{2k-1})(n-j_{2k})}$$ with $n+j_1, j_1-j_2, \ldots, j_{2k}-j_{2k-1}, n-j_{2k} \in ...
5
votes
2answers
2k views

Value of Summation of log(i)

Context: I am learning Dijstra's Algorithm to find shortest path to any node, given the start node. Here, we can use Fibonnacci Heap as Priority Queue. Following is few lines of algorithm: ...
1
vote
2answers
86 views

Can someone prove (or reference) this summation equation from wikipedia?

Wikipedia has a number of equations for approximating a summation. Unfortunately, there are no proofs or references. For example: $$ \sum_{i=1}^n \log(i)^c i^d b^i = \theta(n^d \log(n)^c b^n) $$ for ...
2
votes
1answer
122 views

Asymptotics for sum of binomial coefficients

Could you give me a hint how to find $c$ in the asymptotic for the sum: $$ \sum_{k=0}^{\lfloor {n}/{2} \rfloor}\binom{n-k+1}{k}=(c+o(1))^n $$ and for $$ \max\limits_{a\leq ...
0
votes
1answer
210 views

Techniques for bounding a sum

I have a very messy function. It consists sums four levels deep, and the inner-most term is itself quite messy. $$ \sum \sum \sum \sum (\mbox{stuff})$$ I can't find a closed form for this function. ...