Proofs: Induction on Handshakes 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!
 A: This is the right idea. Your base case is correct, and your argument is the right one, modulo some technical points:


*

*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.

*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.

A: 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$.
