Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.

learn more… | top users | synonyms (1)

4
votes
1answer
73 views

How to show $\sum_{i=1}^{n-1} \frac{i(n-2)!}{(n-1-i)!n^{i+1}} \sim 1/n$

How can one compute the large $n$ asymptotics of $$\sum_{i=1}^{n-1} \frac{i(n-2)!}{(n-1-i)!n^{i+1}}\;?$$ My guess is that it is $1/n$ but I don't know how to show that.
6
votes
2answers
88 views

How to show that $\sum_{x=1}^\infty \prod_{i=1}^{x-1} (1-i/n) \sim \sqrt{\frac{\pi n}{2}}$?

How can one show that asymptotically $$\sum_{x=1}^\infty \prod_{i=1}^{x-1} \left(1-\frac{i}{n}\right) \sim \sqrt{\frac{\pi n}{2}} \; ?$$ A non rigorous argument is to say that for large $n$, ...
1
vote
2answers
59 views

Finding an approximation for the difference of $a_n = \frac{1}{1+a_{n-1}}$ and it's limit.

I've got the recurrence $\displaystyle{a_{n} = {1 \over 1 + a_{n - {\tiny 1}}},\ }$ for $0 < a_{0} < 1 $ which has the solution $\displaystyle{\alpha = {\,\sqrt{\, 5\,}\, - 1 \over 2}}$ I am ...
8
votes
1answer
545 views

Good resource/exercises for learning asymptotic analysis?

I am studying asymptotic methods right now; things such as mellin transform, inverse mellin transform, saddle point method, laplaces method, etc... and I get very frustrated because I can't get very ...
7
votes
3answers
198 views

Asymptotic for sum

How can I find formula for $\displaystyle{\sqrt[3]1 + \sqrt[3]2 + \sqrt[3]3 + \cdots + \sqrt[3]n}$ with an accuracy ${\rm O}\left(\, 1 \over \vphantom{\LARGE A}n^{5}\,\right)$ Is here we should use ...
13
votes
1answer
282 views

Upper bound for the widest matrix with no two subsets of columns with the same vector sum

Over at PPCG there is an ongoing contest going on to find the largest matrix without a certain property, called property $X$. The description is as follows (copied from the question). A circulant ...
1
vote
1answer
109 views

Asymptotic relation between specific binomial coefficient and exponential function

I need to determine the asymptotic relationship between the functions: $$f_1(n)={n\choose{\lfloor{n\over{2}}\rfloor}}, f_2(n)=7^{\sqrt{n}}$$ (I'm going to just assume $n$ is always even.) I've ...
3
votes
1answer
67 views

Does $\theta(n)$ = $1/x$ make any sense?

So, I asked this question on a discrete structures exam today, which I apparently didn't give enough thought to: $f(x) = (5x^2 + 6x + 2)/(x^3 + 4x^2 +x)$ Find the correct theta notation for the ...
1
vote
0answers
40 views

Order of magnitudes comparisons

I need your help with the following. I need to determine how to order (functions) the following : \begin{align} &f(x)=(x/2)^{(x/2)} \\ &g(x)=x! \end{align} Note: I got both of them are ...
4
votes
1answer
124 views

Growth of ratio based on sum of squared binomial identity

It is a well-known identity that $$\binom{n}{0}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{2n}{n}.$$ By symmetry of the binomial coefficients, this means the ratio ...
2
votes
1answer
168 views

Number of words not having a subword of length k with only one letter

Let $f_k(n,t)$ be the number of words of length $t$ over the alphabet $\mathcal{A} = \{1,\ldots,n\}$ such that no word contains $i^k$ as a substring for $i \in \mathcal{A}.$ I am looking to find the ...
3
votes
1answer
140 views

Corollaries of Green-Tao Theorem?

there is already a good thread which discusses some corollaries of the Green-Tao Theorem, here: Constructing arithmetic progressions The question I was wondering about is of a similar flavor but ...
-1
votes
1answer
27 views

big $\Theta$ question dealing with $\log_2{n}$ and $\log_{10}{n}$

Show that $\log_{10}{n} = \Theta(log_2{n})$. I know that I have to show that 1) $\log_{10}{n} = O(\log_2{n})$ show: $\log_{10}{n} \le C * \log_2{n}$ and 2) $\log_2{n} = O(\log_{10}{n})$ show: ...
0
votes
1answer
29 views

Big oh / big theta proof for the following

Find a number $a$ with $s(n) = \Theta(a^n)$ for $s(n) = (\log_2{10})^{(n-3)}$. I'm not quite sure how to proceed. I was having problems with another problem trying to figure out what it means to ...
0
votes
2answers
51 views

Why is Wolfram missing so many oblique asymptotes? (Not only about Wolfram in thread)

Few days ago I made a post, and to be frank I'm not sure if I'm even having this question in the right forum. But I'm also looking for information on if my thoughts are correct. Observe this little ...
0
votes
1answer
37 views

Big oh proof for a(n) using big oh hierarcy

So I'm given the following big-oh hierarchy (each sequence is big-oh of any seqeuence to its right.) $1$, $\log_2{n}$, ... , $\sqrt[4]{n}$, $\sqrt[3]{n}$, $\sqrt{n}$, $n\log_2{n}$, $n\sqrt{n}$, ...
0
votes
1answer
42 views

Proving big oh for a function

Find a $C$ and $k$ such that $\sqrt{n^2 - 1}$ = $O(n^k)$. My professor has stated that there are two different $k$'s. One from the problem statement and one from the definition of big-oh. I know that ...
1
vote
3answers
86 views

Finding the limit of: $\lim_{x\rightarrow +\infty}\left(x\arctan x-x\dfrac{\pi}{2}\right)$

$\lim_{x\rightarrow +\infty}\left(x\arctan x-x\dfrac{\pi}{2}\right)$ I just removed a lot of unnecessary text from this post. If anyone could tell me how to find this limit, without L'Hôpital's rule, ...
3
votes
1answer
33 views

Oblique asymptote for: $f(t) = \frac{t^2\arctan t}{t-4}$?

Say a function $$f(t) = \frac{t^2\arctan t}{t-4}$$ Obviously, this has a vertical asymptote at $t = 4$. However, the oblique asymptote, if there is one, I can't seem to find. What I do is I put the ...
1
vote
2answers
324 views

Find the leading order asymptotic behaviour of the integral

$$I(x) = \int_0^{\infty}e^{-t-\frac{x}{t^2}}dt \mbox{ as } x \mbox{ tends to infinity} $$ I know this has a moveable maximum so you need to make a substitution which transforms it into the integral: ...
2
votes
1answer
91 views

Calculate the leading order asymptotic behaviour (with two maxima)

thanks in advance! Calculate the leading-order asymptotic behaviour of the integral $$I(x) = \int_{0}^{2\pi} (1+t^2) e^{x \cos t} dt \mbox{ as } x \mbox { tends to infinity}$$ So far I know there ...
0
votes
1answer
28 views

How to prove this asymptotic bound? [closed]

Given that $0<a<b$, $f(n) \in O(n^a)$, prove that $f(n) \in o(n^b)$ (note there is a difference between big o and little o)
2
votes
0answers
32 views

Number of ways to visit each cell of $n\times n$ board once

A piece lies on the upper-left corner of an $n\times n$ board. Let $f(n)$ denote the number of ways to move the pieces one step horizontally/vertically at a time, so that it visits each field of the ...
2
votes
1answer
43 views

Asymptotics of $\frac{1}{n} \sum_{ d|n } \mu{\left(\frac{n}{d}\right)} 2^d $

Define $$a(n) = \frac{1}{n} \sum_{ d|n } \mu{\left(\frac{n}{d}\right)} 2^d $$ where $\mu()$ is the Möbius function. Is it possible to find easily computable $b, c$ such that $b(n) \leq a(n) \leq ...
3
votes
3answers
102 views

Iterated integer-valued decimation

This question is for those who have wondered what it means to decimate an army when the number of soldiers is not a multiple of ten. I am interested in really good upper bounds on the length of a ...
0
votes
1answer
28 views

Lower bounds for an expression of two positive integers?

Can we get an approximate lower bounds for the following expression: $$\left( 1 + \frac{1}{ 2 \left( \frac{4^{nC}-1}{2^n-1} \right) } \right)^{ \frac{1}{\left( \frac{4^{nC}-2^{nC}}{2^n-1} \right) } ...
1
vote
0answers
29 views

Calculate the leading-order asymptotic behaviour (Laplace's Method) [duplicate]

thanks in advance! Calculate the leading-order asymptotic behaviour of the integral $$I(x) = \int_{0}^{2\pi} (1+t^2) e^{x \cos t} dt \mbox{ as } x \mbox { tends to infinity}$$ So far I know there ...
0
votes
2answers
43 views

Show that $3n^2 - n+4$ is $O(n^2)$

From the definition of big oh: We say that "$f(n)$ is big oh $g(n)$" if there exists an integer $n_0$ and a constant $c>0$ such that for all integers $n\geq n_0$, $f(n)\leq cg(n)$. Substituting ...
0
votes
2answers
18 views

Determine the asymptotic behavior of $f(n)$ in relation to $g(n)$

$f(n)=n^\sqrt{n}, g(n)=2^n$ $f(n)=10^{\log\log n}, g(n)=\log n$ Note: $\log$ is in base 2. For section #1, I tried to evaluate the limit $\lim_{n\to\infty} \frac{2^n}{n^\sqrt{n}}$ but got stuck ...
1
vote
0answers
124 views

How to prove that a function f(x) is O(g(x)), using the definition (finding C and k)

We say that $f(x)$ is $O(g(x))$ if $$(∃C ∈ \mathbb(R)❘)(∃k ∈ \mathbb(R)❘)(∀x ∈ \mathbb(R)❘)$$ $$(x ≥ k → |f(x)| ≤ C · |g(x)|)$$ In English: We can find $C$ and $k$ so that, once we get past the “small ...
1
vote
1answer
55 views

Asymptotic solution to a differential equation near zero

I am trying to get the both the asymptotic solutions of the equation $y''(x)=\sqrt{x} \cdot y(x)$ as $x\rightarrow 0$. But when I put $y(x)=\exp(S(x))$ since $x=0$ is an irregular singular point, no ...
0
votes
1answer
70 views

$\frac{a_n - a_{n+1}}{a_n} \approx \frac{1}{n}$? (part of 2010 Putnam exam)

Given a non-negative sequence $a_n$, strictly decreasing and tending to zero, can we show that (for large $n$) $$ \frac{a_n - a_{n+1}}{a_n} \approx \frac{a_n}{na_n} = \frac{1}{n} \text{ }?$$ ...
2
votes
1answer
51 views

Finding an upperbound on $f(n)$

I am stumped trying to prove that there exists a real number $c$, such that $f(n)\leq cn^4$ for most natural numbers $n$. $$f(n) = \left\{ \begin{array}{ll} 10, &n=10\\ ...
1
vote
2answers
233 views

Solving $T(n)= 2T(n/2) + \sqrt{n}$ without master theorem (algebraically & recurrence tree)

$$T(n)= 2T(n/2) + \sqrt{n}$$ This recurrence was in a stackoverflow question, and I want to solve it without relying on the master method. The solution was given, but wolframAlpha gives a slightly ...
0
votes
1answer
33 views

Prove that $\log^\alpha n = o( a^n )$

Please, how to prove: $\forall c \in \mathbb R_+$ $\exists n_0 \in \mathbb N_+$ $\forall n \ge n_0 :$ $log^\alpha n < c \cdot a^n$ for $ \\a>1$, $\alpha \in \mathbb R$ ? Thanks
0
votes
1answer
45 views

Solving $T(n) = 8T(\lfloor \frac{n}{2}\rfloor) + 1$ using Akra-Bazzi

I was trying to apply Akra-bazzi to solve $T(n) = 8T(\lfloor \frac{n}{2}\rfloor) + 1$ but I was having some issues. I was told that the correct way to solve it to express the floor in the form (for ...
0
votes
1answer
100 views

Proof of simple relation involving near primes?

Motivation (can skip!). (*) $\sum\log n \approx n\log n-n,$ and $$\sum\log n = \sum_{p_1\leq n} \log p_1+\sum_{p_2\leq n} \log p_2+...+\sum_{p_m\leq n} \log p_m$$ in which $p_k$ are numbers comprised ...
0
votes
0answers
50 views

Binomial series using gamma function

I am trying to find a formula of this online but am having a lot of trouble. In my textbook (Bender and Orszag), they make the following transformation for small $t$: ...
1
vote
1answer
44 views

Limit of multivariate polynomial with large arguments

If I have a polynomial $f(x,y)=x^4+y^4-4xy$, how would I go about showing that as the standard norm of $(x,y)$ goes to infinity, $f(x,y)$ goes to infinity?
4
votes
2answers
52 views

What can we say about the rate of growth of a function growing faster than all polynomials?

Suppose $f: \mathbb{R} \rightarrow \mathbb{R}$ satisfies the following: $$ \forall k \in \mathbb{N} \hspace{5pt} \lim_{t \rightarrow \infty} \frac{t^k}{f(t)} = 0.$$ Can we deduce a stronger growth ...
0
votes
1answer
25 views

Simple Question: division of sums

I am a little bit confused about the following simple task. Given some functions $f(x), g(x), h(x), l(x), m(x)$. We know that $\frac{f(x)}{g(x)}= m(x)$. We further know that $h(x), l(x)$ are ...
0
votes
1answer
22 views

How to deal with such inequalities?

I have that $$ Y \geq n e^{- 1- t \log t + o(1)}$$ and $$Y \leq n e^{\log n +t - t \log t}.$$ Now I would like to find values $t_0(n)$ and $t_1(n)$ such that $$Y \rightarrow 0 \text{ for all } t ...
1
vote
0answers
40 views

Asymptotic expansion of $(\text{log}(1+x))^2$

How can I find asymptotic expansion of the function $(\text{log}(1+z))^2$ with respect to the asymptotic scale $\{z^{-m}, z^{-n}\text{log}(z), z^{-p}\text{log}^2(z), m,n,p=0,1,2,...\}$ while ...
0
votes
1answer
35 views

Prove asymptotic bound by the substitution method

I need to prove that $T(n) = 4T(n/2) + n^2lgn = \mathcal{O}(n^2lg^2n)$ by using the substitution method. Unfortunately, I'm not able to identify the error in my train of thought. For the problem at ...
1
vote
1answer
56 views

Asymptotic expansion of the integral $\int_0^1 e^{-x/t} dt$ for $x \to 0$

How to get the asymptotic expansion for the integral $$\int_{0}^{1}\exp(-x/t)dt$$ in the limit $x\rightarrow 0$ ? I took $x/t=u$ and did integration by parts (IP) but if I keep doing IP, I get a ...
3
votes
1answer
42 views

Is the Pattern in the Number of Digits in the Bernoulli Numbers Showing Something Significant

For the first couple of powers of $10$, the number of digits in these show a certain pattern, is this a coincidence or is their a reasonable explanation. Specifically if we look at $$ \lfloor ...
2
votes
0answers
76 views

Difficulty with Asymptotic Expansion of $\int_{0}^{1}\sqrt{t}e^{ixt}dt$

In the book Advanced Mathematical Methods for Scientists and Engineers by Bender and Orszag (question 6.50) we are asked to compute the asymptotic expansion of $\int_{0}^{1}\sqrt{t}e^{ixt}dt$ fully. ...
0
votes
1answer
51 views

laplace method on this integral

How to get the leading asymptotic expansion for this integral $\int_{0}^{\pi/2}\sqrt{\sin(t)}\exp(-x\sin^4(t))dt $ in the limit $x\rightarrow\infty$ ? Because the maximum of the exponent is at $t=0$ ...
0
votes
1answer
76 views

Asymptotic expansion of $\sin\left(\pi + \exp(-1/\epsilon)\right)$

I need to find the two term asymptotic expansion of $\sin\left(\pi + \exp(-1/\epsilon)\right)$ as $\epsilon$ tends to zero, but the exponential term is confusing me...
0
votes
1answer
65 views

Asymptotic Expression for the Twin Prime Counting Function

A variation on a previous question I asked, which has garnered no responses. I'll attempt to be more lucid: Let $\pi_2(x)$ be the twin prime counting function and $\pi(x)$ be the prime counting ...