The handshake problem is an old chestnut — if everyone in the room shook hands with everyone else, how many handshakes would there be? Then generalize. What I have to add to teaching the problem is a handout (doc version, pdf version) with different (fictional, but based on reality) students’ strategies for solving the problem. This handout is good for homework after students have worked on the problems themselves and listened to their classmates’ strategies.
The handout reinforces that there are a lot of different ways to solve a problem and also that a student’s idea can be worthwhile, even if there are mistakes and the final answer is wrong. It also helps students work on reading mathematics in a format that is friendlier than most text books. The handout includes a variety of representations of the problem.
This is one of those problems that I do every time in the math for teachers sequences, even though some students have seen it in high school (they don’t usually remember it that well). It is a good way to introduce important mathematics — recursive and explicit equations and triangle numbers — that we use throughout the course. It’s an engaging activity that works well. There’s a reason why it’s taught so frequently.