Chapter 11.2, Problem 24SR

To determine

To prove: The no. of handshakes is $\frac{n\left(n-1\right)}{2}$ after $n$ number of guests have arrived.

Answer to Problem 24SR

Theproof is given below.

Explanation of Solution

Concept used:

The poof is to be done by mathematical induction.

Step 1:

To show the given statement is true, for $n=1$,the calculation for $\frac{n\left(n-1\right)}{2}$ isgiven as:

  $\begin{array}{c}\frac{n\left(n-1\right)}{2}=\frac{0\left(0-1\right)}{2}\\ =0\end{array}$

So for one guest there will be $0$ handshakes.

So the given statement is true for $n=1$.

So the given statement is true for $n=1$.

Step 2:

Assume the statement is true for $n=k$. So,the calculation for $\frac{n\left(n-1\right)}{2}$ isgiven as:

  $\begin{array}{c}\text{The number of handshakes for}\left(k-1\right)\text{guests}=\frac{k\left(k-1\right)}{2}\\ =\frac{k^2-k}{2}\left(2\right)\end{array}$

Step 3:

To prove the result is true for $n=k+1$ .

Suppose $k+1$ guests have arrived,

By using the Step 2, the number of handshakes for $k$ guests are $\frac{k^2-k}{2}$.

As by Step 1 it is concluded that for any number of guests the no. of handshakes will be one less than that number. So, for the ${\left(k+1\right)}^{th}$ guest the number of handshakes will be $k$ (using above).

  $\begin{array}{c}\text{The number of handshakes for}\left(k+1\right)\text{guests}=\left[\begin{array}{l}\text{The number of handshakes for}\left(k\right)\text{guests}\\ +\text{number of handshakes for}{\left(k+1\right)}^{th}\text{guest}\end{array}\right]\\ =\frac{k^2-k}{2}+k\left[\text{using}\left(2\right)\right]\\ =\frac{k^2+k}{2}\\ =\frac{k\left(k+1\right)}{2}\end{array}$

Therefore the no. handshakes is $\frac{n\left(n-1\right)}{2}$ for all positive integers $n$ .