Tag Info

4

Bounded away from $b$ means that there is a nontrivial interval around $b$ such that the sequence never enters it. In particular, if a sequence is bounded away from $b$ then it cannot converge to $b$. More generally, $b$ cannot be a limit point of the sequence.

3

Suppose $n$ is even. Bound each term of the "upper half" from below by $(n/2)^{k}$. You have $n/2$ such terms. For a lower bound of $(n/2)(n/2)^{k}= n^{k+1}/2^{k+1}$. The general case can be handled in the same way.

3

The Laplace method can indeed handle some integrals like this, and broad strokes of the procedure are essentially the same. First you would establish that the main contribution to the size of the integral comes from a neighborhood of some $t = t_0$ (often a critical point of $g$), where the size of the neighborhood potentially depends on $N$. Then you would ...

3

For an explicit counterexample, consider $f(x) = 2x$ and $g(x) = 2x + 1/x$. Both are $O(x)$. Then $f(x) - x = x$ and $f(x) - g(x) = 1/x$. So then $$\frac{f(x) - x}{f(x) - g(x)} = \frac{x}{1/x} = x^2$$ which is much larger than $O(x)$! This is a good intuition-building exercise on why you must be careful when using multiple big-oh expressions. For instance, ...

2

According to equation $(30)$ in http://mathworld.wolfram.com/BernoulliNumber.html, $$\frac t2 \coth \frac t2 = \sum_{n=0}^\infty \frac{B_{2n}t^{2n}}{(2n)!}$$ Choosing $t = 2$ gives $$\sum_{j=0}^{\infty}\frac{2^{2j-1}B_{2j}}{(2j)!} = \frac 12 \coth(1) \approx 0.65651764275 \, .$$

2

Use the generating function for Bernoulli numbers $$g(x)={x\over e^x-1}=\sum_{j=0}^\infty B_{j}{x^j\over j!}\\ \implies g(-x)=-{x\over e^{-x}-1}=\sum_{j=0}^\infty (-1)^jB_{j}{x^j\over j!}\\ \implies g(x)+g(-x)={x(e^x+1)\over e^{x}-1}=2\sum_{j=0}^\infty B_{2j}{x^{2j}\over {(2j)}!}\\ \implies\sum_{j=0}^\infty B_{2j}{2^{2j-1}\over {(2j)}!}={1\over2}{\coth(1)} ... 2 Yes, this is true. This is equivalent to proving that, for any a > 0, we have$$ \frac{\ln x}{x^a} \xrightarrow[x\to\infty]{}0 $$(you can see it by setting a=\frac{1}{m} from your question).\; which itself is equivalent to showing$$ \frac{a\ln x}{x^a} = \frac{\ln x^a}{x^a} \xrightarrow[x\to\infty]{}0 $$so, at the end of the day, it is sufficient ... 2 No calculus required.Taking logs to any base b=1+r with r>0, then for x>(1+r)^2 we have \log_b x>2. So for x>(1+r)^2 let n_x be the positive integer such that$$n_x\leq \log_bx<n_x+1.$$We have then b^{n_x}\leq x<b^{n_x+1}. And since n_x\geq 2 and r>0, we have, by the Binomial Theorem,$$x\geq b^{n_x}=(1+r)^{n_x}=1+r ...

2

Here, $\lg^2 n$ stands for $(\log_2 n)^2$. Your question is then to study the asymptotic behavior of $\sum_{k=0}^{\log_2 n} \log_2 \frac{n}{2^k}$.${}^{(\dagger)}$ Below are two different methods, one using knowledge of $\sum_{\ell=1}^m \ell = \frac{m(m+1)}{2}$ and yielding a sharp estimate; the second requiring no prior knowledge, but only giving a ...

1

For $n>0$ let $f(n)=n!/n^n$.Then $f(n+1)=f(n)\cdot (n/(n+1))^n<f(n)$ so $f(n)\leq f(1)=1$ so $n!\leq n^n$. DEF'N: $g(n)=O(h(n)$ as $n\to \infty$ iff $\exists k>0 \;\exists n_0\;(n>n_0\implies |g(n)|\leq k|h(n)|).$ Here we can let $g(n)=n!, h(n)=n^n, n_0=1,$ and $k=1.$

1

It is taking you to the first case of the Master Theorem, since $f(n)\in O(n^{c})$ for, e.g., $c=1.1 < \log_b a = \log_4 5 \simeq 1.16$. So $T(n) \in\Theta(n^{\log_4 5})$.

1

(1) is only true if $\alpha > 0$. Consider (2). $\lim a_n = 0$ means $a_n = o (1)$. This means $(n^{\frac{1}{\alpha}}|b_n|)^\alpha = o (1)$. If $\alpha > 0$, we have $n^{\frac{1}{\alpha}}|b_n| = o (1)$ so the statement is true. Otherwise, $\lim n^{\frac{1}{\alpha}}|b_n| = + \infty$. (3) Let $c = \lim a_n$, where $c > 0$ and finite. Then, $\lim ... 1 If$n$is a power of$2$, write$n=2^k$and apply Stirling's approximation to$k!to show that \begin{align} \frac{n^2}{\log^2 n} &= \frac{2^{2k}}{k!} \sim_{n\to\infty} \frac{2^{2k}}{\sqrt{2\pi k}\left(\frac{k}{e}\right)^k} = \frac{1}{\sqrt{2\pi k}}\cdot \frac{2^{(2+\log e)k}}{2^{k\log k}} = 2^{- k\log k + (2+\log e)k - \frac{1}{2}\log k + O(1) } \\ ... 1 Counterexample: Let N = 8 and s_1 = \binom83 = 56, s_2 = \binom84 = 70, then A(s_1) = 4 > 3 = A(s_2). 1 There obviously cannot be an asymptotic limit of your A(n) as n\to\infty because A(n)=1 whenever n is prime and yet there are some n like 2^k for which A(n) can be arbitrarily large. Nonetheless, if we look at Hardy and Wright's Introduction to the Theory of Numbers 5th ed. (1980), sections 22.10-22.11, we see that A(n) is called there ... 1 Recall the definition of g = O(f): We say that g = O(f) iff there are c \ge 0 and N \in \mathbf N such that\def\abs#1{\left|#1\right|}\abs{g(n)} \le c\abs{f(n)}, \quad n \ge N. $$Suppose now f(n) = n and g(n) = n^2, we would have to show that$$ n^2 \le cn$is true for "$n$large" and some$c$. But regardless of which$c$we ... 1$\frac{n^{k+1}}{k+1}=\int\limits_{0}^nx^kdx\leq1^k+2^k+\dots +n^k\leq \int\limits_{1}^{n+1}x^{k}dx=\frac{(n+1)^{k+1}-1}{k+1}$. It is clear all monic polynomials of degree$k+1$are asymptotically equivalent, so the result follows. 1 Roughly speaking, it means that the sequence$\{a_n\}$does not get close to$0$or to$2$. There exists some$\delta>0$such that$|a_n-0|=|a_n|>\delta$for each$n$and there exists some$\varepsilon>0$such that$|a_n-2|>\varepsilon$for each$n$. The limit cannot be$0$or$2$if the sequence is bounded away. 1 The code is essentially this: sum=0 for i=1 to n do for j=1 to i do for k=1 to j^2 do sum++ The$ k $loop executes$ j^2 $times. The$ j $loop executes$ i $times Therefore the time taken to execute all the iterations of a$ j $loop is$ \sum\limits_{j = 1}^{i}{j^2} = O(i^3) $Finally, the$ i $loop executes$ n $times, ... 1 Close to done - you still need to formalise the contradiction you're looking for. You've reduced it to showing that$a_n=\frac{n!}{2^n}$isn't bounded, and indeed, it is not. Noting that$a_n=\frac{n}{2}a_{n-1}$, we see that for$n\ge3$,$a_n\ge\frac{3}{2}a_{n-1}$, which gives that$a_n\ge \left(\frac{3}{2}\right)^{n-3}a_3$by induction. Hence,$a_n\$ ...

1

Yes. Removing finitely many terms from a sequence does not influence its accumulation points.

Only top voted, non community-wiki answers of a minimum length are eligible