[Math] These sets are written in set generator form. Write the sets in list of elements form.

computer sciencediscrete mathematics

These sets are written in set generator form. Write the sets in list of elements form.

a)$\{\frac{1}{n}: n = 1,2,3,4\}$

b)$\{n^2-n: n = 0,1,2,3,4\}$

I have no idea how to even attempt this…If someone can show me just one or an example of one being done I know for a fact I can do the rest. My book is awful.

Best Answer

Your set, rewritten:

$\{\frac{1}{n} : n \in \{1,2,3,4\}\}$

The set given by elements:

$\{\frac{1}{1},\frac{1}{2},\frac{1}{3},\frac{1}{4}\}$

They all fulfill the requirment that the denominator is either 1,2,3 or 4 while the numerator is 1.

$\{n^2 - n : n \in \{0,1,2,3,4\}\}$

It is clear that

$0^2 - 0 = 0$

$1^2 - 1 = 0$

$2^2 - 2 = 2$

$3^2 - 3 = 6$

$4^2 - 4 = 12$

i.e the set is:

$\{0,2,6,12\}$

Intuition

I think it helps to work from the far right corner. Now add a diagonal to the left. The patterns are like

0 0  1 0  0 1  1 1
 0    1    1    0

So, if we want to extend a triangle, we need only know the leftmost edge and the bottom entry. Every time the entry above our working entry is a 1, the sign of our next entry switches. This means we need an even number of 1s to have the new top entry match the bottom entry. If we do have an even number of 1s in the left column, it doesn't matter if we start with a 0 or a 1 on the bottom we will get the same thing at the top.

Example: In the below example we pick a 0 for the new bottom entry and observe that the new top entry is also a 0 (and that the number of ones in the new edge is still even).

1 1 0     1 1 0     1 1 0     1 1 0    0 1 1 0
 0 1       0 1       0 1     1 0 1      1 0 1
  1         1       1 1       1 1        1 1
           0         0         0          0

Answer ($ 2^{\lceil n/2 \rceil}$)

We first note that if a triangle's output matches its input, that this is true for every "sub triangle" (whereby sub triangle we mean a triangle you can get by deleting some of the columns from the left).

We will, therefore, induct on the size of the triangles, denoted $n$. Denote the number of "good" by $T_n$.

I claim that $T_n = 2^{\lceil n/2 \rceil}$. More specifically, if $n$ is even the $T_{n+1} = 2T_{n}$ and if $n$ is odd, $T_{n+1} = T_n$. Moreover, if $n$ is even, all of the triangles will have an even number of ones on the left size, and if $n$ is odd, half the triangles will have an even number of ones on the left side.

Proof:

$n$ is even: By hypothesis the left side of every triangle has an even number of ones. Therefore, for each triangle we will have two more triangles of size $n+1$ (corresponding to a 0 or a 1 in the new bottom point). However, the triangle corresponding to a 0 will have an odd number of ones.
$n$ is odd: By hypothesis, half the triangles have an odd number of ones on the left edge. These are never sub-triangles for larger triangles. Each of the triangles with an even number of ones on the left edge gives two new triangles of size $n+1$ (again corresponding to a 0 or a 1 in the new bottom point). However, this time, both new triangles have an even number of ones on the left side.

Best Answer

Related Solutions

How many of these strings have the property that they are the same as their output string

Intuition

Answer ($ 2^{\lceil n/2 \rceil}$)

Related Question