Suppose is finite and . Prove that .

My attempt: I try to prove it by using induction on

Base case: Suppose has 1 element, then

I don't think my base case is 'rigorous' enough, it feels there is something missing...

For induction step:

Suppose for having n elements, and ,then .

Now let has n+1 elements, let be an arbitrary element, then has n elements, then

But after that, I have no idea how to proceed at all. Please provide any hint necessary. Thanks in advance.