I was hoping that someone could give me some help with this inductive proof problem, I'm having a hard time understanding what to do.

Thanks in advance

For any nonempty set S let : S Xlists(S) N be defined by
(x, L) = if L = <>then 0
else if x = head(L) then 1 + (x, tail(L))
else (x, tail(L)).
Write out an induction proof that, "(x, L) is the number of occurrences of x
in L."