Tag Info

Hot answers tagged

7

This is an incomplete answer. It only cover the case for small $a$ exactly. Part I - Exact result for small $a$ Let $\rho_c \approx 0.75487766624669$ be the unique real root of the cubic equation $\rho^3 + \rho^2 - 1 = 0$. When $a \le a_c = (1 + \rho_c)^2 \approx 3.079595623491439$, $$Q(a) = (\sqrt{a}-1)^2$$ Let $\rho = \sqrt{q}$. Given any two ...


3

We have: $$\sum_{k=0}^n {n\brack k}x^k=x(x+1)\cdots(x+n-1)$$ (See Comtet, Advanced combinatorics) and $$u_n=\frac{1}{n!} \sum_{k = 1 }^{n } \frac{{n \brack k}}{k+1}=\int_0^1\frac{t(t+1)\cdots (t+n-1)}{n!} dt$$ Now we have $\exp(-x)\geq 1-x$ for $x\geq 0$. Hence for $t\in [0,1]$ we have $$\frac{t(t+1)\cdots (t+n-1)}{n!}=t\prod_{k=1}^{n-1} ...


3

Consider the following: $$\begin{align} \frac{1}{n!}\sum_{k=1}^{n}\frac{{n\brack k}}{k+1} &\stackrel{\color{red}{[1]}}=\frac{1}{n!}\sum_{k=0}^{n}\frac{{n\brack k}}{k+1}\\ &=\frac{1}{n!}\sum_{k=0}^{n}{n\brack k}\int_{0}^{1}x^k\,\mathrm{d}x\\ &=\frac{1}{n!}\int_{0}^{1}\left(\sum_{k=0}^{n}{n\brack k}x^k\right)\,\mathrm{d}x\\ ...


2

Hint You can write $$y=\frac{\sqrt[n]{x}+1}{\sqrt[n]{x}-1}=1+\frac{2}{\sqrt[n]{x}-1}$$ So, if $x$ goes to infinity, you have $$y \simeq 1+\frac{2}{\sqrt[n]{x}}$$


2

Here is a nice simple method. If $x>1$ then $$\frac{x^4 +7x^3+5}{4x+1}<\frac{x^4+7x^4+5x^4}{4x}=\frac{13}{4}x^3$$ and $$\frac{x^4 +7x^3+5}{4x+1}>\frac{x^4}{4x+x}=\frac{1}{5}x^3\ .$$ That is, we have shown that if $x>1$ then $$\frac{1}{5}x^3<f(x)<\frac{13}{4}x^3\ .$$


2

As an expansion on the perfect comments of Daniel and Crostul. Consider the function: $$\begin{cases}f:\Bbb N\to\Bbb N \\ 2k\mapsto 3k \\ 2k+1\mapsto 2k\end{cases}$$ $$\begin{cases} g: \Bbb N\to\Bbb N \\ n\mapsto n\end{cases}$$ This sequence has $f=\Theta(g)$ by definiting, because $$|f(n)|\le 2|g(n)|$$ for every $n$, and similarly for every $n$. ...


2

For any positive power $p$, $\displaystyle \sum\limits_{k=1}^{n} \binom{n}{k}^p \sim \dfrac{2^{np}}{\sqrt{p}}\cdot\left(\frac{n\pi}{2}\right)^{(1-p)/2} $, Making, $n \mapsto 2n$, We have, $\displaystyle \dfrac{\binom{2n}{n-k}}{\binom{2n}{n}} = \dfrac{n}{n+k}\prod\limits_{j=1}^{k-1}\dfrac{1-\frac{j}{n}}{1+\frac{j}{n}} = ...


2

Here's some intuition about the master theorem. Case $1$: If $f(n)$ is polynomially smaller than $n^{\log_b(a)}$, then it is negligible, and the asymptotic behavior is the same as what you would have without it included. Case $2$: If $f(n)$ is either of the same order as or exactly logarithmically larger than $n^{\log_b(a)}$, then the two terms compound ...


1

There is another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and $T(1)=T(2)=T(3)=T(4)=1$ and for $n\ge 5$ $$T(n) = 3 T(\lfloor n/5 \rfloor) + \lfloor \log_5 n \rfloor^2.$$ Then we can unroll the recurrence to obtain the following exact formula for $n\ge 5$ $$T(n) = 3^{\lfloor \log_5 n \rfloor} + ...


1

No. Let $X=10$ be a constant and $Y$ take two values, $100$ and $-100$, with equal probabilities. Then $E(X)=10\gg 0=E(Y)$, but $P(X>15)=0$ while $P(X+Y)>15=1/2$. I don't think you can get a "universal" inequality for all $x$. Take $x$ such that $P(X>x)$ is small but $P(Y>x)$ is large. This does not contradict your condition on the ...


1

A counter example with non-negative random variables would be when $Y$ is identically $1$ and $X$ is $0$ with probability $0.9$ and $10^{10}$ with probability $0.1$. Then $P(X + Y > x) = 1$ when $x < 1$, but $P(X > x) = 0.1$.


1

You are on the right track. However, rather than dividing by $x^3$, I would recommend multiplying by $(4x+1)$. The reason for this is so that you will have polynomials of degree $4$ on all sides of the inequality. It is okay to try different values for $k$ once you get a more simplified inequality. For this problem, I believe setting $k$ to $1$ will work ...


1

Yes, you could take $c_1=\frac{1}{4}$, then you have the following: $$ \frac{1}{4}x^3 \leq \frac{x^4 +7x^3+5}{4x+1} \Rightarrow \frac{4x^4+x^3}{4} \leq x^4+7x^3+5 \Rightarrow x^4+\frac{1}{4}x^3 \leq x^4+7x^3+5 \\ \Rightarrow \frac{27}{4}x^3 \geq -5 \Rightarrow x^3 \geq -\frac{20}{27} \Rightarrow x \geq - \sqrt[3]{\frac{20}{27}}$$ Since $x>0$ and $x \geq ...


1

What about $\sqrt{\log x\log{10}}$ ? Actually, any function mapping $0$ to $0$ and $\log10$ to $\log10$ and such that $f(x)>x$ in between can be used to compose $f(\log x)$ like you want. You can also use Hermite cubic interpolation, giving you all freedom to adjust the slopes.


1

Due to the Gauss formula: $$-\psi(z)+\log(z) = \int_{0}^{1}\left(\frac{1}{\log u}+\frac{1}{1-u}\right)u^{z-1}\,du$$ your series is just $-I(\alpha)$ due to the dominated convergence theorem, where: $$ I(\alpha) = \int_{0}^{1}\left(\frac{1}{\log z}+\frac{1}{1-z}-\frac{1}{2}\right)\frac{z^{\alpha-1}}{1-z^{\alpha}}\,dz.$$ Now, just like in this other question, ...


1

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} ...



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