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

learn more… | top users | synonyms (1)

23
votes
0answers
477 views

On the number of complete and gap-free compositions

This is a longish post about something that has been haunting me for a while about a kind of restricted composition, namely gap-free and complete compositions. First, I will define the terms that are ...
9
votes
0answers
313 views

Asymptotic related to the infinite product of sine

The amount is somewhat complicated ($x$ is a constant): $$S_n=\sum_{k=1}^n\ln\left(1-\frac{\sin^2\big(x/(2n+1)\big)}{\sin^2\big(k\pi/(2n+1)\big)}\right)\tag{*}$$ I want to enrich my handy powerful ...
9
votes
0answers
88 views

Asymptotic behavior of $|f'(x)|^n e^{-f(x)}$

Let $f$ be a strictly convex function on $\mathbb R$, $f'' \geq C > 0$. Let $n$ be a positive integer. What can we say about the growth rate of $|f'(x)|^n e^{-f(x)}$ as $x\rightarrow \infty$? Must ...
8
votes
0answers
132 views

Let $x_n$ be the (unique) root of $\Delta f_n(x)=0$. Then $\Delta x_n\to 1$

Note that by Cesaro's Theorem, we have as a consequence $$\frac{x_n}n\to 1$$ Consider $$r_n(x)=e^{-x}-\sum_{k=0}^n (-1)^k\frac{x^k}{k!}$$ and $$f_n(x)=(-1)^{n+1}e^{-x}r_n(x)$$ One can argue by ...
6
votes
0answers
60 views

Asymptotic property of integral involving Bessel function.

Consider the following integral $$ I(s)=\int_{0}^{\infty}{J_{\frac{n-2}{2}}}(sr)r^{A+1}(e^{-r^{2\alpha}}-1)dr, $$ where $J_{\frac{n-2}{2}}$ is the Bessel function of order ${\frac{n-2}{2}}$, $s, A, ...
6
votes
0answers
49 views

Partitioning points with a line

Let $A_{m, n} = \{1, 2, \dots, n\} \times \{1, 2, \dots, m\}$. A straight line would partition the points into two sets. How many ways are there to do it? Let $p_{m, n}$ be that number. Apparently ...
6
votes
0answers
166 views

Hints/Help studying an Abel Differential Equation

I want to know more than qualitative information about the Abel differential equation $\frac{dy}{dx}+y^3+x=0$. $\qquad ... \;(1)$ Since I don´t know how to solve this and as far as could see, this ...
6
votes
0answers
143 views

An integration to first order

I am having some trouble evaluating an integral -- involving taking an approximation. It would be great if someone could help me. I wish to evaluate $$\int_0^\pi {\cos\theta\cos \left[\omega ...
5
votes
0answers
163 views

An entire function of strict order 2

Here is a problem from Stein and Shakarchi Complex Analysis, can somebody help me to solve it? I guess we can use Phragmen-Lindelof theorem but I don't know the exact way. Suppose $f(z)$ is an entire ...
5
votes
0answers
90 views

Binomial asymptotic.

Is there any "direct" proof of the following asymptotic inequality: let $\alpha\le 1$ and consider $$Q_n(x)=\sum_{k=1}^n\frac{\alpha(\alpha+1)(\alpha+2)\cdots(\alpha+k-1)}{k!}x^k$$ Then, $$\int_0^1 ...
5
votes
0answers
178 views

Sums of Dirichlet-Characters over prime numbers (part 2)

This is kind of related to my previous question that was poorly stated because of misreading my own notes that I have taken on the papers I am currently reading, so no surprise that it eventually ...
4
votes
0answers
52 views

Closed form or asymptotic expansion for $\int_0^m \frac{n^x}{\Gamma(x+1)}dx$?

$$\int_0^m \frac{n^x}{\Gamma(x+1)}dx:n,m \in \mathbb{R}$$ I'm dubious as to whether there's a closed form for the above, if there is I'll be very happy. Otherwise: Is there a closed form for ...
4
votes
0answers
55 views

Asymptotic expansion of $\zeta(s)$

It is well known that $$ \zeta(s) = \sum_{n = 1}^\infty \frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}}, \quad \Re[s] > 1, \tag{1}$$ but, if $p \leq N$ denotes the primes less than or ...
4
votes
0answers
86 views

Prove that a series is $O(t^a)$.

Consider the series $$ u(t,x) = \sum_{i \geq 1} {u_i(x) t_1^i } + \sum_{i+2j \geq k+2, j\geq 1} {\varphi_{i,j,k}(x) t_1^i t_2^j y^k} $$ where $t \in \tilde{\mathbb{C} \setminus \{ 0 \}}$, $x$ is ...
4
votes
0answers
143 views

Double harmonic summation

I am interested in determining an asymptotic formula for the double summation of $1/(ab)$, where $a$ is an odd integer ranging between 1 and $k/\sqrt{j}$, $b$ is an odd integer ranging between $a$ and ...
4
votes
0answers
141 views

Understanding Newman's proof of the prime number theorem

I am trying to understand D.J. Newman's proof of the prime number theorem, as presented by D. Zagier. I am not too familiar with analysis, and so there are some things I don't understand. In (III), ...
4
votes
0answers
72 views

Dominated convergence on $e^{-n^2 t} t^{s/2-1}$

I am trying to apply the Dominated Convergence Theorem to show that $$\sum_{n\ge 1} \int_0^1 e^{-n^2 t} t^{s/2-1}dt= \int_0^1 \sum_{n\ge 1}e^{-n^2 t} t^{s/2-1}dt$$ as soon as $s>1$. I've ...
4
votes
0answers
206 views

How fast does $\binom{n}{k}$ grow when $k \le n/2$?

How fast does $\binom{n}{k}$, $n$ fixed, grow when $k \le n/2$? Especially, I'm interested in the growth of the "inverse" of binomial coefficient $B_n(x) := \min \{k:\binom{n}{k} \ge x\}$. EDIT: ...
4
votes
0answers
87 views

Asymptotic Analysis of Complex Integrals

Let $\gamma\subset B(0,2)\subset \mathbb{C}$ a smooth Jordan curve envolving the origin and $\phi:\mathbb{C}\setminus (-\infty,0)\to \mathbb{C}$ an analytic function having finite boundary values, ...
3
votes
0answers
63 views

Question about Big O notation for asymptotic behavior in convergent power series

Examples of such use of Big O notation can be found for instance on Wolfram Alpha here. More details on the Wikipedia page. The idea, as I understand it, is that the term between parenthesis in Big O ...
3
votes
0answers
38 views

WKB and asymptotic behavior of second order differential equation

I want to study the large $x$ solution to a Riccati equation. After listening to the lectures on Mathematical Physics by Carl Bender, I have fallen in love with asymptotic analysis. But, by no means ...
3
votes
0answers
49 views

Which series of numbers effectively translates the factorial to the exponential function?

We have the relation of the Bernoulli numbers $$B_{2n} = (-1)^{n+1}\frac {2(2n)!} {(2\pi)^{2n}} \left(1+\frac{1}{2^{2n}}+\frac{1}{3^{2n}}+\cdots\;\right).$$ For $n>1$, the right hand sum ...
3
votes
0answers
43 views

Asymptotics of partitions in at most n parts, bounded by r

For every positive integers $n,r,w$ define $$ p_w(n,r)=\#\{ (i_1,...,i_r) | \, 0\leq i_1 \leq \dots \leq i_r\leq n, \, i_1+\dots+i_r=w\} $$ as the number of partitions of $w$ in at most $r$ piece ...
3
votes
0answers
41 views

Growth rate of $\exp(log^{a}(x))$ slower then any power of $x$.

So I'm trying to show that for $0<a<1$ and for $\epsilon >0$ that $\exp((\log x)^{a})=\mathcal{O}(x^{\epsilon}).$ So this amounts to showing that ...
3
votes
0answers
71 views

How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being ...
3
votes
0answers
73 views

Asymptotic solution for $T(n) = 6T(n/4) + n \lg n$

I am given that $T(n) = 6T(n/4) + n \lg n$ and want to find $\Theta(T(n))$. Below is what I have typed up for my solution so far; I asked my professor because I was unsure as to how I could assure ...
3
votes
0answers
76 views

Exponentials of chi-squared random variables (and their sums)

Let $X_1,X_2,\ldots,X_n$ be a sequence of i.i.d. chi-squared random variables with $t$ degrees of freedom, i.e. $X_i\sim\chi^2_t$. I am wondering what is known about the distribution of ...
3
votes
0answers
56 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
0answers
65 views

Definition of small $o$

In one of my homework assignments (in intro to applied mathematics) there is the following definition: Given two functions $f(\epsilon),g(\epsilon)$ that are defined in $D=(0,\epsilon)$ we say ...
3
votes
0answers
133 views

Saddle point and stationary point approximation of the Airy equation

Happy New Year to you all. Let $$\tag 1 J(N)=\int_a^b e^{Nf(x)}dx$$ where $N\in\mathbb R$ and $N>>1$ and $f(x)$ has a global maximum at $x=x_0$ with Taylor expansion $$f(x) \approx ...
3
votes
0answers
70 views

How to explore the asymptotic of an iteration

Definition Given that $f:\Bbb R\to\Bbb R$ is a real-valued function. The iteration of $f$, say $f^n$, is defined here: $f^0(x)=x$ $f^n(x)=f\left(f^{n-1}(x)\right)$ for any positive integer $n$. ...
3
votes
0answers
57 views

Is there a common name for $O(x^{cx})$ type functions?

Is there a common name for the growth rate of functions that are asymptotically on the order of $x^{cx}$, for some $c$? The term super-exponential is much too general. The factorial function grows in ...
3
votes
0answers
335 views

Asymptotics for the expected length of the longest streak of heads.

As Introduction to Algorithms (CLRS) describes, the problem is Suppose you flip a fair coin $n$ times. What is the longest streak of consecutive heads that you expect to see? The book claims ...
3
votes
0answers
96 views

Asymptotics of $\sum_{n=1}^{\infty}x^{n+1/n}/n!>e^x$?

Is there a way to find precise asymptotics or better bounds of series such as $\sum_{n=1}^{\infty}x^{n+1/n}/n!>e^x$ ? Or $\sum_{n=1}^{\infty}x^{\sqrt n}/e^n$?
3
votes
0answers
78 views

Products of primes of the form $an + b$

What is the asymptotic order of numbers divisible by no primes except those of the form $an+b$ ($a$, $b$ fixed)? Surely (except for the trivial cases) they are of order strictly between that of he ...
3
votes
0answers
267 views

When do floors and ceilings matter while solving recurrences?

I came across places where floors and ceilings are neglected while solving recurrences. Example from CLRS (chapter 4, pg.83) where floor is neglected: Here (pg.2, exercise 4.1–1) is an example ...
3
votes
0answers
404 views

Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$

On pages 95 and 96 of the third edition of the CLRS book, we find the following, which applies here since $a=b$ is all it takes to block the application of the Master Theorem: "Although $n\lg n$ is ...
3
votes
0answers
84 views

Asymptotics of Riemann-Lebesgue type integral

How to show that for $u \in L_{\mathbb{C}}^2$ and $a>0$, $$\int_0^a u(t) \sin{\sqrt{\lambda}t} \,dt = o(e^{|Im\sqrt{\lambda}|a}),\text{ as } |\lambda| \rightarrow \infty$$ Note that $\lambda$ ...
3
votes
0answers
140 views

How to solve equation involving binomial coefficient?

I'm reading this paper which says If we have $$ \binom n d p^{\binom d 2} = 1 $$ where $ 0 < p \le 1$, then $$ d = 2 \log_bn - 2 \log_b \log_b n + 2 \log_b\left(\frac 1 2 e\right) + 1 + O(1) ...
3
votes
0answers
182 views

proving the saddle point method in a specific case

$1:$ the problem Let $f : U \to \Bbb{C}$ be analytic on some open set $U$ that includes the closed unit ball. Define a path $\gamma$ by: $\gamma(t) = e^{i t}$, -$\pi < t \leq \pi$ I want to ...
2
votes
0answers
61 views

How to maximize speed of rest position approach of nonlinearly damped spring oscillator?

Inspired by comments to answer for this question: Suppose we have a system which is described by the equation $$\ddot x=-x+g(\dot x),$$ with initial conditions $x(0)=1$, $\dot x(0)=0$. If ...
2
votes
0answers
18 views

Asymptotic behaviour of oscillating integral

I'm interested in the big $x$ ($x \to \infty$) behaviour for the following integral $\int_{-\infty}^{\infty} \frac{dk}{\sqrt{k^2+1}} \frac{e^{-\sqrt{k^2+1}/2}}{1-e^{-\sqrt{k^2+1}}} e^{ikx}$ After a ...
2
votes
0answers
267 views

First disagreement in PROUHET THUE MORSE exponentially big?

Let two sequences of integers be $a_1, \cdots, a_n$ and $b_1, \cdots, b_n$ such that with $a_i \in \{1, \cdots n\}$ and $b_i \in \{1, \cdots, n\}$. Let $k$ be the min integer such that $\sum_{i=1}^n ...
2
votes
0answers
30 views

Asymptotics for Mertens function

It seems that the cumulative mean of the Mertens function is very similar in behaviour to $x$ raised to the power of the first zeta zero. I tentatively notate it as: ...
2
votes
0answers
24 views

Farey Sequences and how evenly is the sequence distributed

Given any $\alpha,\beta\in (0, 1)$, $k\in Z^+, n > 1$ is this true ($\mathcal{F}_n$ denotes the $n$th Farey sequence, and $\mathcal{F_n}^{\prime} = \{q:q = a + b, a\in\mathbb{Z}, ...
2
votes
0answers
31 views

A question regarding binomial coefficient

This question arose during solving an information theory problem. Suppose $l$ is the smallest integer such that $$2^l\geq {n\choose k}$$ define $\rho=\frac{k}{n}$. How we can characterize $\rho$ as a ...
2
votes
0answers
53 views

Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time?

As the question states: Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how? Thanks!
2
votes
0answers
169 views

representing integers as linear combination of integers

Let $a,b,a',b'$ be $r-\epsilon_1$ bit positive integers. Let $c,d$ be $s+\epsilon_2$ bit positive integers. Fix a pair $c,d$ and vary $a,b$ over all $r-\epsilon_1$ bit numbers. Do we have almost ...
2
votes
0answers
25 views

Is there a 2D 3-colorstate mobile automaton that grows like $ln^{0,5}(t)$?

Define an integer function $f(t)$ for an integer $t>25$ such that $|f(f(t)) - ln(t)| < \sqrt {ln(t)}+2$. Define $L(X(t))$ as the number of nonwhite states at iteration $t$ of mobile automaton ...
2
votes
0answers
29 views

How to find the sum of Big-Oh's?

I will admit this is a homework problem, but I'm seriously stuck. I'm not looking for answers, but just any hints as to what to do next. Any tips would be appreciated. I am given: $$f_1(x) = ...