3

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.

M Turgeon
  • 10,419
Set
  • 7,600

3 Answers3

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

Norbert
  • 56,803
  • Thank you Norbert. Could you explain your justification for getting rid of the log in the third equals sign? – Set Jul 16 '12 at 19:18
  • Also, can I essentially just replace $O(f(x))$ with $Af(x)$ for $A$ some unknown positive constant? – Set 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? – Set Jul 16 '12 at 19:27
  • 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$. – Norbert Jul 16 '12 at 19:31
  • 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 – Norbert Jul 16 '12 at 19:34
  • 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? – Set Jul 16 '12 at 19:36
  • 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. – Norbert Jul 16 '12 at 19:37
  • 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. – Set Jul 16 '12 at 19:39
  • This will be a good exercise for you – Norbert Jul 16 '12 at 19:40
  • @Norbert Don't you mean $\exp(f) = 1 + O(f)$ for $f$ bounded? – Erick Wong Jul 16 '12 at 19:42
  • @ErickWong Yes this was a typo – Norbert Jul 16 '12 at 19:47
  • 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
  • @ErickWong I'll fix it – Norbert Jul 16 '12 at 20:50
  • You should attach hypotheses to your identities. e.g. the first two assume $f \in o(1)$. –  Jul 17 '12 at 01:06
  • @Hurkyl, thanks, I've fixed – Norbert Jul 17 '12 at 01:35
2

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

robjohn
  • 345,667
  • $\exp(x) \notin 1 + x + O(x^2)$, because $x \in \omega(1)$. –  Jul 17 '12 at 01: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 01: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. –  Jul 17 '12 at 08: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
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!!!

Set
  • 7,600
  • $O(x^x(1+x^{-1})^x)\neq e x^x$ вообще говоря... – Norbert Jul 17 '12 at 00:55
  • Yes but in this case we are ok right? – Set Jul 17 '12 at 02: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 08: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