# recursive definitions

• Jul 28th 2007, 08:13 AM
Discrete
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)
• Jul 28th 2007, 11:02 AM
CaptainBlack
Quote:

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
• Jul 29th 2007, 08:02 AM
Discrete
Does the concatenation operator here means add? I don't really get it though
• Jul 29th 2007, 09:51 AM
CaptainBlack
Quote:

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
• Jul 30th 2007, 07:33 AM
Discrete
But then if you just concatenate the string how will we be able to find the ones in a string??
• Jul 30th 2007, 09:11 AM
CaptainBlack
Quote:

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
• Jul 31st 2007, 08:32 PM
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?
• Jul 31st 2007, 10:31 PM
CaptainBlack
Quote:

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
• Aug 1st 2007, 04:07 PM
Discrete
so what's the base case here? how do I proof part b by using structural induction??
• Aug 1st 2007, 08:38 PM
CaptainBlack
Quote:

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
• Aug 1st 2007, 09:21 PM
Discrete
what does b', b* means??

so there are two base case here?
• Aug 1st 2007, 10:50 PM
CaptainBlack
Quote:

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:

Quote:

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