a. give a recursive definitions of the function ones(s), which counts the number of ones in a bit string s
b. use structural induction to prove that ones(st) = ones (s) + ones (t)
Let s="100110"
ones(s) = ones("10011"|"0") = ones("10011")
.......... = ones("1001"|"1") = ones("1001") + 1
.......... = ones("100"|"1") + 1 = ones("100") + 1 + 1 = ones("100") + 2
.......... = ones("10"|"0") + 2 = ones("10") + 2
.......... = ones("1"|"0") + 2 = ones("1") + 2 = 1 + 2 = 3
RonL
The base case is that for all bit strings s and bit strings b of length 1:
ones(s|b) = ones(s) + ones(b)
Then suppose it true for all bit strings s and all bit strings b of length k or less. Then:
ones(s|b)=ones(s)+ones(b)
and so if b'=b|"0":
ones(s|b') = ones((s|b)|"0")=ones(s|b)+0 = ones(s)+ones(b)
and if b*=b|"1":
ones(s|b*) = ones((s|b)|"1")=ones(s|b)+1 = ones(s)+ones(b)+1=ones(s)+ones(b|"1")=ones(s)+ones (b*).
Hence it true for all bit strings s and all bit strings b of length k+1 or less.
Therefore by induction we may conclude that it is true for all bit strings s and b.
RonL
They mean what I defined them to be b' is b concatenated with "0" and b* is b concatenated with "1" , and these are part of the inductive step.
The base case was what I said it was:
This is trivial true because of the way the recursive definition of ones is set up.The base case is that for all bit strings s and bit strings b of length 1:
ones(s|b) = ones(s) + ones(b)
RonL
RonL