So I'm supposed to use the recursive definition of #c(s) -- the number of occurrences of the character c in A in a string s. I'm tasked with proving the lemma:
c(s * t) = #c(s) + #c(t).
I was also given the two definitions: [definitions][1][1]: https://i.stack.imgur.com/RyfAy.jpg
So far I have my basis down, by setting both s & t to the empty string and showing that the lemma holds for this case.
However, for my constructor case, I am unsure of how to show equivalence for both sides. I was going to use the constructor case of definition 3.2 in the image, but I get stuck trying to work out the right side. Any suggestions?
p.s. - i dont have 10 rep yet, so i can't post inline pics. sorry
c(s.nul) = c(s) + c(nul), . concatenation
c(s.x) = c(s) + c(x), x single letter
c(s.t.x) = c(s.t) + c(x) = c(s) + c(t) + c(x) = c(s) + c(t.x)