1. ## recursive definitions

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)

2. Originally Posted by Discrete
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)
a)

ones("0")=0
ones("1")=1

ones(s|"0")=ones(s)
ones(s|"1")=ones(s)+1

where | is the concatenation operator

RonL

3. Does the concatenation operator here means add? I don't really get it though

4. Originally Posted by Discrete
Does the concatenation operator here means add? I don't really get it though
We are talking of bit strings. Contatenation adjoins one bit string to the
other, thus "101"|"11"="10111".

In the context of strings "add" has no sensible meaning.

RonL

5. But then if you just concatenate the string how will we be able to find the ones in a string??

6. Originally Posted by Discrete
But then if you just concatenate the string how will we be able to find the ones in a string??
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

7. so the suggested algorithm here is that we start from the beginning of the string and separate a single string from the back and check if it's a one or zero, if it's a one then we add one right?

8. Originally Posted by Discrete
so the suggested algorithm here is that we start from the beginning of the string and separate a single string from the back and check if it's a one or zero, if it's a one then we add one right?
Yes

9. so what's the base case here? how do I proof part b by using structural induction??

10. Originally Posted by Discrete
so what's the base case here? how do I proof part b by using structural induction??
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

11. what does b', b* means??

so there are two base case here?

12. Originally Posted by Discrete
what does b', b* means??

so there are two base case here?
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:

The base case is that for all bit strings s and bit strings b of length 1:

ones(s|b) = ones(s) + ones(b)
This is trivial true because of the way the recursive definition of ones is set up.

RonL

RonL