Skriftlig Eksamen DM11

Institut for Matematik og Datalogi Odense Universitet

One set of possible solutions

Opgave 1

spørgsmål a

Pf. (by structural induction, but it can be by induction on the length of y) Basis step: The only basis element is λ and it has 0 as and 0 bs, so it has an even number of as and bs. √ Inductive step: Assume that x ∈ L has n_{1} as and n_{2} bs, and that n_{1} and n_{2} are both even.

Consider first the string y_{1} = xaa. This has n_{1} + 2 as and n_{2} bs. Since 2 | n_{1} (by the inductive hypothesis) and 2 | 2, by theorem 1 on page 113 of the textbook, 2 | n_{1} + 2. By the inductive hypothesis, n_{2} is even, so y_{1} has an even number of as and bs.

Now consider the string y_{2} = xbb. This has n_{1} as and n_{2} + 2 bs. Since 2 | n_{2} (by the inductive hypothesis) and 2 | 2, by theorem 1 on page 113 of the textbook, 2 | n_{2} + 2. By the inductive hypothesis, n_{1} is even, so y_{2} has an even number of as and bs. √

By structural induction, any string y ∈ L has an even number of as and bs. □

spørgsmål b

a_{n} = 2a_{n−2} for n ≥ 2. Initial conditions: a_{0} = 1, a_{1} = 0.

spørgsmål c

Characteristic equation: r^{2} − 2 = 0. Using the generating function (it’s not necessary)... The generating function is G(x) = ∑_{k=0}^{∞} a_{k}x^{k}. Find a nice expression for G(x):

G(x) − 2x^{2}G(x)

= ∑_{k=0}^{∞} a_{k}x^{k} − 2 ∑_{k=2}^{∞} a_{k−2}x^{k}

= a_{0} + a_{1}x + ∑_{k=2}^{∞}(a_{k} − 2a_{k−2})x^{k}

= 1 Thus, (1 − 2x^{2})G(x) = 1.

G(x) = \frac{1}{1−2x^{2}}

= \frac{1}{(1+\sqrt{2}x)(1−\sqrt{2}x)} = \frac{1/2}{(1+\sqrt{2}x)} + \frac{1/2}{(1−\sqrt{2}x)}

= \frac{1}{2} ∑_{n=0}^{∞}(\sqrt{2})^{n}x^{n} + \frac{1}{2} ∑_{n=0}^{∞}(−\sqrt{2})^{n}x^{n}

So, a_{n} = \frac{1}{2}((\sqrt{2})^{n} + (−\sqrt{2})^{n}) for n ≥ 0.

Opgave 2

spørgsmål a

By the Binomial Theorem, ∑_{j=0}^{n} ( \begin{matrix}n \\ j \end{matrix} ) 2^{j}3^{n−j} = (2 + 3)^{n} = 5^{n}.

spørgsmål b

We note that if n ≥ k ≥ 1, n > 1, then ( \begin{matrix}n \\ k \end{matrix} ) = \frac{n!}{k!(n−k)!} = \frac{n(n−1)!}{k(k−1)!((n−1)−(k−1))!} =

\frac{n}{k} ( \begin{matrix}n − 1 \\ k − 1 \end{matrix} ).

∑_{k=1}^{n}(−1)^{k−1}k ( \begin{matrix}n \\ k \end{matrix} ) = ∑_{k=1}^{n}(−1)^{k−1}k \frac{n}{k} ( \begin{matrix}n − 1 \\ k − 1 \end{matrix} )

= n ∑_{k=1}^{n}(−1)^{k−1} ( \begin{matrix}n − 1 \\ k − 1 \end{matrix} )

= n ∑_{j=0}^{n−1}(−1)^{j} ( \begin{matrix}n − 1 \\ j \end{matrix} )

= n ∑_{j=0}^{n−1}(−1)^{j}1^{n−1−j} ( \begin{matrix}n − 1 \\ j \end{matrix} )

= (−1 + 1)^{n−1}

= 0.

Opgave 3

spørgsmål a

This is the same as the number of ways to choose 5 different positive integers from the first n, so the answer is ( \begin{matrix}n \\ 5 \end{matrix} ).

spørgsmål b

The number of possible ways to choose the 5 numbers is n^{5}, so the probability of getting one of the K_{n} we are interested in is K_{n}/n^{5}.

spørgsmål c

This is the geometric distribution with p = p_{n}, so the expected number of trials is 1/p_{n}. (This can also be calculated directly.)

spørgsmål d

For the first 4 numbers in the sequence, after you choose them, the next larger number is not a possibility, so you are choosing four pairs of numbers and one extra. This is the same as choosing 5 numbers from n − 4, so the answer

is ( \begin{matrix}n − 4 \\ 5 \end{matrix} ).

Opgave 4

spørgsmål a

R is reflexive because if (a, b, c) ∈ A, then 5 | 0 = a + b + c − (a + b + c). Thus, ((a, b, c), (a, b, c)) ∈ R.

R is symmetric because if ((a, b, c), (x, y, z)) ∈ R, then 5 | w = (a+b+c−(x+ y+z)), so 5 | w·(−1) by theorem 1 on page 113. Thus 5 | (x+y+z−(a+b+c)), so ((x, y, z), (a, b, c)) ∈ R.

R is transitive because if ((a, b, c), (x, y, z)) ∈ R and ((x, y, z), (i, j, k)) ∈ R, then 5 | u = (a + b + c − (x + y + z)) and 5 | v = (x + y + z − (i + j + k)) so by theorem 1 on page 113, 5 | u+v = (a+b+c−(x+y+z)+x+y+z−(i+j+k)) = (a + b + c − (i + j + k)). Thus ((a, b, c), (i, j, k)) ∈ R.

Thus, R is an equivalence relation. □

spørgsmål b

There are 5 equivalence classes. The are the tuples where the numbers sum up to something congruent to 0 modulo 5, the tuples where the numbers sum up to something congruent to 1 modulo 5, the tuples where the numbers sum up to something congruent to 2 modulo 5, the tuples where the numbers sum up to something congruent to 3 modulo 5, and the tuples where the numbers sum up to something congruent to 4 modulo 5.

Opgave 5

spørgsmål a

Let H = {x | x is a cube}. The identity e is an element of H since e⊙e⊙e = e. Suppose x, y ∈ H. Then, there exist a, b ∈ G such that x = a ⊙ a ⊙ a and y = b ⊙ b ⊙ b. Hence, x ⊙ y = a ⊙ a ⊙ a ⊙ b ⊙ b ⊙ b = (a ⊙ b) ⊙ (a ⊙ b) ⊙ (a ⊙ b), since G is abelian. Thus, x ⊙ y ∈ H. Since a ∈ G, a has an inverse a^{−1} ∈ G. Let u = a^{−1} ⊙ a^{−1} ⊙ a^{−1}. Then, x ⊙ u = a ⊙ a ⊙ a ⊙ a^{−1} ⊙ a^{−1} ⊙ a^{−1} = e, so u is the inverse of x and is in H. This shows that H is a subgroup of G. □

spørgsmål b

G is cyclic and g is a generator. G has order n and 3 | n.

Since 3 | n, n/3 and 2n/3 are integers. Since G is associative g^{n/3} ⊙ g^{n/3} ⊙ g^{n/3} = g^{n/3+n/3+n/3} = g^{n}. By a corollary to LaGrange’s Theorem (or more directly by an earlier theorem), g^{n} = e, so g^{n/3} is a cube root of e. Again since G is associative g^{2n/3} ⊙ g^{2n/3} ⊙ g^{2n/3} = g^{2n/3+2n/3+2n/3} = g^{2n} = (g^{n})^{2} = e^{2} = e. Thus, g^{2n/3} is also a cube root of e. Clearly, e is a cube root of e since e ⊙ e ⊙ e = e. □

spørgsmål c

Suppose that e has some other cube root h. Since g is a generator, there exists some integer k such that 0 ≤ k ≤ n − 1 and h = g^{k}. Now, e = h ⊙ h ⊙ h = g^{k} ⊙ g^{k} ⊙ g^{k} = g^{3k} by associativity. Let s = gcd(3k, n). There exist integers u, v such that s = 3ku + nv. So g^{s} = g^{3ku+nv} = g^{3ku} ⊙ g^{nv} = (g^{3k})^{u} ⊙ (g^{n})^{v} = e⊙e = e. By a theorem from the notes, n is the least positive integer such that g^{n} = e, so s ≥ n. Thus, n | 3k, and k is a multiple of n/3. Since 0 ≤ k ≤ n−1, k is 0, n/3, or 2n/3. Thus, h is one of the three cube roots mentioned in the previous problem, and there are no more cube roots of e. □

spørgsmål d

Suppose x is a cube in G. Then, there exists y ∈ G such that y ⊙ y ⊙ y = x. Note, that in problem (a), we showed that y^{−1} ⊙ y^{−1} ⊙ y^{−1} = (y ⊙ y ⊙ y)^{−1}. Suppose z is another cube root of x. Consider a = z⊙y^{−1}. Note that a⊙a⊙a = z ⊙ z ⊙ z ⊙ y^{−1} ⊙ y^{−1} ⊙ y^{−1} = x ⊙ (y ⊙ y ⊙ y)^{−1} = x ⊙ x^{−1} = e, where the first equality is by associativity. Thus a is a cube root of e. Thus, z = y ⊙a, where a is a cube root of e, so the only possible cube roots of x are y⊙e = y, y⊙g^{n/3}, and y ⊙g^{2n/3}. These are all distinct, and performing the multiplications shows that they are all cube roots of x. Thus, any cube in G has exactly 3 cube roots. □