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.

I am reading this document.

In this article after defining strong derivative Knuth goes on to calculate derivative of $x^n$. There he uses definition of strong derivative to expand $(x+\epsilon)^{n+1}$ as follows,

$(x+\epsilon)^{n+1} = (x+\epsilon)[x^n + d_n(x)\epsilon + \mathcal{O}(\epsilon^2)]$

when I expand the right side I get

$x^{n+1} + (x d_n(x) + \ x^n)\epsilon + \color{red}{x \ \mathcal{O}(\epsilon^2) + \epsilon^2 \ d_n(x) + \epsilon \ \mathcal{O}(\epsilon^2)}$

But in Knuths calculations the red part is just $\mathcal{O}(\epsilon^2)$.

Question is how? I don't know how to work this out in detail.

share|improve this question
    
This is explained here. Also, this question is similar, and it answers your question. –  William DeMeo Feb 20 '12 at 6:37

1 Answer 1

The part in red is equivalent to $\mathcal{O}(\epsilon^2)$.

Let us assume the first $\mathcal{O}$ in red, $\mathcal{O}(\epsilon^2)$, represents a remainder term $f(\epsilon)$ such that $f(\epsilon)\le A \epsilon^2$ for a constant $A$ and sufficiently small (but positive) $\epsilon$. Similarly, let the second $\mathcal{O}$ term in red represent the remainder term $g(\epsilon)$, which likewise must satisfy $g(\epsilon)\le B\epsilon^2$ for some $B$ and sufficiently small but positive $\epsilon$. When we add the terms together in red we get:

$$x\mathcal{O}(\epsilon^2)+\epsilon^2 d_n(x)+\epsilon\mathcal{O}(\epsilon^2)=xf(\epsilon)+d_n(x)\epsilon^2+\epsilon g(\epsilon) \le (Ax+d_n(x)+B)\epsilon^2$$

for sufficiently small $\epsilon$. One $\epsilon$ disappeared: we're fine for $\epsilon<1$. The inequality was obtained by adding together the inequalities for $f$ and $g$, plus the middle term, and then factoring. We know that the $Ax+d_n(x)+B$ term is constant with respect to $\epsilon$; combined these three terms are $\mathcal{O}(\epsilon^2)$.

share|improve this answer
    
I think your answer would be clearer if you didn't make $B$ disappear from the formula before it ever appeared. In other words write $\epsilon B$ instead of the term $1$ first. Then you can replace it by $1$ under the assumption $\epsilon<1/B$ (rather than $\epsilon<1$ as you said). –  Marc van Leeuwen Feb 20 '12 at 9:09
    
@Marc: Whooops! –  anon Feb 20 '12 at 9:14

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.