Mathematical induction?

Question

Suppose that each of a group of business people arrives at a meeting, where each shakes hands with all of the other people present. If I was to tell you that it could be proven through mathematical induction that one could show that if n people come to the meeting then [n(n – 1)]/2 handshakes occur, what would be your response? See if you can come up with some logical response in support of this statement.

Answer 1

If n people come to the meeting, then
f(n) = n(n-1)/2 hand shakes occur.

Proof by induction.
n = 1:
If 1 person shows up, we expect no handshakes, and we verify that f(1) = 0.

n = 2:
If 2 people show up, we expect 1 handshake, and we see that f(2) = 1.

So the function holds true for n = 1 and 2.

Suppose the function is true for n = r.
i.e. f(r) = r(r-1)/2

Let us investigate n = r+1
If there are r people we expect r(r-1)/2 handshakes.
If 1 more person shows up (n = r + 1), then that person must shake hands with each of the previous r people
ie r more handshakes.
So no of handshakes = r(r-1)/2 + r
= r^2/2 - r/2 + r
= r^2/2 + r/2
= (r+1)*r/2
= f(r+1)
This is precisely the function value for n = r+1.

Thus it is proved by induction that the formula holds true for all n.

Answer 2

If there are n people, the first person shakes hands with n-1 people. To eliminate duplicate counting, the second person shakes hand with n-2 people,... with the nth (the last person) shaking hand with 0 person.

total handshakes T = (n-1) + (n-2) + (n-3) + ... + 2 + 1 + 0

Rewrite T as
T = 0 + 1 + 2 + ... + (n-3) + (n-2) + (n-1)

Add them
2T = (n-1) + (n-1) + (n-1) + ... (n-1) + (n-1) + (n-1)

Since there are n people, there must be n of these (n-1) terms
2T = (n-1)n

T = n*(n-1)/2

Answer 3

It hardly needs induction. Each of the n people shakes hands with the other (n-1) people, but since that counts each handshake twice, divide by 2.

Your second sentence contains a redundancy: "could be proven" and "could show."