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!

  • $\begingroup$ Looks like some basic graph theoretic lemma. Don't really need induction to be proved btw. $\endgroup$ – Gabriel Romon Jul 11 '15 at 17:47
  • $\begingroup$ I agree, but the assignment requires the use of induction. Prof earned her PhD in graph theory, so Yay... $\endgroup$ – Mr. Meeseeks Jul 11 '15 at 17:50

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.
  • $\begingroup$ Great, thank you very much. Once I figured out the +2 thing it almost seemed too easy, so I thought I was doing it incorrectly or making an assumption that wasn't allowed. Appreciate the technical help, as well. Thank you! $\endgroup$ – Mr. Meeseeks Jul 11 '15 at 17:39

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


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.