Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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<x< \infty$ 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.

share|improve this question

3 Answers 3

up vote 6 down vote accepted

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)$

share|improve this answer
    
Thank you Norbert. Could you explain your justification for getting rid of the log in the third equals sign? –  Ron Jeremy Jul 16 '12 at 19:18
    
Also, can I essentially just replace $O(f(x))$ with $Af(x)$ for $A$ some unknown positive constant? –  Ron Jeremy Jul 16 '12 at 19:21
    
@коктейльМолотова no you can't. The only thing you can say is that $A$ is a bounded function with respect to $x$. –  Norbert Jul 16 '12 at 19:26
    
why can't you then just set A to be the max of your bounded function? –  Ron Jeremy Jul 16 '12 at 19:27
1  
@Norbert Also, I think the $o(f)$ should be $O(f)$, or otherwise $f + o(f)$. –  Erick Wong Jul 16 '12 at 20:48

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} $$

share|improve this answer
    
$\exp(x) \notin 1 + x + O(x^2)$, because $x \in \omega(1)$. –  Hurkyl Jul 17 '12 at 1:07
    
@Hurkyl: I'm not sure I understand. We are only exponentiating things in $(1)$ using the power series that are $O\left(\frac1x\right)$. –  robjohn Jul 17 '12 at 1:59
    
I was referring to the first two equations. I know what you mean and you know what you mean, but they may be misleading to the OP. –  Hurkyl Jul 17 '12 at 8:56
    
@Hurkyl: hopefully, using $t$ in the first two equations and sending $t\to0$ as $x\to\infty$ will reduce any confusion. –  robjohn Jul 17 '12 at 10:01

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!!!

share|improve this answer
    
$O(x^x(1+x^{-1})^x)\neq e x^x$ вообще говоря... –  Norbert Jul 17 '12 at 0:55
    
Yes but in this case we are ok right? –  Ron Jeremy Jul 17 '12 at 2:28
    
No we are not, once you write $O$-symbol you can't neglect it in your comoutation. Speaking inrormally $O$-symbol is a loss of information that you don't need. If you write $O(x^x(1+1/x)^x)$ you can't say exactly which function is supposed to be here. –  Norbert Jul 17 '12 at 8:22
    
@коктейльМолотова: $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. –  robjohn Jul 17 '12 at 10:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.