1.1. Change in Discrete StepsToward the end of the eighteenth century, a German elementary school teacher decided to keep his pupils busy by assigning them a long, boring arithmetic problem: to add up all the numbers from one to a hundred [1]. The children set to work on their slates, and the teacher lit his pipe, confident of a long break. But almost immediately, a boy named Carl Friedrich Gauss brought up his answer: 5,050. [1] I'm giving my own retelling of a hoary legend. We don't really know the exact problem, just that it was supposed to have been something of this flavor. Figure A. Adding the numbers from 1 to 7. Figure B. A trick for finding the sum. Figure A suggests one way of solving this type of problem. The filledin columns of the graph represent the numbers from 1 to 7, and adding them up means finding the area of the shaded region. Roughly half the square is shaded in, so if we want only an approximate solution, we can simply calculate 7^{2}/2 = 24.5. But, as suggested in figure b, it's not much more work to get an exact result. There are seven sawteeth sticking out out above the diagonal, with a total area of 7/2, so the total shaded area is (7^{2}+7)/2 = 28. In general, the sum of the first n numbers will be (n^{2}+n)/2, which explains Gauss's result: (100^{2}+100)/2 = 5,050. Two sides of the same coinProblems like this come up frequently. Imagine that each household in a certain small town sends a total of one ton of garbage to the dump every year. Over time, the garbage accumulates in the dump, taking up more and more space. Let's label the years as n=1, 2, 3,…, and [2] let the function x(n) represents the amount of garbage that has accumulated by the end of year n. If the population is constant, say 13 households, then garbage accumulates at a constant rate, and we have x(n)=13n. [2] Recall that when x is a function, the notation x(n) means the output of the function when the input is n. It doesn't represent multiplication of a number x by a number n. But maybe the town's population is growing. If the population starts out as 1 household in year 1, and then grows to 2 in year 2, and so on, then we have the same kind of problem that the young Gauss solved. After 100 years, the accumulated amount of garbage will be 5,050 tons. The pile of refuse grows more quickly every year; the rate of change of x is not constant. Tabulating the examples we've done so far, we have this:
The rate of change of the function x can be notated as \(\dot{x}\). Given the function \(\dot{x}\), we can always determine the function x for any value of n by doing a running sum. Likewise, if we know x, we can determine \(\dot{x}\) by subtraction. In the example where x=13n, we can find \(\dot{x} = x(n)x(n1) = 13n13(n1) = 13\). Or if we knew that the accumulated amount of garbage was given by (n^{2}+n)/2, we could calculate the town's population like this: \begin{align} & \frac{n^2+n}{2}  \frac{(n1)^2+(n1)}{2} \\ &= \frac{n^2+n\left(n^22n+1+n1\right)}{2} \\ &= n \end{align} Figure D. \(\dot{x}\) is the slope of x. The graphical interpretation of this is shown in figure d: on a graph of x = (n^{2}+n)/2, the slope of the line connecting two successive points is the value of the function \(\dot{x}\). In other words, the functions x and \(\dot{x}\) are like different sides of the same coin. If you know one, you can find the other  with two caveats. First, we've been assuming implicitly that the function x starts out at x(0)=0. That might not be true in general. For instance, if we're adding water to a reservoir over a certain period of time, the reservoir probably didn't start out completely empty. Thus, if we know \(\dot{x}\), we can't find out everything about x without some further information: the starting value of x. If someone tells you \(\dot{x} = 13 \), you can't conclude x = 13n, but only x = 13n + c, where c is some constant. There's no such ambiguity if you're going the opposite way, from x to \(\dot{x}\). Even if x(0) ≠ 0, we still have \(\dot{x} = 13n+c[13(n1)+c] =13\). Second, it may be difficult, or even impossible, to find a formula for the answer when we want to determine the running sum x given a formula for the rate of change \(\dot{x}\). Gauss had a flash of insight that led him to the result (n^{2}+n)/2, but in general we might only be able to use a computer spreadsheet to calculate a number for the running sum, rather than an equation that would be valid for all values of n. Some guessesEven though we lack Gauss's genius, we can recognize certain patterns. One pattern is that if \(\dot{x}\) is a function that gets bigger and bigger, it seems like x will be a function that grows even faster than \(\dot{x}\). In the example of \(\dot{x} = n\) and x = (n^{2}+n)/2, consider what happens for a large value of n, like 100. At this value of n, \(\dot{x} = 100\), which is pretty big, but even without pawing around for a calculator, we know that x is going to turn out really really big. Since n is large, n^{2} is quite a bit bigger than n, so roughly speaking, we can approximate x≈ n^{2}/2=5,000. 100 may be a big number, but 5,000 is a lot bigger. Continuing in this way, for n=1000 we have \(\dot{x} = 1000\) , but x≈ 500,000  now x has far outstripped \(\dot{x}\). This can be a fun game to play with a calculator: look at which functions grow the fastest. For instance, your calculator might have an x^{2} button, an e^{x} button, and a button for \( x! \) (the factorial function, defined as \( x!=1 \cdot 2 \cdot ... \cdot x \), e.g., \( 4!=1 \cdot 2 \cdot 3 \cdot 4=24 \)). You'll find that 50^{2} is pretty big, but e^{50} is incomparably greater, and \( 50! \) is so big that it causes an error. All the x and \(\dot{x}\) functions we've seen so far have been polynomials. If x is a polynomial, then of course we can find a polynomial for \(\dot{x}\) as well, because if x is a polynomial, then x(n)x(n1) will be one too. It also looks like every polynomial we could choose for \(\dot{x}\) might also correspond to an x that's a polynomial. And not only that, but it looks as though there's a pattern in the power of n. Suppose x is a polynomial, and the highest power of n it contains is a certain number  the “order” of the polynomial. Then \(\dot{x}\) is a polynomial of that order minus one. Again, it's fairly easy to prove this going one way, passing from x to \(\dot{x}\), but more difficult to prove the opposite relationship: that if \(\dot{x}\) is a polynomial of a certain order, then x must be a polynomial with an order that's greater by one. We'd imagine, then, that the running sum of \(\dot{x} = n^2 \) would be a polynomial of order 3. If we calculate x(100) = 1^{2}+2^{2}+…+100^{2} on a computer spreadsheet, we get 338,350, which looks suspiciously close to 1,000,000/3. It looks like x(n) = n^{3}/3+…, where the dots represent terms involving lower powers of n such as n^{2}. The fact that the coefficient of the n^{3} term is 1/3 is proved in problem 21 in Section 1.4. Example 1Figure E. A pyramid with a volume of 1^{2}+2^{2}+3^{2}. Figure E shows a pyramid consisting of a single cubical block on top, supported by a 2× 2 layer, supported in turn by a 3× 3 layer. The total volume is 1^{2}+2^{2}+3^{2}, in units of the volume of a single block. Generalizing to the sum x(n) = 1^{2}+2^{2}+…+n^{2}, and applying the result of the preceding paragraph, we find that the volume of such a pyramid is approximately (1/3)Ah, where A=n^{2} is the area of the base and h=n is the height. When n is very large, we can get as good an approximation as we like to a smoothsided pyramid, and the error incurred in x(n) ≈ (1/3)n^{3}+… by omitting the lowerorder terms … can be made as small as desired. We therefore conclude that the volume is exactly (1/3)Ah for a smoothsided pyramid with these proportions. This is a special case of a theorem first proved by Euclid (propositions XII6 and XII7) two thousand years before calculus was invented.
