241 lines
8.2 KiB
TeX
241 lines
8.2 KiB
TeX
|
\documentclass[12pt]{article}
|
||
|
|
\usepackage{ntnu}
|
||
|
|
\usepackage{ntnu-math}
|
||
|
|
\usepackage{ntnu-code}
|
||
|
|
|
||
|
|
\author{Øystein Tveit}
|
||
|
|
\title{MA0301 Exercise 5}
|
||
|
|
|
||
|
|
\usepackage{amsthm}
|
||
|
|
\usepackage{mathabx}
|
||
|
|
|
||
|
|
\begin{document}
|
||
|
|
\ntnuTitle{}
|
||
|
|
\break{}
|
||
|
|
|
||
|
|
\begin{excs}
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
Base case:
|
||
|
|
\begin{align*}
|
||
|
|
\sum^{m}_{j=1} \frac{1}{j(j+2)} &= \frac{m(3m+5)}{4(m+1)(m+2)} \\[2ex]
|
||
|
|
\frac{1}{1(1+2)} &= \frac{1(3\cdot1 + 5)}{4(1+1)(1+2)} \\[2ex]
|
||
|
|
\frac{1}{3} &= \frac{8}{4(2)(3)} \\[2ex]
|
||
|
|
\frac{1}{3} &= \frac{8}{8(3)} \\[2ex]
|
||
|
|
\frac{1}{3} &= \frac{1}{3}
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
Assume:
|
||
|
|
\[ \sum^{m}_{j=1} \frac{1}{j(j+2)} = \frac{m(3m+5)}{4(m+1)(m+2)} \]
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
\sum^{m+1}_{j=1} \frac{1}{j(j+2)}
|
||
|
|
&= \frac{1}{1(1+2)} + \frac{1}{2(2+2)} + \ldots + \frac{1}{m(m+2)} + \frac{1}{(m+1)((m+1)+2)} \\[2ex]
|
||
|
|
&= \frac{m(3m+5)}{4(m+1)(m+2)} + \frac{1}{(m+1)((m+1)+2)} \\[2ex]
|
||
|
|
&= \frac{3m^2+5m}{4m^2+12m+8} + \frac{1}{m^2+4m+3} \\[2ex]
|
||
|
|
&= \frac{(m^2+4m+3)(3m^2+5m) + 4m^2+12m+8}{(m^2+4m+3)(4m^2+12m+8)} \\[2ex]
|
||
|
|
&= \frac{3m^4+17m^3+29m^2+15m + 4m^2+12m+8}{(m^2+4m+3)(4m^2+12m+8)} \\[2ex]
|
||
|
|
&= \frac{3m^4+17m^3+33m^2+27m+8}{(m^2+4m+3)(4m^2+12m+8)} \\[4ex]
|
||
|
|
&\text{(Here, I used a calculator to factorize the expression)} \\[4ex]
|
||
|
|
&= \frac{3m^2+11m+8}{4m^2+20m+24} \\[2ex]
|
||
|
|
&= \frac{(m+1)(3m+8)}{4(m^2+5m+6)} \\[2ex]
|
||
|
|
&= \frac{(m+1)(3(m+1)+5)}{4(m+2)(m+3)} \\[2ex]
|
||
|
|
&= \frac{(m+1)(3(m+1)+5)}{4((m+1)+1)((m+1)+2)} \\[2ex]
|
||
|
|
\end{align*}
|
||
|
|
\qed
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
a_{m+1} &= 2^{2(m + 1) + 1} + 1 \\
|
||
|
|
&= 2^{2m+3} + 1 \\
|
||
|
|
&= 2^{2m+1}2^2 + 1 \\
|
||
|
|
&= (2^{2m+1} + 1)2^2 - (1)2^2 + 1 \\
|
||
|
|
&= 4a_{m} - 4 + 1 \\
|
||
|
|
&= 4a_{m} - 3 \\
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
$(a_m \bmod 3 = 0) \wedge (-3 \bmod 3 = 0) \Rightarrow ((4a_m - 3) \bmod 3 = 0)$
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
Base case:
|
||
|
|
\begin{align*}
|
||
|
|
\sum^m_{i=1} iL_i &= mL_{m+2} - L_{m+3} + 4 \\
|
||
|
|
1 \cdot L_1 &= 1 \cdot L_{1+2} - L_{1+3} + 4 \\
|
||
|
|
1 &= 4 - 7 + 4 \\
|
||
|
|
1 &= 1 \\
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
Assume:
|
||
|
|
\[ \sum^m_{i=1} i L_i = mL_{m+2} - L_{m+3} + 4 \]
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
\sum^{m+1}_{i=1} iL_i &= 1L_1 + 2L_2 + \ldots + mL_m + (m+1)L_{m+1} \\
|
||
|
|
&= mL_{m+2} - L_{m+3} + 4 + (m+1)L_{m+1} \\
|
||
|
|
&= mL_{m+2} - L_{m+3} + 4 + mL_{m+1} + L_{m+1} \\
|
||
|
|
&= m(L_{m+2} + L_{m+1}) - L_{m+3} + L_{m+1} + 4 \\
|
||
|
|
&= mL_{m+3} - L_{m+3} + L_{m+1} + 4 \\
|
||
|
|
&= (m+1)L_{m+3} - L_{m+3} - L_{m+3} + L_{m+1} + 4 \\
|
||
|
|
&= (m+1)L_{m+3} - L_{m+3} - L_{m+2} - L{m+1} + L_{m+1} + 4 \\
|
||
|
|
&= (m+1)L_{m+3} - L_{m+3} - L_{m+2} + 4 \\
|
||
|
|
&= (m+1)L_{m+3} - L_{m+4} + 4 \\
|
||
|
|
&= (m+1)L_{(m+1)+2} - L_{(m+1)+3} + 4 \\
|
||
|
|
\end{align*}
|
||
|
|
\qed
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
Base case:
|
||
|
|
\begin{align*}
|
||
|
|
\sum^1_{i=1}(-1)^{i+1}i^2 &= (-1)^{1+1}\sum^{1}_{i=1}i \\
|
||
|
|
(-1)^{1+1} \cdot 1^2 &= (-1)^{1+1} \cdot 1 \\
|
||
|
|
(-1)^{2} &= (-1)^{2} \\
|
||
|
|
1 &= 1 \\
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
Assume:
|
||
|
|
|
||
|
|
\[ \sum^m_{i=1}(-1)^{i+1}i^2 = (-1)^{m+1}\sum^{m}_{i=1}i = (-1)^{m+1}\left(\frac{m(m+1)}{2}\right)\]
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
\sum^{m+1}_{i=1} &= (-1)^{1+1} \cdot 1^2 + (-1)^{2+1} \cdot 2^2 + \ldots + (-1)^{m+1} m^2 + (-1)^{(m+1)+1} (m+1)^2 \\
|
||
|
|
&= (-1)^{m+1}\frac{m(m+1)}{2} + (-1)^{(m+1)+1} (m+1)^2 \\
|
||
|
|
&= (-1)^{m+1} \left(\frac{m(m+1)}{2} + (-1) (m+1)^2 \right) \\
|
||
|
|
&= (-1)^{m+1} (m+1) \left( \frac{m}{2} - (m+1) \right) \\
|
||
|
|
&= (-1)^{m+1} (-1) (m+1) \left( -\frac{m}{2} + (m+1) \right) \\
|
||
|
|
&= (-1)^{m+2} (m+1) \left( -\frac{m}{2} + (m+1) \right) \\
|
||
|
|
&= (-1)^{m+2} (m+1) \left( \frac{-m + 2(m+1)}{2} \right) \\
|
||
|
|
&= (-1)^{m+2} (m+1) \left( \frac{-m + 2m + 2}{2} \right) \\
|
||
|
|
&= (-1)^{m+2} (m+1) \left( \frac{m + 2}{2} \right) \\
|
||
|
|
&= (-1)^{m+2} \left( \frac{(m+1)(m + 2)}{2} \right) \\
|
||
|
|
&= (-1)^{(m+1)+1} \left( \frac{(m+1)((m+1) + 1)}{2} \right) \\
|
||
|
|
\end{align*}
|
||
|
|
\qed
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
\begin{subexcs}
|
||
|
|
\subexc{}
|
||
|
|
|
||
|
|
$R$ is reflexive because $x \bmod x = 0$
|
||
|
|
|
||
|
|
$R$ is not symmetric because $ 2 \bmod 1 = 0$ but $1 \bmod 2 = 1$
|
||
|
|
|
||
|
|
$R$ is transitive because
|
||
|
|
\begin{align*}
|
||
|
|
xRy &\Leftrightarrow (y = nx), &&n \in \mathbb{Z} \\
|
||
|
|
yRz &\Leftrightarrow (z = my = m(nx)), &&m \in \mathbb{Z} \\
|
||
|
|
z=nmx &\Leftrightarrow (z \bmod x = 0)
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
\subexc{}
|
||
|
|
|
||
|
|
$R$ is reflexive because \[ A \cap C = A \cap C \]
|
||
|
|
|
||
|
|
$R$ is symmetric because \[ A \cap C = B \cap C \Leftrightarrow B \cap C = A \cap C \]
|
||
|
|
|
||
|
|
$R$ is transitive because \[ (A \cap C = B \cap C) \wedge (B \cap C = D \cap C) \Rightarrow A \cap C = D \cap C \]
|
||
|
|
|
||
|
|
\subexc{}
|
||
|
|
|
||
|
|
$R$ is not reflexive because \[ l_1 \not\perp l_1 \]
|
||
|
|
|
||
|
|
$R$ is symmetric because \[ l_1 \perp l_2 \Leftrightarrow l_2 \perp l_1 \]
|
||
|
|
|
||
|
|
$R$ is not transitive because \[ l_1 \perp l_2 \wedge l_2 \perp l_3 \Rightarrow l_1 \not\perp l_3 \]
|
||
|
|
|
||
|
|
\subexc{}
|
||
|
|
|
||
|
|
$R$ is not reflexive because \[ (2n + 1) + (2n + 1) = 2(2n + 1) = 2k \]
|
||
|
|
|
||
|
|
$R$ is symmetric because \[ x+y = y+x = 2n+1 \]
|
||
|
|
|
||
|
|
$R$ is not transitive because an odd number can only be the sum of two integers if one is odd and the other is even
|
||
|
|
|
||
|
|
Case 1: $x$ is even and $y$ is odd:
|
||
|
|
\begin{align*}
|
||
|
|
x + y &= 2n+1 \\
|
||
|
|
y + z &= 2n+1 \Rightarrow z = 2k \\
|
||
|
|
x+z &= 2k_1 + 2k_2 = 2(k_1 + k_2) = 2k
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
Case 2: $x$ is odd and $y$ is even:
|
||
|
|
\begin{align*}
|
||
|
|
x + y &= 2n+1 \\
|
||
|
|
y + z &= 2n+1 \Rightarrow z = 2k + 1 \\
|
||
|
|
x+z &= (2k_1+1) + (2k_2+1) = 2(k_1 + k_2) + 2 = 2(k_1 + k_2 + 1) = 2k
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
\end{subexcs}
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
In order to show that this is an equivalence relation, the relation has to be reflexive, symmetric and transitive
|
||
|
|
|
||
|
|
Reflexive:
|
||
|
|
\[ ab = ba \]
|
||
|
|
|
||
|
|
Symmetric:
|
||
|
|
\[ (ad = bc) \Leftrightarrow (bc = ad) \]
|
||
|
|
|
||
|
|
Transitive:
|
||
|
|
\[ (ad = bc) \wedge (cf = de) \Leftrightarrow \left(\frac{a}{b} = \frac{c}{d}\right) \wedge \left(\frac{c}{d} = \frac{e}{f}\right) \Rightarrow \left(\frac{a}{b} = \frac{e}{f}\right) \Leftrightarrow (af = be) \]
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
|
||
|
|
In order to show that this is an equivalence relation, the relation has to be reflexive, symmetric and transitive
|
||
|
|
|
||
|
|
Reflexive:
|
||
|
|
\[ x+y = x+y \]
|
||
|
|
|
||
|
|
Symmetric:
|
||
|
|
\[ (x+y = u+v) \Leftrightarrow (u+v = x+y) \]
|
||
|
|
|
||
|
|
Transitive:
|
||
|
|
\[ (x+y = u+v) \wedge (u+v = m+n) \Rightarrow (x+y = m+n) \]
|
||
|
|
|
||
|
|
In this case, you could either use the fact that there are only specific integers that will sum to another integer, or check every relation between every tuple in order to calculate the equivalence classes. I decided to solve it by automating the process.
|
||
|
|
|
||
|
|
\codeFile{scripts/ex7.hs}{haskell}
|
||
|
|
|
||
|
|
Output:
|
||
|
|
\begin{verbatim}
|
||
|
|
[(1,3),(2,2),(3,1)]
|
||
|
|
[(1,5),(2,4),(3,3),(4,2),(5,1)]
|
||
|
|
[(1,1)]
|
||
|
|
\end{verbatim}
|
||
|
|
|
||
|
|
therefore
|
||
|
|
|
||
|
|
\begin{align*}
|
||
|
|
[(1,3)] &= \{(1,3), (2,2), (3,1)\} \\
|
||
|
|
[(2,4)] &= \{(1,5), (2,4), (3,5), (4,2), (5,1)\} \\
|
||
|
|
[(1,1)] &= \{(1,1)\}
|
||
|
|
\end{align*}
|
||
|
|
|
||
|
|
\exc{}
|
||
|
|
In order to show that this is an equivalence relation, the relation has to be reflexive, symmetric and transitive
|
||
|
|
|
||
|
|
Reflexive:
|
||
|
|
\[ x - x \bmod 3 = 0 \bmod 3 = 0 \]
|
||
|
|
|
||
|
|
Symmetric:
|
||
|
|
\[ (x - y \bmod 3 = 0) \Leftrightarrow (x,y= 3k_1 + r, 3k_2 + r) \Leftrightarrow (y - x \bmod 3 = 3(k_2 - k_1) + r - r = 0) \]
|
||
|
|
|
||
|
|
Transitive:
|
||
|
|
\[ (ad = bc) \wedge (cf = de) \Leftrightarrow \left(\frac{a}{b} = \frac{c}{d}\right) \wedge \left(\frac{c}{d} = \frac{e}{f}\right) \Rightarrow \left(\frac{a}{b} = \frac{e}{f}\right) \Leftrightarrow (af = be) \]
|
||
|
|
|
||
|
|
The equivalence classes will contain the numbers that has the same remainder after dividing by $3$, since subtracting them from each other will remove the remainder and make the number divisible by $3$.
|
||
|
|
|
||
|
|
therefore the partition of $A$ induced by $R$ will be
|
||
|
|
|
||
|
|
\[ \{\{1,4,7\}, \{2,5\}, \{3,6\}\} \]
|
||
|
|
|
||
|
|
|
||
|
|
\end{excs}
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
\end{document}
|