# How to use general recursion to generate a set of words?

I am just getting to recursion in one of my classes, and I’m a bit confused on how to go about generating a set of words and the notation.

Given the following question, how would I go about generating this set?

(assuming ∑={a,b}), the set of strings with twice as many a’s as b’s.


If I start by saying that λ∈T as my base case, how would I then generate the recursive case?

Mathematics Asked by Pwelb on November 14, 2021

I would also include in the base case the three minimal non-empty strings in $$T$$:

• $$lambda,aab,aba,baain T$$
• If $$u,vin T$$, and $$v=xy$$, then $$xuyin T$$. (Note that $$x$$ or $$y$$ can be empty.)

The hard part is going to be proving that this actually generates all of $$T$$; this will be the case if and only if every $$uin Tsetminus{lambda,aab,aba,baa}$$ has a proper substring in $$T$$. (Why?)

HINT: Set $$c_0=0$$, and for $$k=1,ldots,n$$ let

$$x_k=begin{cases} c_{k-1}+1,&text{if }x_k=a\ c_{k-1}-2,&text{if }x_k=b;; end{cases}$$

note that $$c_n=0$$, since $$uin T$$.

• Show that if $$c_k=0$$ for some $$kin{1,ldots,n-1}$$, $$u$$ has a proper substring in $$T$$.
• Suppose that $$c_i>0$$ for $$i=1,ldots,n-1$$, and let $$c_k=max{c_i:0le ile n}$$. Show that there are $$i,j$$ such that $$0 and $$c_i=c_j$$ and conclude that $$u$$ has a proper substring in $$T$$. (Use the fact that although it decreases by $$2$$ when it decreases, the counter $$c$$ only ever increases by $$1$$. Thus, it can skip over a value when decreasing but not when increasing.)
• Prove a similar result in the case that $$c_i<0$$ for $$i=1,ldots,n-1$$.
• Show that the only remaining possibility is that $$c_k=c_{n-1}=-1$$ for some $$k$$ such that $$2le k and again conclude that $$u$$ has a proper substring in $$T$$.

It may help to realize that these bullet points correspond to the following types of strings, respectively:

• $$u=vw$$ for some non-empty $$v,win T$$.
• Every non-empty proper initial segment of $$u$$ has too many $$a$$s to be in $$T$$.
• Every non-empty proper initial segment of $$u$$ has too many $$b$$s to be in $$T$$.
• $$u$$ has the form $$xva$$, where $$xa,vin T$$, every non-empty proper initial segment of $$x$$ has too many $$a$$s, $$x$$ ends in $$b$$, and $$xnotin T$$.

Answered by Brian M. Scott on November 14, 2021

Edit: Please consider accepting @Brian M. Scott's answer as it is complete and more rigorous.

(Too large for a comment, but I hope it will give you some insight.)

Generate 2 $$a$$'s for each $$b$$. First, you have 3 possibilities ($$1^{st}$$ generation). $$mathbf{w}_1^1=aab, mathbf{w}_2^1 = aba, mathbf{w}_3^1=baa$$ Next, generate all the possible permutations of each previous $$mathbf{w}_i^1$$, inserting each previous $$mathbf{w}_i^1$$ at each possible place ($$2^{nd}$$ generation). For example: $$mathbf{w}_1^2 = aab|mathbf{w}_1^1, hspace{10pt} mathbf{w}_2^2 = aba|mathbf{w}_1^1, hspace{10pt} mathbf{w}_3^2 = baa|mathbf{w}_1^1 \ mathbf{w}_4^2 = aa|mathbf{w}_1^1|b, hspace{10pt} mathbf{w}_5^2 = ab|mathbf{w}_1^1|a, hspace{10pt} mathbf{w}_6^2 = ba|mathbf{w}_1^1|a \ large dots$$

Note that you can insert multiple (previous) strings at different positions, for the next generation. You can go to the next generation only after you have enumerated all possible strings for the current generation, and this includes inserting multiple previous strings.

I have used the notation $$u | v$$ to denote the concatenation of $$u$$ and $$v$$, and $$mathbf{w}_i^j$$ denotes the $$i$$-th word in generation $$j$$.

You can then derive a recursive formula for $$mathbf{w}_i^j$$ using this.

Answered by Alexandru Dinu on November 14, 2021

## Related Questions

### $a,b,c,d$ such that $a^n=b^n=c^n=d^n=1$ and $a+b+c+d=1$

0  Asked on January 18, 2021 by lio

### Using L’Hopital’s rule to find the limit of this function

1  Asked on January 18, 2021 by gregorystory16

### Trigonometric graph analysis – point determination

2  Asked on January 18, 2021 by ct-27-3555

### Best representation/model of a 3D object from multiple observations

0  Asked on January 18, 2021

### Let$A$ be an open, dense set in $mathbb R^n$. Prove that $A + A = mathbb R^n$

1  Asked on January 18, 2021 by francisco-jos-letterio

### (proposed) elegant solution to IMO 2003 P1

0  Asked on January 18, 2021 by mnishaurya

### Reverse order of polynomial coefficients of type $left(r-xright)^n$

1  Asked on January 18, 2021 by thinkingeye

### Should one include already cemented proofs of related principles in one’s paper?

0  Asked on January 18, 2021 by a-kvle

### The Cauchy-Crofton formula on a plane

1  Asked on January 18, 2021 by jalede-jale-uff-ne-jale

### Solving a limit for capacity of a transmission system

3  Asked on January 18, 2021 by jeongbyulji

### Galois group Abstract algebra

1  Asked on January 18, 2021 by user462999

### Does there always exists coefficients $c,dinmathbb{R}$ s.t. $ax^3+bx^2+cx+d$ has three different real roots?

2  Asked on January 17, 2021 by w2s

### If there is a “worldly ordinal,” then must there be a worldly cardinal?

2  Asked on January 17, 2021 by jesse-elliott

### Cover number and matching number in hypergraphs.

1  Asked on January 17, 2021 by josh-ng

### $displaystyleint_C (e^x+cos(x)+2y),dx+(2x-frac{y^2}{3}),dy$ in an ellipse

1  Asked on January 17, 2021 by fabrizio-gambeln

### Show that $h_n(x)=x^{1+frac{1}{2n-1}}$ converges uniformly on $[-1, 1]$.

1  Asked on January 17, 2021 by wiza

### What does the functional monotone class theorem say and how does it relate to the other monotone class theorem?

0  Asked on January 17, 2021 by alan-simonin

### Symmetric matrix and Hermitian matrix, unitarily diagonalizable

2  Asked on January 17, 2021