Description
Problem 1. (25 points)
1. Show that Pn
j=1(aj − aj−1) = an − a0, where a0, a1, . . . , an is a sequence of real numbers.
This type of sum is called telescoping.
2. Sum both sides of the identity k
2 − (k − 1)2 = 2k − 1 from k = 1 to k = n and use the previous step
to find:
a. a formula for Pn
k=1(2k − 1).
b. a formula for Pn
k=1 k.
3. Use the technique given in step 1, together with the results of step 2, to derive the formula for Xn
k=1
k
2
.
Hint: take ak = k
3
in the telescoping sum in step 1.
Problem 2. (25 points)
Solve the recurrence relation:
1. An = 2 · An−1 + 3, where A0 = 1
2. An = An−1 + 4n − 2, where A0 = 1
Problem 3. (25 points)
Let V = {S, A, B, a, b} and T = {a, b}. Find the language generated by the grammar (V, T, S, P) when the
set P of production rules consists of
1. S → AB, A → ab, B → bb.
2. S → AB, S → aA, A → a, B → ba.
3. S → AB, S → AA, A → aB, A → ab, B → b.
4. S → AA, S → B, A → aaA, A → aa, B → bB, B → b.
5. S → AB, A → aAb, B → bBa, A → λ, B → λ.
1
Problem 4. (25 points)
Find a phrase-structure grammar for each of these languages.
1. the set consisting of the bitstrings 00, 11, and 010.
2. the set of bitstrings that start with 10 and end with one or more 1s.
3. the set of bitstrings consisting of an odd number of 0s followed by a final 1.
4. the set of bitstrings that have neither two consecutive 0s nor two consecutive 1s.
Aggie Honor Statement: On my honor as an Aggie, I have neither given nor received any unauthorized
aid on any portion of the academic work included in this assignment.
Checklist: Did you…
1. abide by the Aggie Honor Code?
2. solve all problems?
3. start a new page for each problem?
4. show your work clearly?
5. type your solution?
6. submit a PDF to eCampus?
2
