13
$\begingroup$

I would like to know if there is a simple real-world problem which requires knowing a closed form for $\displaystyle \sum_{i=1}^n i$ and/or the sum of the first $n$ even/odd numbers. The only application I can think of is when doing Riemann Sums, but this student has not taken calculus.

$\endgroup$
  • 1
    $\begingroup$ Do you mean an actual practical problem or is something engaging sufficient? $\endgroup$ – quid May 9 '17 at 19:26
  • $\begingroup$ What do you mean by something engaging? The first time I saw this sum I was told the old story about Gauss, but I would like to have more of a practical problem if possible. $\endgroup$ – Ovi May 9 '17 at 19:47
  • $\begingroup$ The population of a town grows over time as 1, 2, 3, ... Each person produces one unit of garbage per year, which fills up a landfill. $\endgroup$ – Ben Crowell May 9 '17 at 20:08
  • $\begingroup$ @BenCrowell Is that model close to the actual way populations grow? I don't want to make the example sound too artificial. $\endgroup$ – Ovi May 9 '17 at 20:43
  • $\begingroup$ I meant things like the hand-shake problem, mentioned by now. My point being that on the one hand I do feel it can be a good motivation, yet on the other hand it might not really be a real-world problem in a literal sense. $\endgroup$ – quid May 9 '17 at 23:20
10
$\begingroup$

Students sometimes find applications to computer programming interesting. The sum in question often pops up in determining the complexity of various algorithms. For a simple example, selection sort sorts a list of $n$ items, by first scanning over it, selecting the first element , then scanning over the remaining $n-1$ items to find the second element of the sorted list, etc. The total amount of scanning is $1 + 2 + ... + n$. Alternatively, it involves $1 + 2 + ... + (n-1)$ pairwise comparisons in the course of those scans. In either case, the formula for the sum shows that selection sort is $O(n^2)$.

More generally, this sort of analysis is applicable to any algorithm with nested for-loops where the outer loop has its index (say $i$) ranging from $1$ to $n$ and the inner loop has its index (say $j$) ranging from $1$ to $i$.

$\endgroup$
9
$\begingroup$

If $n$ people meet and everyone shakes hands with everyone else, how many hand shakes were there?

You could do this combinatorially, e.g. $n$ choose 2, but another way to think about it is that the first person shakes $n-1$ times, the next $n-2$, ... until the second to last person only shakes the last person's hand. This leads to the summation.

$\endgroup$
9
$\begingroup$

Perhaps you can make the topic "applicable" by comparing it to some popular social media posts of the form, "How many triangles are in this figure? Only geniuses get this right!"

enter image description here

Take a $5\times 1$ rectangular grid, for example, and ask the students: How many rectangles of any size can be found in this figure? Surely, some of them will just start counting right away and find that the answer is 15. Then, prod them further by asking, "Okay, of those 15 rectangles, how many of them are $1\times 1$? How many are $2\times 1$? etc. up to $5\times 1$"

The students will see that there are 5, 4, 3, 2, and 1 such rectangles, respectively. Hopefully, they will then realize how to generalize the problem: if we start with an $n\times 1$ rectangle, the total number of rectangles will be $n+(n-1)+(n-2)+\cdots+3+2+1$.

Now, ask them what the answer to this problem would be if $n=100$. See how many students started punching calculator buttons or doing mental/paper arithmetic. Stop them immediately and say, "Surely, there must be a better, more efficient, method than just adding 100 numbers!" This motivates the necessity of a closed-form solution, and you can use this to jump into finding such a formula.

Addendum: Depending on the audience and time available, you could also use that problem to introduce binomial coefficients, since ${n+1\choose 2}$ is the solution to that problem. You can then segue into a combinatorial "proof without words" for that same fact. The image below demonstrates a bijection between the $1+2+\cdots+n$ elements in the upper triangle and pairs of elements in the row of $n+1$ elements in the bottom row (source via math.se):

enter image description here

Finally, you could follow this up by exploring a similar 2-dimensional problem: how many squares can you find in an $m\times n$ rectangular grid? The solution is ${m\choose 2}\cdot{n\choose 2}$. See this link for more.

$\endgroup$
8
$\begingroup$
  1. You are able to buy cubical wooden blocks of unit size, and you want to build a staircase to get over a wall of height $n$ units. How many blocks are required?

  2. A gold mining operation has two shifts. The day shift bores a tunnel that is deeper by an additional depth $\delta$ each day. The night shift comes in and works the whole accumulated length of the tunnel every day, extracting gold worth $g$ dollars per unit of depth. Find the gross revenue after $n$ days.

  3. The population of a town grows over time as 1, 2, 3, ... Each person produces one unit of garbage per year, which fills up a landfill.

[Re #3, from comments:]

Is that model close to the actual way populations grow? I don't want to make the example sound too artificial.

I would approach this from the point of model building. Models don't need to be perfectly realistic in order to be informative. Also, linear population growth is likely to be a pretty decent approximation over an appropriate time interval (say a decade).

$\endgroup$
7
$\begingroup$

I am not quite sure if this answers the question in the body of your post, but here is how I have motivated the search for a closed form regarding these summations.

Summing the first $n$ counting numbers:

I used this formula when I demoed for my current teaching position, and think it is a good way to start a new year off, too: To learn student names, I have each of them say their own name, and then the name of each of their predecessors. So, the first person says just her own name ($1$ name), the second person says her sole predecessor's name as well as her own ($2$ more names), the third person says each of the first two's names and then her own ($3$ more names), and so forth.

At the end, I ask the students whose name was said the most times, whose name was said the fewest times, and how many total name utterances there were. Generally this is solved in one of three (related) ways: the Gaussian summation trick of duplicating the total, evaluating it as $n(n+1)$, and dividing by $2$ for the answer; pairing the number of utterances by the first and last speaker (i.e., $1$ and $n$), the second and penultimate speaker ($2$ and $n-1$) etc., with a small caveat around when there are an odd number of students; or multiplying the average number of utterances by the number of students (to my surprise, a group of eighth graders devised this method when I actually demoed!).

I like to follow-up and ask a question such as, e.g., for a class of $16$ students: Would the total number of utterances be greater, fewer, or the same, if instead of having them go through the names as above, we broke into two groups of $8$ students and had each group proceed with this name game? (This can be computed as $16(17)/2$ versus $2 \cdot 8(9)/2$, or answered without computation...)

If you devise a method of summing the first $n$ counting numbers and realize it as $n(n+1)/2$, then the sum of the first $n$ even numbers is (clearly) twice this, i.e., $n(n+1) = n^2 + n$. And once you know that, you can sum the first $n$ odd numbers by summing the first $n$ even numbers and subtracting $1$ from each of the $n$ addends, which gives a total of $(n^2 + n) - n = n^2$.

An application of the fact that the first $n$ odds sum to $n^2$ arises when one broaches quadratic functions. Specifically, students in my algebra classes will write a quadratic expression in either vertex form, $a(x-h)^2 + k$, or standard form, $ax^2 + bx + c$, and then graph them by finding the vertex, first, and then (when the quadratic is monic, i.e., $a=1$) going over one, up $1$; over another, up $3$, over another, up $5$, etc. When the quadratic has a coefficient $a \not = 1$, then you can take these same rises and multiply through by $a$.

For example, the quadratic function defined by $x \mapsto 2(x-3)^2 - 8$ can be graphed by first noting that the vertex is at $(3, -8)$, and then going over one (to the left and right) and up $2 \cdot 1 = 2$; over another, up $2 \cdot 3 = 6$; over another, up $2 \cdot 5 = 10$, etc. This is a quick way to graph the quadratics that we are dealing with, but making sense of why this works relies on the closed formula for the sum of odds. (So, any problem you have around quadratics that benefits from a graphical representation can be readily connected to $\sum$odds as described above.)

$\endgroup$
1
$\begingroup$

In my experience, this most commonly pops up in terms of averages of a uniform distribution. What is the average face value of a standard die (6-sided)? Of a polyhedral 4, 8, 12, or 20-sided die? What is the average of the numerical cards in a standard deck (2-10)? While the answer may seem trivial, many students find it totally opaque on first encounter.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.