Prove the Handshake Theorem by induction 
Let $n \in \mathbb{N}$, and assume $n \geq 1$. Suppose you are at a party of $n$ people (including yourself). At the end of the party, define a person's parity as odd if they have shaken hands with an odd number of people, and even if they have shaken hands with an even number of people. Prove that the number of people of odd parity must be even.

My approach is first we find the base case, which is when $n = 1$, then there are $0$ people have shaken hands with an odd number of people, and $0$ is even, we are done.
For the induction step, we assume that for $k \in \mathbb{N}$ number of people, the number of people of odd parity must be even, we want to show for $k+1$ number of people, the number of people of odd parity is even as well. I tried to split it into two cases:

*

*Case 1: The new person's parity is even

*Case 2: The new person's parity is odd


But then I'm kind of stuck and don't know what to do since there are so many cases that can be and I wonder if there's a smarter approach.

When a new person is added, that person shakes hands with $p$ people and that alter the previous parity.
Assuming the statement true for some k:

*

*There are $k_1$ even people

*There are $k_2$ odd people and $k_2$ mod $2$ = $0$
Adding a new person who shake hands with $p$ people (case $k+1$)

*

*If he shakes hands with $p_1$ even people, that people become odd

*If he shakes hands with $p_2$ odd people, that people become even

*$p_1$ + $p_2$ = $p$
The new number of odd people are:

*

*Case1: $k_2$ - $p_2$ + $p_1$ + 1 if $p$ is odd

*Case2: $k_2$ - $p_2$ + $p_1$ if $p$ is even

By induction hypothesis, $k_2$ is even.
And because $p_1$ - $p_2$ = $p$ - $2p_2$ we can conclude that $p_1$ - $p_2$ = $p$ mod $2$
In both cases, the number of odd people is even.
