A key idea from calculus – used frequently in optimization – is that we can use linear functions to locally approximate complicated non-linear functions. This post will illustrate the effectiveness of this approach for a very specific function, the square root (maintaining some continuity with my previous post).
Let’s start with the following goal: find the integer closest to √28. This is the type of problem that my wife gives to her middle school students. The answer is clearly either 5 or 6, since 52=25<28<36=62. But is √28 closer to 5 or to 6?
We are asking whether √28 is bigger or less than 5.5, or equivalently, whether 28 is bigger or less than 5.52. We can solve this by calculating 5.52=121/4=30.25>28, so therefore 5.5>√28, and thus √28 is closer to 5 than to 6. This method works, but requires squaring a fraction (which middle schoolers hate).
When my wife teaches methods for estimating square roots, she gives her students the following shortcut: Since 28 is closer to 52=25 than 62=36, conclude that √28 is closer to 5 than to 6.
The shortcut gets the right answer in this case, but when I heard about it, I was suspicious. Asking whether √n is closer to 5 than 6 is not the same as asking whether n is closer to 52 than 62. Or is it?
It turns out that for any integer n, the shortcut will get the right answer! We can see this algebraically. Let’s say that n is in between k2 and (k+1)2. The shortcut says to compare n to the average of k2 and (k+1)2, which is k2+k+1/2. The correct approach is to compare n to (k+1/2)2=k2+k+1/4. While these two thresholds are not identical, there are no integers between them, so they yield the same answer for any integer n.1
What if we want an even better estimate of √28? Linear interpolation is our friend again! Since 28 is 3/11 of the way from 52=25 to 62=36, we will estimate √28≈5+3/11.
More generally, if we know that n=k2+j<(k+1)2, then the linear interpolation estimates that √n≈k+j2k+1. In the previous example with n=28, we have k=5 and j=3.
That’s our estimate, but how good is it? First of all, because f(x)=√x is concave, we know that this method always gives an under-estimate. To see how much we miss by, we need to do some more algebra. Let √n=k+δ for some δ∈(0,1). Then k2+j=n=(k+δ)2=k2+2kδ+δ2, so we have j=2kδ+δ2. This means that our error is √n−(k+j2k+1)=(k+δ)−(k+j2k+1)=δ−j2k+1=δ−2kδ+δ22k+1=δ(1−δ)2k+1≤18k+4, where the final inequality uses the fact that for any δ we have δ(1−δ)≤1/4.2
This approximation method can be used on all sorts of problems involving square roots, but it is especially nice for estimating sums of consecutive square roots. Suppose that we want to estimate S=√100+√101+...+√121. The linear interpolation approach says, “There are 22 terms here. The first is 10, the last is 11, so on average they are about 10.5. Multiply 22×10.5 to get S≈231.”
This logic (and the associated calculation) are extremely simple, yet also very accurate! The analysis we just did tells us that (i) this is an under-estimate, and (ii) the error in estimating each term is at most 1/(8k+4) (in this example, k=10). We have only 2k terms with any error (we get the first and last terms exactly). Therefore, the total error in our estimate is at most 2k/(8k+4)<1/4. In other words, we know that S must be between 231 and 231.25. Woah! That’s a very tight range.