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

2 AnswersI 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<i<k<j<n$ 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<n-1$ 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

0 Asked on January 18, 2021 by lio

1 Asked on January 18, 2021 by gregorystory16

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

0 Asked on January 18, 2021

least squares linear programming mathematical modeling numerical methods parameter estimation

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

0 Asked on January 18, 2021 by mnishaurya

1 Asked on January 18, 2021 by thinkingeye

0 Asked on January 18, 2021 by a-kvle

0 Asked on January 18, 2021 by jp-sugarbroad

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

3 Asked on January 18, 2021 by jeongbyulji

1 Asked on January 18, 2021 by user462999

2 Asked on January 17, 2021 by w2s

algebra precalculus calculus polynomials real analysis roots

2 Asked on January 17, 2021 by jesse-elliott

1 Asked on January 17, 2021 by josh-ng

1 Asked on January 17, 2021 by fabrizio-gambeln

1 Asked on January 17, 2021 by wiza

0 Asked on January 17, 2021 by alan-simonin

2 Asked on January 17, 2021

0 Asked on January 17, 2021 by hoang-skadi

Get help from others!

Recent Answers

- Vincent on Safe to put tiles on top of two 3/4″ fir board layers & Ditra-Heat?
- FreeMan on How can I repair a split copper pipe in place?
- Quoc Vu on Safe to put tiles on top of two 3/4″ fir board layers & Ditra-Heat?
- d.george on How can I repair a split copper pipe in place?
- Harper - Reinstate Monica on How can I repair a split copper pipe in place?

© 2021 InsideDarkWeb.com. All rights reserved.