Question

2. Let S be the set of strings over the alphabet Σ = {a, b, c} defined recursively by (1) λ ∈ S and a ∈ S; and (2) if x ∈ S, then bxc ∈ S. Recall that λ denotes the empty string which has no letters and has length 0. List all strings of S which are length at most seven.

3. Prove the following theorem by induction: For every integer n ≥ 1,

1 · 2 + 2 · 3 + 3 · 4 + · · · + n(n + 1) = n(n + 1)(n + 2) 3 .

Answer 1

The recursive defination is given by ,

and   . If   then   .

Step 1 : As     

, as   denote the empty string .

As  

So we get , .

Step 2 : As  

As

So ,  

Step 3 : As  

As  

So ,  

Step 4 : As

As  

  

But these strings are of length eight and nine respectively .

Hence  list all strings of S which are length at most seven are ,

We will use induction on   to prove that ,

Base Case : For   ,

  

So the statement is true for   . .

Induction Hypothesis : Suppose the statement is true for   that is ,

Induction Step : For   .

, Using Induction hypothesis .

So the statement is true for   if we assume that it is true for . Also the statement is true for    . Hence by induncion on the statement is true for all natural number . Hence ,  

for all .

.

.

.

.

.

If you have doubt or need more clarification at any step please comment .

RATE THE ANSWER ACCORDINGLY . .