Question about sequences and little-o notation

187 Views Asked by At

Here's the question I'm trying to solve:

Consider sequences of the form $a_k = a/(k+1)^\alpha$ where $a > 0$ and $\alpha > 0$ and $k=0, 1, 2, ...$.

Show that $a_{k+1}/a_k = 1 - o(a_k)$ implies that $\alpha < 1$

Here's how I've gone about it so far:

$$ \frac{a_{k+1}}{a_k} = \frac{\frac{a}{(k+2)^\alpha}}{\frac{a}{(k+1)^\alpha}} = \frac{(k+1)^\alpha}{(k+2)^\alpha} = \frac{(k+2)^\alpha - (k+2)^\alpha + (k+1)^\alpha}{(k+2)^\alpha}$$ $$ = 1 - \frac{(k+2)^\alpha - (k+1)^\alpha}{(k+2)^\alpha} = 1 - o(a_k)$$

So then I need to show that the following limit goes to $0$:

$\displaystyle \lim_{k \to \infty} \frac{\frac{(k+2)^\alpha - (k+1)^\alpha}{(k+2)^\alpha}}{\frac{a}{(k+1)^\alpha}} = \frac{1}{a} \lim_{k \to \infty} \left[ (k+1)^\alpha - \frac{(k+1)^{2\alpha}}{(k+2)^\alpha} \right]$

However, when I look at this limit, it looks like it goes to $0$ regardless of $\alpha$. As $k$ gets large, it dominates the $+1$ and $+2$ terms in the limit, ultimately giving $\lim k^\alpha - k^\alpha = 0$. Am I misunderstanding something about little o notation?

2

There are 2 best solutions below

3
On BEST ANSWER

If I understand your question correctly, the following may help :

We have $$\begin{align} &\lim_{k \to \infty} \left[ (k+1)^\alpha - \frac{(k+1)^{2\alpha}}{(k+2)^\alpha} \right] \\\\&=\lim_{k\to\infty}\left[k^{\alpha}\bigg(\frac{k+1}{k}\bigg)^{\alpha}-k^{\alpha}\left(\frac{(k+1)^2}{k(k+2)}\right)^{\alpha}\right] \\\\&=\lim_{k\to\infty}\left[k^{\alpha}\left(1+\frac 1k\right)^{\alpha}-k^{\alpha}\left(\frac{1+\frac 2k+\frac{1}{k^2}}{1+\frac 2k}\right)^{\alpha}\right] \end{align}$$

Although we do have, regardless of the value of $\alpha$, $$\lim_{k\to\infty}\left(1+\frac 1k\right)^{\alpha}=1\qquad\text{and}\qquad \lim_{k\to\infty}\left(\frac{1+\frac 2k+\frac{1}{k^2}}{1+\frac 2k}\right)^{\alpha}=1$$ we cannot have

$$\lim_{k\to\infty}\left[k^{\alpha}\left(1+\frac 1k\right)^{\alpha}-k^{\alpha}\left(\frac{1+\frac 2k+\frac{1}{k^2}}{1+\frac 2k}\right)^{\alpha}\right]=\lim_{k\to\infty}\left(k^{\alpha}\times 1-k^{\alpha}\times 1\right)$$

where the limit as $k\to\infty$ is taken for subexpressions, which is generally invalid.

Example : Although we have $\displaystyle\lim_{n\to\infty}\frac 1n=0$, we cannot have $$\lim_{n\to\infty}\left(1+\frac 1n\right)^n=\lim_{n\to\infty}(1+0)^n=1$$ where the limit as $n\to\infty$ is taken for a subexpression $\dfrac 1n$.


Added :

You said in a comment "It looks like we could also apply Bernoulli's inequality here which makes things a bit easier by not having to carry around all the extra terms".

Although we cannot apply Bernoulli's inequality since it is of the form $(1+x)^r\color{red}{\geqslant} 1+rx$ for $r\gt 1$, we can apply the following inequality :

If $-1\lt x\leqslant 0$ and $r\gt 1$, then $$(1+x)^r\color{red}{\leqslant} 1+rx+\frac{r(r-1)+1}{2}x^2\tag1$$ A proof of $(1)$ is written at the end of this answer.


Proof that the limit going to $0$ implies that $\alpha\lt 1$.

  • If $\alpha=1$, then $\displaystyle\lim_{k\to\infty}\left[ (k+1)^\alpha - \frac{(k+1)^{2\alpha}}{(k+2)^\alpha} \right]=\displaystyle\lim_{k\to\infty}\frac{k+1}{k+2}=1$

  • If $\alpha\gt 1$, then we have, using $(1)$, $$\small\begin{align}\left[ (k+1)^\alpha - \frac{(k+1)^{2\alpha}}{(k+2)^\alpha} \right] &=(k+1)^\alpha\left[ 1 - \frac{(k+1)^{\alpha}}{(k+2)^\alpha} \right] \\\\&=(k+1)^\alpha\left[ 1 - \left(1-\frac1{k+2}\right)^\alpha \right] \\\\&\geqslant (k+1)^\alpha\left[ 1 - \left(1-\frac{\alpha}{k+2}+\frac{\alpha(\alpha-1)+1}{2}\bigg(-\frac{1}{k+2}\bigg)^2\right) \right] \\\\&=(k+1)^{\alpha-1}\left[\frac{k+1}{k+2}\alpha-\frac{(\alpha^2-\alpha+1)(k+1)}{2(k+2)^2}\right]\end{align}$$ Since $$\lim_{k\to\infty}(k+1)^{\alpha-1}\left[\frac{k+1}{k+2}\alpha-\frac{(\alpha^2-\alpha+1)(k+1)}{2(k+2)^2}\right]=\infty$$ we can say that if $\alpha\gt 1$, then $$\lim_{k\to\infty}\left[ (k+1)^\alpha - \frac{(k+1)^{2\alpha}}{(k+2)^\alpha} \right]=\infty$$

In conclusion, if $\displaystyle\lim_{k\to\infty}\left[ (k+1)^\alpha - \frac{(k+1)^{2\alpha}}{(k+2)^\alpha} \right]=0$, then we have to have $\alpha\lt 1$.$\quad\blacksquare$


Let us prove a stronger inequality than $(1)$ :

If $-1\lt x\leqslant 0, r\gt 1$ and $A\geqslant\max\bigg(\dfrac{r(r-1)}{2}, \dfrac r2\bigg)$, then $$(1+x)^r\leqslant 1+rx+Ax^2\tag2$$

Proof :

Let $f(x):=1+rx+Ax^2-(1+x)^r$.

Then, $$\begin{align}f'(x)&=r+2Ax-r(1+x)^{r-1} \\\\f''(x)&=2A-r(r-1)(1+x)^{r-2} \\\\f'''(x)&=\underbrace{r(r-1)(1+x)^{r-3}}_{\text{positive}}(2-r)\end{align}$$

  • If $1\lt r\lt 2$, then $f'''(x)\gt 0$, so $f''(x)$ is increasing with $\displaystyle\lim_{x\to (-1)^+}f''(x)=-\infty$ and $f''(0)=2A-r(r-1)\gt 2A-r\geqslant 0$.

    So, there is only one $\beta$ such that $f''(\beta)=0$ and $-1\lt \beta\lt 0$.

    So, $f'(x)$ is decreasing for $-1\lt x\lt \beta$ and is increasing for $\beta\lt x\lt 0$ with $\displaystyle\lim_{x\to (-1)^+}f'(x)=r-2A\leqslant 0$ and $f'(0)=0$, which implies $f'(x)\leqslant 0$.

    So, $f(x)$ is decreasing with $f(0)=0$, which implies $f(x)\geqslant 0$.

  • If $r\geqslant 2$, then $f'''(x)\leqslant 0$, so we see that $f''(x)$ is decreasing with $f''(0)=2A-r(r-1)\geqslant 0$, which implies $f''(x)\geqslant 0$.

    So, $f'(x)$ is increasing with $f'(0)=0$, which implies $f'(x)\leqslant 0$.

    So, $f(x)$ is decreasing with $f(0)=0$, which implies $f(x)\geqslant 0$.

Therefore, we can say that $(2)$ holds.$\quad\square$

Taking $A=\dfrac{r(r-1)+1}{2}$, we can say that $(1)$ holds.

6
On

We have that by binomial series

$$\left[ (k+1)^\alpha - \frac{(k+1)^{2\alpha}}{(k+2)^\alpha} \right]=(k+1)^\alpha\left[ 1 - \frac{(k+1)^{\alpha}}{(k+2)^\alpha} \right]=$$

$$=(k+1)^\alpha\left[ 1 - \left(1-\frac1{k+2}\right)^\alpha \right]=(k+1)^\alpha\left[\frac\alpha{k+2}+O\left(\frac1{k^2}\right)\right]$$

and we need that $\alpha <1$.


Well, your approach is fine but the final evaluation for the limit is uncorrect. Let see why!

You are claiming that:

  • "it looks like it goes to $0$ regardless of $\alpha$. As $k$ gets large, it dominates the $+1$ and $+2$ terms in the limit, ultimately giving $\lim k^\alpha - k^\alpha = 0$"

but this is wrong.

Indeed by binomial series, assuming wlog $\alpha <2$, we have that

$$(k+1)^\alpha = k^\alpha\left(1+\frac1k\right)^\alpha =k^\alpha\left(1+\frac\alpha k+O\left(\frac1{k^2}\right)\right)=k^\alpha+\alpha k^{\alpha -1}+O\left(\frac1{k^{2-\alpha}}\right)$$

and

$$\frac{(k+1)^{\alpha}}{(k+2)^\alpha} =\left(1-\frac{1}{k+2}\right)^\alpha=1-\frac{\alpha}{k+2}+O\left(\frac1{k^2}\right)$$

which implies

$$\frac{(k+1)^{2\alpha}}{(k+2)^\alpha} =k^\alpha+\alpha k^{\alpha -1}-\frac{\alpha k^\alpha}{k+2}+O\left(\frac1{k^{2-\alpha}}\right)$$

and therefore

$$(k+1)^\alpha-\frac{(k+1)^{2\alpha}}{(k+2)^\alpha}=\frac{\alpha k^\alpha}{k+2}+O\left(\frac1{k^{2-\alpha}}\right)$$

which requires $\alpha <1$ in order to have the limit equal to zero.