Recursion of Binary Strings

gizmoguy19 · 2012-07-08 12:03:43

Hi
I came across these two binary recursion questions in one of my course notes and had trouble understanding how to solve them. Any help would be appreciated:

1. Let C be the set of strings defined by:
(a) {abc, ccbb} contained in C and
(b) for each x in C, xa, xac, xbc in C
Define a recursive sequence (c_n) that gives the number of strings in C of length n. Start with n=0.

2. Let B be the set of binary strings defined by:
(a) {1} contained in B and
(b) for each x in the set B, x01, x001 in the set B
Show B=C where C is the set of all binary strings that have no 2 consecutive 1's and no 3 consecutive 0's, and start and end with 1.

thanks!

anonimnystefy · 2012-07-08 22:47:32

Hi gizmoguy19

1: Say we already know the number of strings of length n-2 and n-1 which are c(n-2) and c(n-1) respectively. Now look at the second part of the definition. We can add either just a, which increases the length by 1, or ac and bc, which increases the string lwngth by 2. So, to get all strings of length n, you can add a to all strings of length n-1, or add ac to all strings of length n-2 or add bc to all strings length n-2. That will give us c(n-1)+c(n-2)+c(n-2) strings of length n. That means that:

c(n)=c(n-1)+2*c(n-2)

Just solve this recursive equation to get the general form of c(n).

bobbym · 2012-07-09 01:08:45

Hi gizmoguy19;

For 2) I am having trouble even understanding the question.

C is the set of all binary strings that have no 2 consecutive 1's and no 3 consecutive 0's, and start and end with 1

C are Padovan's spiral numbers. The generating function is

I can find recurrences for the sequence

and even a closed form but then what do I do?

anonimnystefy · 2012-07-09 01:15:04

Hi bobbym

It is needed to be proven that the num ers from that sequence begin and end with a 1, don't have 2 consecutive 1s in them (so no numbers like 101101) or 3 consecutive 0s in them (no numbers lik 10001).

bobbym · 2012-07-09 01:24:00

Hi;

How can you prove that about a sequence when he has not provided any properties of the sequence? I have found them myself.

anonimnystefy · 2012-07-09 01:27:01

He has given the process by which the sequence is made and left other things to us. He didn't know it was Padovan's spiral sequence.

bobbym · 2012-07-09 01:29:09

Hi;

That is the point, I do not understand that process. It is written in jargonese, a language I do not speak.

anonimnystefy · 2012-07-09 01:53:21

Here it is a little formalised:

bobbym · 2012-07-09 01:59:36

Hmmm. Let's say we have the sequence:

202
3005
20007
700002
.
.
.

prove that the first and last digits are a prime. The question does not make any sense. How the heck can I prove that?

Let B be the set of binary strings defined by:
(a) {1} contained in B and
(b) for each x in the set B, x01, x001 in the set B

This is what I am asking the question about.

anonimnystefy · 2012-07-09 02:00:50

But do you have a formal definition of tjat sequence?

bobbym · 2012-07-09 02:05:29

Nope, he gave it to me. So that fact that there is no 3 zeroes and no two ones and the ends are ones is a given. You could say that is the definition of the sequence. You do not have to prove definitions.

careless25 · 2012-07-09 03:16:35

hi bobbym,
I think an example might help:

Let B be the set of binary strings dened by
(a) {E,0} contained in B; and (where "E" is an empty string)
(b) for each s in the set B; s1 in set B and s10 in set B:
Show that B = C, where C is the set of all binary strings that do not have 2 consecutive
zeros.

Solution:

First we show that C is contained in B and finally B is contained in C.. Let P(n) be the statement that every binary string
of C of length at most n is in B. We use Mathematical Induction to show that P(n) is true
for all non-negative integers n.
Conditions (a) and (b) imply that P(0) and P(1) are both true. This completes the basis
step.

Induction Hyothesis: For n > 1, assume P(n - 1) is true.

Induction Step:

Let s be any binary string of C of length n. If s ends with a 1, then s = t1 where t is a binary string of C of length n-1.
Since P(n-1) is true, t is in B. By condition (b), s = t1 is in B.
If s ends with a 0, then s = t10, since s has no consecutive zeros, and t is a binary string of C of length n - 2.
Since P(n - 1) is true, t is in B.
By condition (b), s = t10 is in B.
Therefore P(n) is true.

By Mathematical Induction, P(n) is true for all positive integers n. Therefore C is contained in B.

Now we show B is contained in C. Let B(i) be the set of all strings of B that can be obtained by applying operation (b) at most i times.
For example, B(0) = {E,0} and B(1) = {E,0,1,10,01,010}.
Let Q(n) be the statement that B(n) is contained in C.

By Inspection, Q(0) is true. This completes the basis step.

Hypothesis: For n > 0, assume Q(n - 1) is true.
Induction Step:
Clearly B(n) = {E,0} union {b1|b in B(n-1)} union {b10| b in B{n-1)}.
If string b does not have any consecutive zeros, then neither does string b1.
Since B(n-1) is contained in C by our hypothesis, {b1|b in B(n-1)} is contained in C.
If string b does not have any consecutive zeros, then neither does string b10.
Since B(n-1) is contained in C by our induction hypothesis, {b10|b in B(n-1)} is contained in C. Therefore, Bn is contained in C;
that is, Q(n) is true. This completes the inductive step.

Therefore B = C.

bobbym · 2012-07-09 06:19:29

Hi careless25;

Thanks for providing your proof!

anonimnystefy · 2012-07-09 09:29:08

bobbym wrote:

Nope, he gave it to me. So that fact that there is no 3 zeroes and no two ones and the ends are ones is a given. You could say that is the definition of the sequence. You do not have to prove definitions.

Thatis the definition of the set C,but you have to prove that is also the definition of set B.

gizmoguy19 · 2012-07-09 12:23:53

Thanks for your responses, it was greatly appreciated.

anonimnystefy · 2012-07-09 14:10:28

Hi gizmoguy19

We still haven't finished discussing the second problem. You might wanna stick around a bit more.

bobbym · 2012-07-09 20:46:31

Hi;

How about post #12?

anonimnystefy · 2012-07-09 22:58:59

That ian't the proof of the original problem.

bobbym · 2012-07-10 01:29:11

It isn't? Then which is it a proof of?

anonimnystefy · 2012-07-10 01:32:20

I think that was an example. To the OP or to you, I have no idea.

bobbym · 2012-07-10 02:21:10

Thatis the definition of the set C,but you have to prove that is also the definition of set B.

Now you are learning! trouble is I am deader than disco!

anonimnystefy · 2012-07-10 03:00:47

What about the Latin language?

bobbym · 2012-07-10 03:16:22

Per omnia saecula seculorum.

anonimnystefy · 2012-07-10 04:09:37

Are you deader than it?

bobbym · 2012-07-10 05:08:33

Yep, when it comes to going any further for the OP.

Math Is Fun Forum

#1 2012-07-08 12:03:43

Recursion of Binary Strings

#2 2012-07-08 22:47:32

Re: Recursion of Binary Strings

#3 2012-07-09 01:08:45

Re: Recursion of Binary Strings

#4 2012-07-09 01:15:04

Re: Recursion of Binary Strings

#5 2012-07-09 01:24:00

Re: Recursion of Binary Strings

#6 2012-07-09 01:27:01

Re: Recursion of Binary Strings

#7 2012-07-09 01:29:09

Re: Recursion of Binary Strings

#8 2012-07-09 01:53:21

Re: Recursion of Binary Strings

#9 2012-07-09 01:59:36

Re: Recursion of Binary Strings

#10 2012-07-09 02:00:50

Re: Recursion of Binary Strings

#11 2012-07-09 02:05:29

Re: Recursion of Binary Strings

#12 2012-07-09 03:16:35

Re: Recursion of Binary Strings

#13 2012-07-09 06:19:29

Re: Recursion of Binary Strings

#14 2012-07-09 09:29:08

Re: Recursion of Binary Strings

#15 2012-07-09 12:23:53

Re: Recursion of Binary Strings

#16 2012-07-09 14:10:28

Re: Recursion of Binary Strings

#17 2012-07-09 20:46:31

Re: Recursion of Binary Strings

#18 2012-07-09 22:58:59

Re: Recursion of Binary Strings

#19 2012-07-10 01:29:11

Re: Recursion of Binary Strings

#20 2012-07-10 01:32:20

Re: Recursion of Binary Strings

#21 2012-07-10 02:21:10

Re: Recursion of Binary Strings

#22 2012-07-10 03:00:47

Re: Recursion of Binary Strings

#23 2012-07-10 03:16:22

Re: Recursion of Binary Strings

#24 2012-07-10 04:09:37

Re: Recursion of Binary Strings

#25 2012-07-10 05:08:33

Re: Recursion of Binary Strings

Board footer