Say you’re at a party with nine other people and everyone shakes everyone else’s hand exactly once. How many handshakes take place?

This is the “handshake problem,” and it’s one of my favorites. As a math teacher, I love it because there are so many different ways you can arrive at the solution, and the diversity and interconnectedness of those strategies beautifully illustrate the power of creative thinking in math.

One solution goes like this: Start with each person shaking every other person’s hand. Ten people, with nine handshakes each, produce 9 × 10 = 90 total handshakes. But this counts every handshake twice — once from each shaker’s perspective — so the actual number of handshakes is $latex frac{90}{2} = 45$. A simple and lovely counting argument for the win!

There’s also a completely different way to solve the problem. Imagine that the guests arrive one at a time, and when they get there, they shake hands with everyone present. The first person has no hands to shake, so in a one-person party there are zero total handshakes. Now the second person arrives and shakes hands with the first person. This adds one handshake to the total, so in a two-person party, there are 0 + 1 = 1 total handshakes. When the third person arrives and shakes hands with the first two guests, this adds two handshakes to the total. The fourth person’s arrival adds three handshakes to the total, and so on.

This strategy models the sequence of handshakes recursively, meaning that each term in the sequence is defined relative to those that come before it. You’re probably familiar with the Fibonacci sequence, the most famous recursive sequence of all. It starts out 1, 1, 2, 3, 5, 8, 13, 21, and continues on with each subsequent term equal to the sum of the previous two.

As we’ll see below, recursion is a flexible and powerful framework for thinking about a wide range of mathematical ideas. And even though ancient Indian scholars like Hemachandra are credited with knowing about these kinds of sequences as far back as 1150, they still offer intriguing challenges for mathematicians today.

Let’s see how thinking recursively helps with the handshake problem. If we let $latex a_n$ equal the number of handshakes at an n-person party, we can represent this recursive relationship with the following formula:

$latex a_n = a_{n-1} + n–1$

This tells us that the number of handshakes at an n-person party ($latex a_n$) is equal to the number of handshakes at an (n − 1)-person party ($latex a_{n-1}$) plus n − 1 more handshakes, capturing the idea that when a new person arrives they add a certain number of new handshakes to those that have already taken place.

In our particular version of the handshake problem, we want to know $latex a_{10}$, the number of handshakes at a 10-person party, so to find that we use the recursive relationship

$latex a_{10} = a_9 + 9$

To find the value of $latex a_{10}$, we just need to know the value of $latex a_9$ and add 9 to it. How do we find the value of $latex a_9$? By using recursion, of course!

$latex a_9 = a_8 + 8$

Now, to find the value of $latex a_8$, we need to find the value of $latex a_7$, which requires knowing $latex a_6$, and so on. At this point, you might be worried that this will go on forever in a kind of infinite descent, but once we reach $latex a_1$ we’re done, because we know that there are zero total handshakes at a one-person party.

$latex a_1 = 0$

This initial or “seed” value is a key feature of a recursive sequence. It guarantees that this process of backtracking through the sequence using the recursive relationship will end. Once you hit the seed value the backtracking stops, and you can then work your way forward through the list to get the value you want.

$latex a_1 = 0$

$latex a_2 = a_1 + 1 = 0 + 1 = 1$

$latex a_3 = a_2 + 2 = 1 + 2 = 3$

$latex a_4 = a_3 + 3 = 3 + 3 = 6$

$latex cdots$

$latex a_{10} = a_9 + 9 = 36 + 9 = 45$

By working through the list, we see that there are 45 total handshakes at a 10-person party, which agrees with our initial calculation. If you’re anything like my students, you might ask why we need another way to solve this problem when we already know the answer, especially since this second approach seems to take longer.

It’s a good question. One answer is that the recursive approach gives us an entirely different view of what’s going on in this problem, and different perspectives are useful in math, as they are in all things. They give us different opportunities to understand concepts and allow us to use different tools, which can help when we’re stuck.

In particular, recursion is useful because it’s everywhere in math. It arises, for example, in the linear relationships everyone learns about in math class — the ones characterized by a constant rate of change and represented by lines in the plane. A linear function like $latex f(x) = 3x + 5$ can be thought of as a recursive formula:

$latex a_0 = 5$

$latex a_n = a_{n-1} + 3$

Although the more obvious way to think about $latex f(2)$ may be that $latex f(2) = 3 times 2 + 5 = 11$, another way is that $latex a_2 = a_1 + 3 = a_0 + 3 + 3 = 11$. Recursively modeling the fundamental characteristic of linear functions — the constant rate of change — gives us another way to think about this relationship. The same can be done with exponential functions characterized by constant multiplicative change.

Recursive thinking works beyond sequences of numbers as well. If you’ve ever solved a system of equations, you’ve probably applied a recursive approach. To solve the system

$latex 2x + y = 10$

$latex 3x – y = 5$

you can first add the two equations together to eliminate the y variable, which results in the equation $latex 5x = 15$. Solve this to get $latex x =$ 3, substitute to find $latex y = 4$, and you’re done. This approach utilizes a recursive algorithm, where the solution to a system is built from the solution to smaller, related systems. For example, to solve a 3 × 3 system, you eliminate one variable to turn it into a 2 × 2 system, and then again to turn it into a 1 × 1 system. This easy-to-solve single equation is like the seed value of this recursive process. It signals the end of the backtracking, and from there you work your way back up the chain of equations, just like in a recursive sequence.

There are even recursive proof techniques. For example, a famous formula in geometry is the polygon angle sum formula, which says that the sum of the measures of the interior angles of an n-sided polygon is $latex (n-2) times 180^{circ}$. One way to prove this result is to start with an n-gon and imagine what would happen if you removed a triangle.

Removing a triangle turns the n-gon into an (n − 1)-gon, and it also removes 180 degrees of interior angle measure. This is a recursive relationship: The interior angle sum for an n-gon is 180 degrees more than the interior angle sum for an (n − 1)-gon. To establish the general result, keep removing triangles until you reach the seed value, which in this situation happens when you’ve removed all but three of the n-gon’s vertices. At this point the initial polygon has been reduced to a triangle, whose interior angle sum is known to be 180 degrees. Now work your way back up, adding 180 degrees at each step, and you’ll get the formula.

Returning to our party, the handshake problem itself shows us what is possible when we think creatively and then connect those multiple different perspectives of a problem together. If we play around with the recursive model for our sequence of handshakes:

$latex a_1 = 0$

$latex a_n = a_{n-1} + n – 1$

a nice pattern emerges:

$latex a_2 = a_1 + 1 = 0 + 1$

$latex a_3 = a_2 + 2 = 0 + 1 + 2$

$latex a_4 = a_3 + 3 = 0 + 1 + 2 + 3$

$latex cdots$

$latex a_n = a_{n-1} + (n-1) = 0 + 1 + 2 + 3 + cdots + (n-1)$

We now have a new, and general, way to think about the problem: The number of handshakes in an n-person party is equal to the sum of the first n − 1 positive integers.

Think back to our original approach. In an n-person party, each person will shake hands with the other n − 1 people. The product $latex n (n-1)$ counts every handshake twice, so the total number of handshakes is $latex frac{n(n-1)}{2}$. But since our different methods count the same thing, they have to yield the same result. In particular, this means:

$latex 1 + 2 + 3 + cdots + (n-1) = frac{n(n-1)}{2}$

By connecting different approaches to the handshake problem, we get a closed formula for the sum of the first n − 1 positive integers. But we get even more: the expression $latex frac{n(n-1)}{2}$ involves a fraction, but because it is equal to a sum of integers, it too must be an integer. This proves a simple fact of number theory: For every integer n, $latex frac{n(n-1)}{2}$ is an integer.

This same kind of argument continues to power modern mathematics. As one example, researchers in the early 2000s proved some surprising results about recursive sequences known as Somos sequences by showing that they too count something. Through the power of creative connections, mathematicians once again discovered where they could go by understanding where they’ve been.

Exercises

1. Find a closed formula for the sequence that is defined recursively as
$latex a_1 = 1$
$latex a_n = a_{n-1} + 2n – 1$

2. At the end of the column, the expression $latex frac{n(n-1)}{2}$ was shown to be an integer even though the expression involves a fraction, because $latex frac{n(n-1)}{2}$ is the result of counting something. There is also a number theory argument that shows this expression must be an integer. What is it?

3. Find the first few terms of the recursive sequence
$latex a_1 = 1$
$latex a_n = frac{1}{1+a_{n-1}}$

4. Find the first few terms of the recursive sequence
$latex a_1 = 1$
$latex a_2 = 1$
$latex a_n = a_{n-1} – a_{n-2}$