Ox-words: Rules, Length & Occurrences of a & b

[jammed]

Homework Statement

Ox-words are sequences of letters a and b that are constructed according to the following
rules:
I. The sequence consisting of no letters is an Ox-word.
II. If the sequence W is an Ox-word, then the sequence that begins with a, followed
by W and ending in b, written aWb, is an Ox-word.
III. If the sequences U and V are Ox-words, then the sequence U followed by V , written
UV , is an Ox-word.
All Ox-words are constructed using these rules. The length of an Ox-word is the number
of letters that occur in it. For example aabb and abab are Ox-words of length 4.
(i) Show that every Ox-word has an even length.
(ii) List all Ox-words of length 6.
(iii) Let W be an Ox-word. Is the number of occurrences of a in W necessarily equal to
the number of occurrences of b in W ? Justify your answer.
You may now assume that every Ox-word (of positive length) can be written uniquely
in the form aWbW' where W and W' are Ox-words.
(iv) For n>= 0, let Cn be the number of Ox-words of length 2n. Find an expression for
Cn+1(where n+1 = subscript) in terms of C0(where 0 = subscipt),C1(where 1 = subscript), · · · Cn (n = subscript). Explain your reasoning.

Homework Equations

no equation

The Attempt at a Solution

(i)Using rule 1 we know that there when there are no letters the word is an ox-word which means we have a word of length zero which is even no. Using rule 2 we can make a word starting with a and containing W and ending in b which will also be even as W can contain no letters or a and b. Using rule 3 then according to rule 1 and rule 2 the song U and v will also be even so every ox-word will be even.
(ii)ababab, abaabb, aabbab, aababb, aaabbb

Pls tell me how to deal with (iv) part.

 

[micromass]

Take an Ox-word of length n. Then this word can be written as aWbW' where W and W' are unique. There are now n-2 cases:

1) W is in C0
Then W' must be in Cn-2. So the number of possible words in this case are C0.Cn-2

2) W is in C1
Then W' must be in Cn-3. So the number of possible words in this case are C1.Cn-3

3) ...


After these cases you just add up all te possible words in the separate cases.