3
$\begingroup$

So I'm trying to show that for $x\rightarrow \infty$:

$(x+1+O(x^{-1}))^x = ex^x + O(x^{x-1})$

So these complicated big-Oh expressions are clearly going to be a recurring theme in my book, and I simply have no idea how to manipulate them in a rigorous fashion. I know logically what these expressions are saying, for instance this one means that:

For any function $f(x)=O(x^{-1})$ for all $a for some $a$, we must prove that there exists some $b$ such that $(x+1+O(f(x)))^x = ex^x + O(x^{x-1})$ for all $b< x< \infty$. And then I guess just use the $Max(a,b)$.

Nevertheless my book provides no list of 'legal' operations for big-Oh notation, and no examples of how to work with expressions that don't fall into the most simple category of $f(x) = O(g(x))$. Thus I'm simply at a loss not only for how I go about proving such expressions but I don't even know what operations I'm allowed to perform. How does one generally approach these problems? Thanks.

3 Answers 3

6

Here is an example of usage $ (x+1+O(x^{-1}))^x= $ $ \begin{align} &=x^x(1+x^{-1}+O(x^{-2}))^x\\ &=x^x\exp(x\log(1+x^{-1}+O(x^{-2})))\\ &=x^x\exp(x(x^{-1}+O(x^{-2})-0.5(x^{-1}+O(x^{-2}))+o(x^{-1}+O(x^{-2}))^2))\\ &=x^x\exp(x(x^{-1}+O(x^{-2})-0.5x^{-2}-x^{-1}O(x^{-2})-O(x^{-2})^2+o(x^{-1}+O(x^{-2}))^2))\tag{1}\\ &=x^x\exp(x(x^{-1}+O(x^{-2})-x^{-1}O(x^{-2})-O(x^{-2})^2+o(x^{-1}+O(O(x^{-1})))^2))\tag{3,4}\\ &=x^x\exp(x(x^{-1}+O(x^{-2})-x^{-1}O(x^{-2})-O(x^{-4})+o(x^{-1}+O(x^{-1}))^2))\tag{5,7}\\ &=x^x\exp(x(x^{-1}+O(x^{-2})-O(x^{-3})-O(x^{-4})+o(x^{-1})^2))\tag{9,12}\\ &=x^x\exp(x(x^{-1}+O(x^{-2})-O(O(x^{-2}))-O(O(x^{-2}))+o(x^{-1})^2))\tag{3}\\ &=x^x\exp(x(x^{-1}+O(x^{-2})-O(x^{-2})-O(x^{-2})+o(x^{-2})))\tag{7}\\ &=x^x\exp(x(x^{-1}+O(x^{-2})+o(x^{-2})))\tag{13}\\ &=x^x\exp(x(x^{-1}+O(x^{-2})))\tag{8}\\ &=x^x\exp(1+O(x^{-1}))\tag{12}\\ &=x^x\exp(1)\exp(O(x^{-1}))\\ &=x^x\exp(1)(1+O(x^{-1})+o(O(x^{-1})))\tag{2}\\ &=x^x\exp(1)(1+O(x^{-1}))\tag{10}\\ &=x^x e(1+O(x^{-1}))\\ &=ex^x+ex^xO(x^{-1})\\ &=ex^x+eO(x^xx^{-1})\tag{12}\\ &=ex^x+O(x^{x-1})\tag{11}\\ \end{align} $ In this solution I've used the following identites $ \begin{align} \log(1+f)&=f-0.5f^2+o(f)^2\qquad&(1)\\ \exp(f)&=1+f+o(f)\qquad&(2)\\ x^{-m-n}&=O(x^{-m})\qquad&(3)\\ C\cdot f+O(f)&=O(f)\qquad&(4)\\ O(f)\cdot O(g)&=O(fg)\qquad&(5)\\ o(f)\cdot o(g)&=o(fg)\qquad&(6)\\ O(O(f))&=O(f)\qquad&(7)\\ O(f)+o(f)&=O(f)\qquad&(8)\\ o(f+O(f))&=o(f)\qquad&(9)\\ O(f)+o(O(f))&=O(f)\qquad&(10)\\ C\cdot O(f)&=O(f)\qquad&(11)\\ f\cdot O(g)&=O(f\cdot g)\qquad&(12)\\ C\cdot O(f)+D\cdot O(f)&=O(f)\qquad&(13)\\ \end{align} $ where $f=o(1)$

  • 0
    @Hurkyl, thanks, I've fixed2012-07-17
1

Using the power series approxiations $ \begin{align} \log(1+t)&=t+O(t^2)\\ \exp(t)&=1+t+O(t^2) \end{align} $ as $t\to0$, we get, as $x\to\infty$, $ \begin{align} \left(1+\frac{1}{x}+O\left(x^{-2}\right)\right)^x &=\exp\left(x\log\left(1+\frac{1}{x}+O\left(x^{-2}\right)\right)\right)\\ &=\exp\left(x\left(\frac{1}{x}+O\left(x^{-2}\right)\right)\right)\\ &=\exp\left(1+O\left(x^{-1}\right)\right)\\ &=e\,\exp\left(O\left(x^{-1}\right)\right)\\ &=e\,\left(1+O\left(x^{-1}\right)\right)\\ &=e+O\left(x^{-1}\right)\tag{1} \end{align} $ Next, we have $ \begin{align} \left(x+1+O\left(x^{-1}\right)\right)^x &=ex^x+x^x\left(\left(1+\frac{1}{x}+O\left(x^{-2}\right)\right)^x-e\right)\\ &=ex^x+x^x\left(e+O\left(x^{-1}\right)-e\right)\\ &=ex^x+O\left(x^{x-1}\right)\tag{2} \end{align} $

  • 0
    @Hurkyl: hopefully, using $t$ in the first two equations and sending $t\to0$ as $x\to\infty$ will reduce any confusion.2012-07-17
0

What about this slick one:

$(x+1+O(x^{-1}))^x = (x(1 + x^{-1}) +O(x^{-1}))^x$

$=O(x^x(1+\frac{1}{x})^x) + O(x^{x-1}) = ex^x + O(x^{x-1})$

TA-DA!!!

  • 0
    @коктейльМолотова: $O(x^x(1+\frac{1}{x})^x)$ is something that is within a constant multiple of $x^x(1+\frac{1}{x})^x$. This is about the same size as the answer. It's like saying, "within an error of $10$, $4\times2=12$"; that is, your uncertainty is about the same size, or bigger, than your result.2012-07-17