I'm supposed to prove this by induction. I already proved it by contradiction, but I am lost on how to set it up for induction.
Prove that if at least two people are at a party, at least two of them know the same number of people. We assume that if person 1 knows person 2, then person 2 knows person 1. We also assume that a person doesn't count themselves in how many people they know.
Any ideas?
Since the statement is only true for $n\geq2$ people, the case $n=2$ must be the base case. As usual the base case is easily proved: the two people either both know $0$ or both know $1$ other person.
Now suppose $n>2$ and that it has been shown that among any group of $n-1$ people there are always two that know the same number of other people in that group. We distinguish two cases.
At least one of the $n$ people knows none of the other people. As the relation is symmetric, the remaining $n-1$ people don't know that person either, and considering just them as a group does no change the number of people known by any of them; the induction hypothesis shows that two among them know the same number of other people.
Everyone knows at least one of the other people. Now we have $n$ people, each of which know a number $i\in\{1,2,\ldots,n-1\}$ other people. By the pigeonhole principle, at least one value of $i$ is shared by two or more people.
Added. In reply to the comment by Brian M. Scott, I note that when wrinting this proof I originally had three bullets: the two above, and a second inductive case between them for when at least one person knows all the others (removing that person decreases everyone else's number of acquaintences by$~1$, and hence does not change their relation of having the same number of them). However I realised that this reduced the number of remaining values for $i$ to $n-2$, giving me more than I actually needed to apply the pigeonhole principle, so I then dropped the second bullet.
Taking this up differently, this also allows to do things without using induction at all (though that would invalidate the answer): one clearly cannot both have a person that knowns nobody, and a person that knows everybody (would they know each other?), so in any case only $n-1$ of the $n$ values $0,1,\ldots,n-1$ are left to be taken, and the pigeonhole principle can be applied directly.