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
    Thank you Norbert. Could you explain your justification for getting rid of the log in the third equals sign?2012-07-16
  • 0
    Also, can I essentially just replace $O(f(x))$ with $Af(x)$ for $A$ some unknown positive constant?2012-07-16
  • 0
    @коктейльМолотова no you can't. The only thing you can say is that $A$ is a bounded function with respect to $x$.2012-07-16
  • 0
    why can't you then just set A to be the max of your bounded function?2012-07-16
  • 0
    This is a problem of notation. When you see equality $g=O(f)$ you can say informally that $g$ is bounded by $f$. But you can't say $O(f)=g$, because $O(f)$ is a set of functions which "bounded" by $f$.2012-07-16
  • 0
    In fact we use ambiguous notaion in calculus. If we want to be rigorous we must say for example $\exp(1+x)=1+g(x)$, where $g\in o(x)$ for $x\to 0$. But no one writes this way because it is messy and this boring repetitions in practise are avoided by [Landau-Symbole notation](http://de.wikipedia.org/wiki/Landau-Symbole)2012-07-16
  • 0
    So when we say $g=O(f)$ what we're saying is g is some element of the set of all functions whose absolute value is bounded by a constant multiple of $f$, is that a correct understanding?2012-07-16
  • 0
    You are almost correct, the last thing you need to say is that $g$ is eventually bounded by $A f$. Not for all $x$ but all $x$ in some neighborhood of particular point.2012-07-16
  • 0
    Ok so past some point $x_0$ or within some neighborhood of a point, that makes sense; thanks! I think I'm going to spend some time proving those identities you listed to help my understanding.2012-07-16
  • 0
    This will be a good exercise for you2012-07-16
  • 0
    @Norbert Don't you mean $\exp(f) = 1 + O(f)$ for $f$ bounded?2012-07-16
  • 0
    @ErickWong Yes this was a typo2012-07-16
  • 1
    @Norbert Also, I think the $o(f)$ should be $O(f)$, or otherwise $f + o(f)$.2012-07-16
  • 0
    @ErickWong I'll fix it2012-07-16
  • 0
    You should attach hypotheses to your identities. e.g. the first two assume $f \in o(1)$.2012-07-17
  • 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
    $\exp(x) \notin 1 + x + O(x^2)$, because $x \in \omega(1)$.2012-07-17
  • 0
    @Hurkyl: I'm not sure I understand. We are only exponentiating things in $(1)$ using the power series that are $O\left(\frac1x\right)$.2012-07-17
  • 0
    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.2012-07-17
  • 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+x^{-1})^x)\neq e x^x$ вообще говоря...2012-07-17
  • 0
    Yes but in this case we are ok right?2012-07-17
  • 0
    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.2012-07-17
  • 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