Number of handshakes in a room

[jonroberts74]

Homework Statement

as each new person arrives to a meeting, they shake hands of all who are present.

prove the number [by induction] of occurred handshakes are $$\frac{n(n-1)}{2}$$

The Attempt at a Solution

if no one shows up then clearly no handshakes are exchanged

$$\frac{0(0-1)}{2} = 0$$

assuming k people show up, there will be $$\frac{k(k-1)}{2}$$ handshakes

now if one more person shows up, that will make a total of k+1 people and because one does not shake their own hand there will be k +1 -1 more shakes than when there where k people .

there will be

$$\frac{(k+1)(k+1-1)}{2}$$ handshakes in total

$$=\frac{k^2+k-k+k+1-1}{2}$$
$$=\frac{k^2-K}{2} + \frac{k+k+1-1}{2}$$
$$=\frac{k(k-1)}{2} + k$$


is this explained properly?

 

[LCKurtz]

Homework Statement

as each new person arrives to a meeting, they shake hands of all who are present.

prove the number [by induction] of occurred handshakes are $$\frac{n(n-1)}{2}$$

The Attempt at a Solution

if no one shows up then clearly no handshakes are exchanged

$$\frac{0(0-1)}{2} = 0$$

assuming k people show up, there will be $$\frac{k(k-1)}{2}$$ handshakes

now if one more person shows up, that will make a total of k+1 people and because one does not shake their own hand there will be k +1 -1 more shakes than when there where k people .

there will be

$$\frac{(k+1)(k+1-1)}{2}$$ handshakes in total

I don't follow that step. Aren't you assuming what you are trying to prove?

$$=\frac{k^2+k-k+k+1-1}{2}$$
$$=\frac{k^2-K}{2} + \frac{k+k+1-1}{2}$$
$$=\frac{k(k-1)}{2} + k$$


is this explained properly?

 

[jonroberts74]

I felt like I was assuming but wasn't for sure.

I feel like there's a point where I need to state the new number of handshakes with each incoming person is the new total of people minus 1, so I don't know if I said that at the right time.

 

[LCKurtz]

If there are $k$ people in the room your induction hypotheses says there have been $\frac{(k-1)(k)}{2}$ handshakes. If you now walk into the room, how many handshakes will you add (easy question)?

 

[jonroberts74]

I'll add k handshakes

so start here

$$\frac{k(k-1)}{2} + k$$

 

[LCKurtz]

Yes. Simplify that and see if you get the right formula for $k+1$. You worked it backwards originally.

 

[thelema418]

In addition to above, I'm concerned about the basis case, $n = 0$. In the context of the problem, I'm wondering why you did not chose $n = 1$ or $n = 2$.

 

[thelema418]

More explicitly: make certain that the inductive step works when $k = 0$ in the steps LCKurtz mentioned

 

[HallsofIvy]

Homework Statement

as each new person arrives to a meeting, they shake hands of all who are present.

prove the number [by induction] of occurred handshakes are $$\frac{n(n-1)}{2}$$

The Attempt at a Solution

if no one shows up then clearly no handshakes are exchanged

$$\frac{0(0-1)}{2} = 0$$

assuming k people show up, there will be $$\frac{k(k-1)}{2}$$ handshakes

now if one more person shows up, that will make a total of k+1 people and because one does not shake their own hand there will be k +1 -1 more shakes than when there where k people .

I would have stated this a little differently. If one more person arrives he must shake hands witheach of the k people who were already there so the number of handshakes is increased by k:
$$\frac{k(k-1)}{2}+ k$$

there will be

$$\frac{(k+1)(k+1-1)}{2}$$ handshakes in total

$$=\frac{k^2+k-k+k+1-1}{2}$$
$$=\frac{k^2-K}{2} + \frac{k+k+1-1}{2}$$
$$=\frac{k(k-1)}{2} + k$$


is this explained properly?

 

[LCKurtz]

I would have stated this a little differently. If one more person arrives he must shake hands witheach of the k people who were already there so the number of handshakes is increased by k:
$$\frac{k(k-1)}{2}+ k$$

Apparently you didn't read posts 4, 5, and 6?

 

[jonroberts74]

I didn't notice them, rereading all now

nvm, not to me.

so many long days, haha

 

[HallsofIvy]

Of course this can be done more simply without induction. Each of the n people must shake hands with each of the n-1 others which would give n(n-1) people shaking hands. But each hand shake involves 2 people so that is n(n-1)/2 hand shakes.