Approxi guess that +d for some constants a, b c, and d. all that remains is to determine these constants. We can do this by plugging a few values for n into the equation above. Each value gives a linear equation in a, b, c, and d. For example n=1 1=a+b+c+d 5=8a+4b+2c+d n=3→14=27a+9b+3c+d We now have four equations in four unknowns. Solving this system gives a= 1/ 3, b=1/2, c=1/6, and d=0, so it is tempting to conclude that 3+2+6 (n+)(mn+ But be careful! This equation is valid only if we were correct in our initial guess at the form of the solution. If we were wrong, then this equation might not hold for any n other than 0, 1, 2, and 3! So be sure to verify that such guesses are correct by giving an induction 3 Approximating Functions When you ask about the weather, you probably want to hear something like"hot","cold or"raining", not a lengthly discourse on convection currents, radiative heat transfer, and dew points. Something similar is true about the analysis of computer algorithms and systems: a simple, approximate answer is often more useful than an exact, complicated answer So techniques for replacing complicated expressions with simple approximations can be extremely useful 3.1 Taylor's Theorem A wonderful way to get approximations is to dredge up Taylor's Theorem from the dark, murky regions of calculus. Unfortuantely, the theorem looks like something dredged from a dark, murky place. So let's start with some intuition ple approximation for the function In(1+a) that is fairly accu- rate when a is a small number. Here's what the function actually looks like� Sums and Approximations 9 guess that n 3 i 2 = an + bn2 + cn + d i=1 for some constants a, b, c, and d. All that remains is to determine these constants. We can do this by plugging a few values for n into the equation above. Each value gives a linear equation in a, b, c, and d. For example: n = 0 0 = ⇒ d n = 1 1 = ⇒ a + b + c + d n = 2 5 = 8 ⇒ a + 4b + 2c + d n = 3 14 = 27 ⇒ a + 9b + 3c + d We now have four equations in four unknowns. Solving this system gives a = 1/3, b = 1/2, c = 1/6, and d = 0, so it is tempting to conclude that: �n 3 2 i 2 n n n = + + 3 2 6 i=1 1 n(n + 2 )(n + 1) = 3 But be careful! This equation is valid only if we were correct in our initial guess at the form of the solution. If we were wrong, then this equation might not hold for any n other than 0, 1, 2, and 3! So be sure to verify that such guesses are correct by giving an induction proof. 3 Approximating Functions When you ask about the weather, you probably want to hear something like “hot”, “cold”, or “raining”, not a lengthly discourse on convection currents, radiative heat transfer, and dew points. Something similar is true about the analysis of computer algorithms and systems: a simple, approximate answer is often more useful than an exact, complicated answer. So techniques for replacing complicated expressions with simple approximations can be extremely useful. 3.1 Taylor’s Theorem A wonderful way to get approximations is to dredge up Taylor’s Theorem from the dark, murky regions of calculus. Unfortuantely, the theorem looks like something dredged from a dark, murky place. So let’s start with some intuition. Suppose we want a simple approximation for the function ln(1 + x) that is fairly accu￾rate when x is a small number. Here’s what the function actually looks like: