ums and Ap tion 3.4 Approximating 1+3 We can get upper and lower bounds on the function 1 +a by exponentiating our bounds n In(1 +r) What a profoundly stupid thing to do! The function 1 +r is really simple, while the func tion e /(+a) is complicated. Why would one ever want to bound a simple function with a complicated function? Why not just work with the original, simple function? The reason is that a appears at "ground level"in the function 1 +a, but"upstairs"in the functions ez and e/(1+z). This difference allows one to switch back and forth between sums and products. As a result, 1+a N e is probably the most widely-used approxima- tion in computer science! For example, let's take the nasty product that we tried to scare you with earlier 2 3 m2 1+ n2 n2 Our upper bound on 1+a gives n2 ≤ The second line follows from the rule ea. eB= eA+. Weve now translated the nasty product into an easy sum in the exponent! The rest is simplification. Note that el/2n is very close to 1 when n is large Similarly, the lower bound on 1 +a gives 1+ (1+)≥ ∴..+2x This sum is outside our repetoire. But we can get a lower bound by making some of the denominators a little bigger. In particular, if we make all the denominators as big as the argest one, then we have: 1+ nn+m2n+…+nn So the very scary product rapidly descends to nothing more than ve.� � � � � � 14 Sums and Approximations 3.4 Approximating 1 + x We can get upper and lower bounds on the function 1 + x by exponentiating our bounds on ln(1 + x): x/(1+x) e ≤ 1 + x ≤ e x What a profoundly stupid thing to do! The function 1 + x is really simple, while the func￾tion ex/(1+x) is complicated. Why would one ever want to bound a simple function with a complicated function? Why not just work with the original, simple function? The reason is that x appears at “ground level” in the function 1 + x, but “upstairs” in the functions ex and ex/(1+x) . This difference allows one to switch back and forth between sums and products. As a result, 1 + x ≈ ex is probably the most widely­used approxima￾tion in computer science! For example, let’s take the nasty product that we tried to scare you with earlier: � � � � � � � � 1 2 3 n 1 + 1 + 1 + 1 + n2 n2 n2 · · · n2 Our upper bound on 1 + x gives: � � � � � � 1 2 n ≤ e 1/n2 2/n2 n/n2 1 + 1 + 1 + e e n n 2 2 2 · · · n · · · · (1+2+...+n)/n2 = e n(n+1)/2n2 = e 1/2n = √e · e A B The second line follows from the rule e e = eA+B · . We’ve now translated the nasty product into an easy sum in the exponent! The rest is simplification. Note that e1/2n is very close to 1 when n is large. Similarly, the lower bound on 1 + x gives: � � � 1/n2 2/n2 n/n 2 1 2 n n n · · · n ≥ e 1+1/n2 · e 1+2/n2 · · · e 1+n/n2 1 + 1 + 1 + 2 2 2 1 2 + . . . + n = en2+1 + n2+2 n2+n This sum is outside our repetoire. But we can get a lower bound by making some of the denominators a little bigger. In particular, if we make all the denominators as big as the largest one, then we have: 1 2 n 1 + 1 + � � 1 + n � ≥ en2 1 +n + n2 2 +n + . . . + n2+n n n 2 2 2 · · · n (1+2+...+n)/n(n+1) = e = √e So the very scary product rapidly descends to nothing more than √e