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.
Solution.
1.
Xn
j=1
(aj − aj−1) = a1 − a0 + a2 − a1 + a3 − a2 + a4 − a3 . . . + an − an−1 + an−1 − an−2 + an−2 − an−3
= ✚a✚1 − a0 +✚a✚2 −✚a✚1 +✚a✚3 −✚a✚2 +✚a✚4 −✚a✚3 . . . + an −✘an✘−1 +✘an✘−1 −✘an✘−2 +✘an✘−2 −✘an✘−3
= an − a0
1
2.
Xn
k=1
(2k − 1) =Xn
k=1
k
2 − (k − 1)2
Let ak = k
2
=
Xn
k=1
ak − (ak − 1)2
=n
2
Xn
k=1
(2k − 1) =n
2
Xn
k=1
2k −
Xn
k=1
1 = n
2
2
Xn
k=1
k − n = n
2
2
Xn
k=1
k = n
2 + n
Xn
k=1
k =
n
2 + n
2
Xn
k=1
(2k − 1) =n(n + 1)
2
3.
Leta
k = k
3
so,
ak − ak−1 = k
3 − (k − 1)3
k
3 − (k − 1)3 = k
3 − (k
3 − 1 − 3k
2 + 3k)
= 1 + 3k
2 − 3k
k
2 =
k
3 − (k − 1)3 + 3k − 1
3
Xn
k=1
k
2 =
1
3
Xn
k=1
k
3 − (k − 1)3 + 3k − 1
=
1
3
(
Xn
k=1
k
3 − (k − 1)3 +
Xn
k=1
3k −
Xn
k=1
1)
Xn
k=1
k
2 = n
3 − 0 + 3
n(n + 1)
2
− n
Xn
k=1
k
2 =
n(n + 1)(2n + 1)
6
2
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
Solution.
1.
An = 2 · An−1 + 3, where A0 = 1
An = 2An−1 + 3
An−1 = 2An−2 + 3
An−2 = 2An−3 + 3
An = 2(2(2An−3 + 3) + 3) + 3
An = 23An−3 + 3(3)
An = 2nA0 + 3n Since A0 = 1
An = 2n + 3n
2.
An = An−1 + 4n − 2, where A0 = 1
3
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 → λ.
Solution.
1. S → AB, A → ab, B → bb.
From S we get AB
From A we now have abB
From B we now have aabb
∴ the language is {aabb}
2. S → AB, S → aA, A → a, B → ba.
From S we get AB
From A we now have aB
From B we now have {aba}
Also, from S we get aA
From A we now have {aa}
∴ the language is {aba, aa}
3. S → AB, S → AA, A → aB, A → ab, B → b. From S we get AB
From A we now have aBB
Using B twice we get abb
From S we get AA
From A we now have aBaB
Using B twice we get abab
∴ the language is {abb, abab}
4. S → AA, S → B, A → aaA, A → aa, B → bB, B → b.
From S we get AA
From both A’s we forms of A such that aaaa or aaaaa or aaaaaa or aaaaaaaa, strings of even a’s with
minimum size of 4
Using S → B to dervive B we get forms of b, bb, bbb, such that it results in strings of b greater than 1
∴ the language is {a · 2
n | n ≥ 2} ∪ {b
2
| n ≥ 1}
5. S → AB, A → aAb, B → bBa, A → λ, B → λ From S we get AB
From A we get aBa all the way to ababababab . . . AB until λ depending on x number of repetitions
From B we get abbaAB all the way to ababababab . . . AB until λ depending on y number of repetitions
∴ the language is of the form {a
x+y
b
x+y
| x ≥ 0, y ≥ 0}
4
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.
Solution.
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. the set consisting of the bitstrings 00, 11, and 010. With L = {00, 11, 010}
The phrase structure gammer of this language is G = {V, T, S, P}
The Vocabulary (V ) = {0, 1, S} and the terminal symbols are T = {0, 1}
The productions are S → 00, S → 11, and S → 010
2. the set of bitstrings that start with 10 and end with one or more 1s.
The language L = {a : a is a bit string that starts with 10 and end with one or more 1s}
The phrase structure gammer of this language is G = {V, T, S, P}
The Vocabulary (V ) = {0, 1, S, A, B} and the terminal symbols are T = {0, 1}
The productions are S → 10AB, A → AA, A → 1, A → 0, B → BB, B → 1
3. the set of bitstrings consisting of an odd number of 0s followed by a final 1.
The language L = {a : a is a bit string of odd number of 0s followed by a final 1}
The phrase structure gammer of this language is G = {V, T, S, P}
The Vocabulary (V ) = {0, 1, S, A, B, C} and the terminal symbols are T = {0, 1}
The productions are S → A1, A → λ, A → BBC, A → BCB, A → CBB, B → CB, B → BC, B →
1, C → 0
4. the set of bitstrings that have neither two consecutive 0s nor two consecutive 1s.
The language L = {a : a is a bit string that has neither two consecutive 0s nore two consecutive 1s}
The phrase structure gammer of this language is G = {V, T, S, P}
The Vocabulary (V ) = {0, 1, S, A, B} and the terminal symbols are T = {0, 1}
The productions are S → A, A → AA, A → 01, A → λ, S → B, B → BB, B → 10, B → λ
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?
5
Powered by TCPDF (www.tcpdf.org)
