jammed
- 26
- 0
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.