Proofs: Induction on Handshakes

Question

Here is the problem:

Suppose $n$ people are at a party, and some number of them shake hands. At the end of the party, each guest $G_i$, $1 \leq i \leq n$ shares that they shook hands $x_i$ times. Assume there were a total of $h \geq 0$ handshakes at the party. Use induction on $h$ to prove that:

$x_i + \cdots + x_n = 2h$

I am a little confused about the best way to solve this problem. Performing induction on $h$, means that I will assign my base case for $h=1$. The base case then suggests:

$x_i + \cdots + x_n = 2h$

$x_i + \cdots + x_n = 2$

I am I correct to assume that this means that for my base case for $1$ handshake, that there are 2 ($x_1$ + $x_2$) people who shook hands?

Based on this assumption, my next step would be to assume $h=k, \ \forall \ k \in \mathbb{Z} $. Performing induction on $h$, I would then let $h=(k+1)$ and I want to show that the left side of the equation is equivalent to $2(k+1)$:

$x_i + \cdots + x_n + 2 = 2(k+1)$

^This is the step I'm not really certain of. Since I know that when I add one additional hand shake, that means I am adding $2$ people to the situation... so, would adding $2$ to the left side be a fair way to show this induction? If I do this, then I easily come up with:

$2k + 2 = 2(k+1)$

$ 2k + 2 = 2k + 2$

Which is a true statement, so then I would have (hopefully...) proved this by induction.

What do you guys think? I have traditionally only performed induction on more straight forward math-y problems, so I'm not really sure if I am headed down the right rabbit hole on this one. I am currently in an Introduction to Proofs course at my University. This is a homework problem- I am obviously not looking for someone to do my homework for me (since that wouldn't bode well for my next exam...) but I just want to seek out some advice for my approach to this problem.

Thanks for looking!

Answer 1

This is the right idea. Your base case is correct, and your argument is the right one, modulo some technical points:

1. You don't want to assume $h=k$ $\forall k \in \mathbb{Z}$. That doesn't really make sense and isn't what you are really doing. You need to assume the claim holds for $1\leq h \leq k$, i.e. that $x_1 + \cdots + x_n = 2h$ when there are $h$ handshakes for all $1 \leq h \leq k$. The point of induction is to show that this holds for $h=k+1$, i.e. $$x_1 + \cdots + x_n = 2(k+1)$$ when there are $k+1$ handshakes.
2. For clarity you might say, for the inductive step, to add a handshake, two people must shake hands with each other. Say person 1 and person 2 are this new handshake. Then we consider the sum $$(x_1 + 1) + (x_2 + 1) + x_3 + \cdots + x_n.$$ This is obviously $2+x_1 + \cdots + x_n = 2 + 2k$ by the inductive hypothesis, and $2+2k = 2(k+1)$ as you have observed.

Answer 2

Assume that the handshakes occur sequentially: At time $1$ there is a handshake, then there is a handshake at time $2$, and so on. Let us suppose that when $h=k$, then $x_1+x_2+\cdots +x_n=2k$. Now at time $k+1$, a new handshake takes place, say between person $i$ and person $j$. Then $x_i$ is incremented by $1$, and so is $x_j$, and therefore $x_1+x_2+\cdots+x_n$ is incremented by $2$.