Using mathematical induction prove that, for a finite set $S$, the largest anti-symmetric binary relation $\rho\subseteq S\times S$ is such that:
$$|\rho| = \frac{|S|(|S|+1)}{2}$$
I tried solving this problem but I couldn't reach an answer. I hope someone could help.
For one element set, size of such relation is 1, namely the only reflexive element so the result holds true. Suppose for n element set, size of such relation is A =n(n+1)/2 Now for n+1 element set, size of such relation would be A +{1 element for (p,p) if p is the n+1 th element } + { n elements in the form (i, p) where i are previous n elements}. Note that (p,i) is not a part of the relation if (p,i) is, as the relationship is anti symmetric. So adding them all we get (n+1)((n+1)+1)/2. Hence proved for all n.
Using combinatorics, the size of the relation will be {n for all the reflective tuples} + {half of n choose 2 for all the other pairs counting only once occurance of (a,b) and (b,a) where a is not equal to b as the relation is anti symmetric.}