Discrete-math 4

1

\begin{matrix} Given: a_{1} \in R, d \in N, \forall n \geq 2 : a_{n} = a_{n - 1} + d \\ Prove: \sum_{k = 1}^{n} a_{k} = \frac{n (a_{1} + a_{n})}{2} \\ Proof: \\ Base case. Let n = 1 \\ \sum_{k = 1}^{n} a_{k} = a_{1} = \frac{1 (a_{1} + a_{n})}{2} \\ Induction step. Let \sum_{k = 1}^{n} a_{k} = \frac{n (a_{1} + a_{n})}{2} \\ a_{n} = a_{1} + (n - 1) \cdot d \\ a_{n + 1} = a_{1} + n \cdot d \\ \sum_{k = 1}^{n + 1} a_{k} = \sum_{k = 1}^{n} a_{k} + a_{n + 1} = \frac{n (a_{1} + a_{n})}{2} + a_{n + 1} = \\ = \frac{n (a_{1} + a_{n}) + 2 a_{n + 1}}{2} = \frac{n a_{1} + n a_{n + 1} - n \cdot d + a_{n + 1} + a_{1} + n \cdot d}{2} = \frac{(n + 1) (a_{1} + a_{n + 1})}{2} \\ ⟹ \forall n \in N : \sum_{k = 1}^{n} a_{k} = \frac{n (a_{1} + a_{n})}{2} ⟹ \sum_{k = 1}^{n + 1} a_{k} = \frac{(n + 1) (a_{} + a_{n + 1})}{2} \\ Base case + induction step ⟹ Proved by induction \end{matrix}

\begin{matrix} Given: P_{0} = A \\ \forall n \in N : P_{n} = \neg P_{n - 1} \lor A \end{matrix}

2a

\begin{matrix} Prove: For all odd n, P_{n} is a tautology \\ Proof: \\ Base case. Let n = 1 \\ P_{1} = \neg P_{0} \lor A = \neg A \lor A \equiv T \\ Induction step. Let P_{n} be a tautology \\ P_{n + 2} = \neg P_{n + 1} \lor A = \neg (\neg P_{n} \lor A) \lor A = (\underset{\equiv T}{\underset{⏟}{P_{n}}} \land \neg A) \lor A = \neg A \lor A \equiv T \\ ⟹ P_{n} is a tautology ⟹ P_{n + 2} is a tautology \\ \underset{By Induction}{⟹} \forall odd n : P_{n} \equiv T \end{matrix}

2b

\begin{matrix} Prove: For all even n, P_{n} = A \\ Proof: \\ Base case. Let n = 0 \\ P_{0} = A \\ Induction step. Let P_{n} = A \\ P_{n + 2} = \neg P_{n + 1} \lor A = \neg (\neg P_{n} \lor A) \lor A = (P_{n} \land \neg A) \lor A = (A \land \neg A) \lor A \equiv A \\ ⟹ P_{n} = A ⟹ P_{n + 2} = A \\ \underset{By Induction}{⟹} \forall even n : P_{n} = A \end{matrix}

3

\begin{matrix} Prove: It is possible to cover a 2^{n} \times 2^{n} grid with one cell missing, \\ with L-shaped tiles consisting of three connected cells for all natural n \\ Proof: \\ Base case. Let n = 1 \\ 2 \times 2 grid can be filled like this: (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}) \\ 0 represents the missing cell, other numbers represent the index of a tile used \\ Let us define four ways to fill this grid: \\ A_{1}^{R U} = (\begin{matrix} 1 & 0 \\ 1 & 1 \end{matrix}), A_{1}^{L U} = (\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}), A_{1}^{L L} = (\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}), A_{1}^{R L} = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) \\ Where first R/L is right or left, second U/L is upper or lower and index is the value of n \\ Induction step. \\ Now let us see if we can fill the grid for n + 1, given that we can do it for n \\ A_{n + 1} = 2^{n + 1} \times 2^{n + 1} can be represented as 2 \cdot 2^{n} \times 2^{n} \cdot 2 = 4 \cdot 2^{n} \times 2^{n} - four A_{n} grids \\ Let us compose A_{n + 1} the following way : \\ A_{n + 1} = (\begin{matrix} A_{n}^{R L} & A_{n}^{L L} \\ A_{n}^{R U} & A_{n}^{L U} \end{matrix}) = (\begin{matrix} \dots & \dots & \dots & \dots \\ \dots & 0 & 0 & \dots \\ \dots & 0 & 0 & \dots \\ \dots & \dots & \dots & \dots \end{matrix}) \\ We can see that the center has four empty cells, \\ which is logical as each A_{n} grid has one empty cell and there are four such grids \\ This empty center can be filled with one L-shaped tile: \\ (\begin{matrix} \dots & \dots & \dots & \dots \\ \dots & x & x & \dots \\ \dots & x & 0 & \dots \\ \dots & \dots & \dots & \dots \end{matrix}) \end{matrix}

\begin{matrix} Now let us prove that for any n it is possible to fill the grid as A_{n}^{L U}, A_{n}^{L L}, A_{n}^{R U}, A_{n}^{R L} \\ A_{n} = (\begin{matrix} \dots & \dots & \dots & \dots \\ \dots & 0 & x & \dots \\ \dots & x & x & \dots \\ \dots & \dots & \dots & \dots \end{matrix}) = (\begin{matrix} A_{n - 1}^{R L} & \dots \\ \dots & \dots \end{matrix}) \underset{Turn A_{n - 1}^{R L} by 180 degress}{\to} (\begin{matrix} A_{n - 1}^{L U} & \dots \\ \dots & \dots \end{matrix}) = A_{n}^{L U} \\ A_{n} = (\begin{matrix} \dots & \dots & \dots & \dots \\ \dots & x & x & \dots \\ \dots & x & 0 & \dots \\ \dots & \dots & \dots & \dots \end{matrix}) = (\begin{matrix} \dots & \dots \\ \dots & A_{n - 1}^{L U} \end{matrix}) \underset{Turn A_{n - 1}^{L U} by 180 degrees}{\to} (\begin{matrix} \dots & \dots \\ \dots & A_{n - 1}^{R L} \end{matrix}) = A_{n}^{R L} \\ A_{n} = (\begin{matrix} \dots & \dots & \dots & \dots \\ \dots & x & x & \dots \\ \dots & 0 & x & \dots \\ \dots & \dots & \dots & \dots \end{matrix}) = (\begin{matrix} \dots & \dots \\ A_{n - 1}^{R U} & \dots \end{matrix}) \underset{Transpose A_{n - 1}^{R U}}{\to} (\begin{matrix} \dots & \dots \\ A_{n - 1}^{L L} & \dots \end{matrix}) = A_{n}^{L L} \\ A_{n} = (\begin{matrix} \dots & \dots & \dots & \dots \\ \dots & x & 0 & \dots \\ \dots & x & x & \dots \\ \dots & \dots & \dots & \dots \end{matrix}) = (\begin{matrix} \dots & A_{n - 1}^{L L} \\ \dots & \dots \end{matrix}) \underset{Transpose A_{n - 1}^{L L}}{\to} (\begin{matrix} \dots & A_{n - 1}^{R U} \\ \dots & \dots \end{matrix}) = A_{n}^{R U} \\ Base case + Induction step ⟹ Proved for all n by induction \end{matrix}

4

\begin{matrix} Let a \neq 0 \in R : a + \frac{1}{a} \in Z \\ Prove: \forall n \in N : a^{n} + \frac{1}{a^{n}} \in Z \\ Proof: \\ b_{1} = a + \frac{1}{a} = \frac{a^{2} + 1}{a} \in Z \\ Let b_{n} = a^{n} + \frac{1}{a^{n}} = \frac{a^{2 n} + 1}{a^{n}} \\ ⟹ b_{n + 1} = \frac{a^{2 n + 2} + 1}{a^{n + 1}} \\ Base case. Let n = 1 \\ b_{1} = a + \frac{1}{a} ⟹ b_{1} \in Z \\ Let n = 2 \\ b_{2} = a^{2} + \frac{1}{a^{2}} = \frac{a^{4} + 1}{a^{2}} = \frac{(a^{2} + 1)^{2} - 2 a^{2}}{a^{2}} = {(\frac{a^{2} + 1}{a})}^{2} - 2 \\ \frac{a^{2} + 1}{a} \in Z ⟹ {(\frac{a^{2} + 1}{a})}^{2} \in Z ⟹ {(\frac{a^{2} + 1}{a})}^{2} - 2 = b_{2} \in Z \\ Strong induction step. Let \forall k \in [1, n] : b_{k} \in Z \\ b_{1} \cdot b_{n} = \frac{(a^{2} + 1) (a^{2 n} + 1)}{a \cdot a^{n}} = \frac{a^{2 (n + 1)} + 1 + a^{2 n} + a^{2}}{a^{n + 1}} = \\ = \underset{b_{n + 1}}{\underset{⏟}{\frac{a^{2 (n + 1)} + 1}{a^{n + 1}}}} + \underset{b_{n - 1}}{\underset{⏟}{\frac{a^{2 (n - 1)} + 1}{a^{n - 1}}}} = b_{n + 1} + b_{n - 1} ⟹ b_{n + 1} = b_{1} \cdot b_{n} - b_{n - 1} \\ b_{1}, b_{n - 1}, b_{n} \in Z ⟹ b_{1} \cdot b_{n} \in Z ⟹ b_{1} \cdot b_{n} - b_{n - 1} = b_{n + 1} \in Z \\ Base step + Strong induction step ⟹ Proved by strong induction for all n \in N \end{matrix}

5

\begin{matrix} R = {(1, 1), (1, 2), (1, 3), (2, 1), (3, 1), (2, 2)} \\ A = {1, 2}, B = {1, 2, 3} \\ Show: R = A \times B or R \neq A \times B \\ Solution: \\ (2, 3) \in A \times B, (2, 3) \notin R \\ ⟹ R \neq A \times B \\ Another reason being: \\ (3, 1) \notin A \times B, (3, 1) \in R \end{matrix}

\begin{matrix} A is a set \\ A_{1}, A_{2}, \dots, A_{n} : \forall i \in [1, n] : A_{i} \subseteq A \\ R \subseteq A \times A, R = {(x, y) \in A \times A | \exists i : x \in A_{i} \land y \in A_{i}} \end{matrix}

6a

\begin{matrix} Prove or disprove: ⋃_{i \in [1, n]} A_{i} = A ⟹ R is reflexive \\ Proof: \\ Let x \in A \\ x \in A ⟹ x \in ⋃_{i \in [1, n]} A_{i} ⟹ \exists i \in [1, n] : x \in A_{i} \\ ⟹ \exists i \in [1, n] : x \in A_{i} \land x \in A_{i} ⟺ (x, x) \in R ⟺ R is reflexive \end{matrix}

6b

\begin{matrix} Prove or disprove: R is reflexive ⟹ ⋃_{i \in [1, n]} A_{i} = A \\ Proof: \\ R is reflexive ⟺ \forall x \in A : (x, x) \in R ⟺ \forall x \in A : \exists i \in [1, n] : x \in A_{i} \\ Let x \in A \\ x \in A \underset{R is reflexive}{⟹} \exists i \in [1, n] : x \in A_{i} ⟹ x \in ⋃_{i \in [1, n]} A_{i} ⟹ 1. A \subseteq ⋃_{i \in [1, n]} A_{i} \\ Let x \in ⋃_{i \in [1, n]} A_{i} \\ x \in ⋃_{i \in [1, n]} A_{i} ⟹ \exists i \in [1, n] : x \in A_{i} \\ A_{i} \subseteq A ⟹ \exists i \in [1, n] : x \in A ⟹ 2. ⋃_{i \in [1, n]} A_{i} \subseteq A \\ 1. and 2. ⟹ A = ⋃_{i \in [1, n]} A_{i} \end{matrix}

6c

\begin{matrix} Prove or disprove: (\forall i \neq j : A_{i} \cap A_{j} = \emptyset) ⟹ R is transitive \\ Proof: \\ Let a, b, c \in A, (a, b) \in R, (b, c) \in R \\ (a, b) \in R ⟺ \exists i \in [1, n] : a \in A_{i} \land b \in A_{i} \\ (b, c) \in R ⟺ \exists j \in [1, n] : b \in A_{j} \land c \in A_{j} \\ Let i \neq j \\ Then b \in A_{i} \land b \in A_{j} ⟹ A_{i} \cap A_{j} \neq \emptyset - Contradiction! \\ ⟹ i = j \\ ⟹ \exists i \in [1, n] : a \in A_{i} \land b \in A_{i} \land c \in A_{i} \\ ⟺ (a, c) \in R ⟹ R is transitive \end{matrix}

6d

\begin{matrix} Prove or disprove: R is transitive ⟹ \forall i \neq j : A_{i} \cap A_{j} = \emptyset \\ Disproof: \\ Counter-example: \\ A = {1, 2, 3, 4} \\ A_{1} = A, A_{2} = A \\ R is transitive on A \\ But A_{1} \cap A_{2} \neq \emptyset \\ Disproved \end{matrix}

7a

\begin{matrix} Given: R, S - equivalence relations on A \\ Prove or disprove: R \cap S is an equivalence relation on A \\ Proof: \\ R is an equivalence relation on A ⟺ R is reflexive, symmetric and transitive \\ S is an equivalence relation on A ⟺ S is reflexive, symmetric and transitive \\ \forall a \in A : (a, a) \in R \land (a, a) \in S ⟺ \forall a \in A : (a, a) \in (R \cap S) \\ \forall a, b \in A : ((a, b) \in R \to (b, a) \in R) \land ((a, b) \in S \to (b, a) \in S) (1) \\ (a, b) \in (R \cap S) \equiv (a, b) \in R \land (a, b) \in S \\ \underset{(1)}{⟹} (b, a) \in R \land (b, a) \in S ⟺ (b, a) \in (R \cap S) \\ \forall a, b, c \in A : ((a, b) \in R \land (b, c) \in R) \to (a, c) \in R (2) \\ \forall a, b, c \in A : ((a, b) \in S \land (b, c) \in S) \to (a, c) \in S (3) \\ (a, b), (b, c) \in (R \cap S) ⟺ (a, b), (b, c) \in R \land (a, b), (b, c) \in S \\ \underset{(2), (3)}{⟹} (a, c) \in R \land (a, c) \in S ⟺ (a, c) \in (R \cap S) \\ ⟹ (R \cap S) is reflexive, symmetric and transitive \\ ⟺ (R \cap S) is an equivalence relation \end{matrix}

7b

\begin{matrix} Given: R, S - equivalence relations on A \\ Prove or disprove: R \cup S is an equivalence relation on A \\ Disproof: \\ Let (a, b) \in (R \cup S), (b, c) \in (R \cup S) \\ Then this is possible: (a, b) \in R, (b, c) \notin R, (b, c) \in S \\ For example: \\ A = {1, 2, 3, 4} \\ R = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1)} \\ S = {(1, 1), (2, 2), (3, 3), (4, 4), (2, 3), (3, 2)} \\ R \cup S = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1), (2, 3), (3, 2)} \\ (1, 2) \in R \cup S, (2, 3) \in R \cup S \\ But (1, 3) \notin R \cup S ⟹ (R \cup S) is not transitive \\ ⟺ (R \cup S) is not an equivalence relation \end{matrix}

8

\begin{matrix} S is a relation on (R ∖ {0}) \times (R ∖ {0}) \\ S = {((x_{1}, y_{1}), (x_{2}, y_{2})) | x_{1} \cdot x_{2} > 0 \land y_{1} \cdot y_{2} > 0} \\ Prove that S is an equivalence relation on (R ∖ {0}) \times (R ∖ {0}) \\ Proof: \\ Let (a, b) \in (R ∖ {0}) \\ a \cdot a > 0 \land b \cdot b > 0 ⟹ ((a, b), (a, b)) \in S ⟹ S is reflexive \\ Let ((a, b), (c, d)) \in S \\ Then a \cdot c > 0 \land b \cdot d > 0 \\ ((c, d), (a, b)) \in S ⟺ \underset{\equiv a \cdot c > 0}{\underset{⏟}{c \cdot a > 0}} \land \underset{\equiv b \cdot d > 0}{\underset{⏟}{d \cdot b > 0}} \\ ⟹ S is symmetric \\ Let ((a, b), (c, d)), ((c, d), (e, f)) \in S \\ Then a \cdot c > 0, b \cdot d > 0, c \cdot e > 0, d \cdot f > 0 \\ a \cdot c \cdot c \cdot e > 0 ⟹ a \cdot e \cdot c^{2} > 0 ⟹ a \cdot e > 0 \\ b \cdot d \cdot d \cdot f > 0 ⟹ b \cdot f \cdot d^{2} > 0 ⟹ b \cdot f > 0 \\ a \cdot e > 0 \land b \cdot f > 0 ⟺ ((a, b), (e, f)) \in S ⟹ S is transitive \\ S is reflexive, symmetric and transitive ⟺ S is an equivalence relation \end{matrix}