MAT102 Test 3 Prep

• Readings 7: MAT102 Field Axioms
  • Be able to define a field.
    • A field is a set of elements in which we can have a(n):
      • additive
        • identity
        • inverse
      • multiplicative
        • identity
        • inverse
      • closure under addition and multiplication (can't escape the field if we add two or multiply two numbers from this field)
      • commutative
      • associative
      • Note: commutativity and associativity comes from being a $\subseteq \mathbb{R}$. So these are almost always included.
  • Prove simple results about abstract fields.
  • Identify when ${\mathbb{Z}}_n$ is a field, and be able to explain why these values of n either succeed or fail at producing a field.
    • ${\mathbb{Z}}_n$ is a field $⟺n$ is prime.
• Readings 8: MAT102 Prep 8
  • Explain how mathematical induction works and what it is designed to prove.
  • Prove basic statements by using mathematical induction.
  • Expand a sum or product from sigma/pi-notation to an explicit finite sum/product and vice versa.
  • Prove basic summation/product formulas using induction.
• Readings 9: MAT102 Prep 9
  • Explain the difference between strong and regular induction. Use strong induction to do elementary proofs.
  • Explain what it means for something to be defined recursively.
  • Use (structural) induction to prove properties of recursively defined elements.

Test 3 Example

• 1
  • Let $F$ denote a field on $4$ elements, and $1$ denote the multiplicative identity in $F$.
  • 1
    • Show that $1+1+1+1=0⟺1+1=0$
    • $⟹$
      • If $1+1+1+1=0$
      • This means that we can add in the multiplicative identity of the field $F$ here.
      • Let $a,b\in \mathbb{Z}$
      • If we have $a\cdot a^{-1}=1,b\cdot b^{-1}=1$, which is our multiplicative identity
      • $(a\cdot a^{-1})+(b\cdot b^{-1})+(a\cdot a^{-1})+(b\cdot b^{-1})=0$
      • If the above is true, then this means that at $(a\cdot a^{-1})+(b\cdot b^{-1})=0$
      • Only if this is true, can $0+0=0$.
      • Or $(a\cdot a^{-1})+(b\cdot b^{-1})=-((a\cdot a^{-1})+(b\cdot b^{-1}))$

      ---

      • $1+1+1+1=0$
      • $(1+1)+(1+1)=0$
      • let $x=1+1$
      • $x+x=0$
      • so $x=-x$
      • The above is only true if the first, second and third, fourth elements are additive inverses of each other.
    • $⟸$
      • If we have $1+1=0$
      • Let $x=1+1$
      • so $x=0$
      • This then makes sense, if we have $(x)+(x)=0$
      • $0+0=0$ is true.
  • 2
    • Show that at least one of $1+1$ and $1+1+1$ must equal $0$.
    • If we let $x=-x$ and have $x+1=0$, this means that $x=-1$, which wouldn't work.
    • So we have to try the other one.
    • We know that to have two multiplicative inverses $=0$, that for some $a,b\in \mathbb{Z}$ and $a^{-1},b^{-1}$ should be additive inverses of each other.
    • Such as $a\cdot a^{-1}=-(b\cdot b^{-1})$
• 2
  • Let $A,B_1,\dots ,B_n$ be general sets for $n\ge 1$
  • Define
    • $\bigcup _{k=1}^n{B}_k=B_1\cup B_2\cup \cdots \cup B_n=\{x:x\in B_k\text{ for some }k=1,\dots ,n\}$
  • Show that
    • $A\cap \left[\bigcup _{k=1}^n{B}_k\right]=\bigcup _{k=1}^n(A\cap B_k)$
  • Base Case: $n=1$
    • $B_1\cup B_1$
    • Which is $B_1$
    • Now let's show that $A\cap \left[\bigcup _{k=1}^n{B}_k\right]=\bigcup _{k=1}^n(A\cap B_k)$
    • $\bigcup _{k=1}^1(A\cap B_1)=(A\cap B_1)\cup (A\cap B_1)$
    • $\bigcup _{k=1}^1(A\cap B_1)=(A\cup A)\cap (B_1\cup B_1)$
    • $\bigcup _{k=1}^1(A\cap B_1)=A\cap B_1$
    • $A\cap B_1=A\cap B_1$
    • Base case is true
  • Induction Hypothesis:
    • For $n\in \mathbb{N}$
    • Assume that $A\cap \left[\bigcup _{k=1}^n{B}_k\right]=\bigcup _{k=1}^n(A\cap B_k)$
  • Induction Step:
    • Show that $A\cap \left[\bigcup _{k=1}^n{B}_k\right]=\bigcup _{k=1}^n(A\cap B_k)⟹A\cap \left[\bigcup _{k=1}^{n+1}{B}_k\right]=\bigcup _{k=1}^{n+1}(A\cap B_k)$
    • We can re-express the right by taking out the $n+1$th term
    • The left side is:
      • $A\cap [\bigcup _{k=1}^n(B_k)\cup B_{n+1}]$
    • The right side is:
      • $\bigcup _{k=1}^n(A\cap B_k)\cup (A\cap B_{n+1})$
    • Left:
      • $A\cap (B_1\cup B_2\cup \cdots \cup B_n\cup B_{n+1})$
    • Right:
      • $(A\cap B_1)\cup (A\cap B_2)\cup \cdots \cup (A\cap B_n)\cup (A\cap B_{n+1})$
    • Now we know via the properties of sets. We know that $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
    • So the left side is:
      • $(A\cap B_1)\cup (A\cap B_2)\cup \cdots \cup (A\cap B_n)\cup (A\cap B_{n+1})$
    • Show that $A\cap \left[\bigcup _{k=1}^n{B}_k\right]=\bigcup _{k=1}^n(A\cap B_k)⟹A\cap \left[\bigcup _{k=1}^{n+1}{B}_k\right]=\bigcup _{k=1}^{n+1}(A\cap B_k)$
    • $A\cap \left[\bigcup _{k=1}^{n+1}{B}_k\right]=A\cap [\left(\bigcup _{k=1}^n{B}_k\right)\cup B_{n+1}]$ (Rewriting the union)
    • $=[A\cap \left(\bigcup _{k=1}^n{B}_k\right)]\cup [A\cap B_{n+1}]$ (Distributive property: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C))
    • $=[\bigcup _{k=1}^n(A\cap B_k)]\cup [A\cap B_{n+1}]$ (Induction Hypothesis)
    • $=\bigcup _{k=1}^{n+1}(A\cap B_k)$ (Combining into a single union)
• 3
  • 1
    • Show that for any positive integer $k,\frac{3(k+1)}{2(k+1)+1}-\frac{3k}{2k+1}=\frac{3}{4(k+1{)}^2-1}$
    • $\frac{3(k+1)}{2(k+1)+1}-\frac{3k}{2k+1}=\frac{3}{4(k+1{)}^2-1}$
    • $\frac{3(k+1)}{2k+3}-\frac{3k}{2k+1}=\frac{3}{4(k+1{)}^2-1}$
    • $\frac{3k+3}{2k+3}-\frac{3k}{2k+1}=\frac{3}{4(k+1{)}^2-1}$
    • $\frac{3k+3(2k+1)}{2k+3(2k+1)}-\frac{3k(2k+3)}{2k+1(2k+3)}=\frac{3}{4(k+1{)}^2-1}$
    • $\frac{6k^2+9k+3}{(2k+3)(2k+1)}-\frac{6k^2+9k}{(2k+3)(2k+1)}=\frac{3}{4(k+1{)}^2-1}$
    • $\frac{3}{(2k+3)(2k+1)}=\frac{3}{4(k+1{)}^2-1}$
    • $\frac{3}{(4k^2+2k+6k+3)}=\frac{3}{4(k+1{)}^2-1}$
    • $\frac{3}{(4k^2+9k+3)}=\frac{3}{4(k+1{)}^2-1}$
    • $\frac{3}{(4k^2+9k+3)}=\frac{3}{4(k+1)(k+1)-1}$
    • $\frac{3}{(4k^2+9k+3)}=\frac{3}{4(k^2+2k+1)-1}$
    • $\frac{3}{(4k^2+9k+3)}=\frac{3}{4k^2+8k+4-1}$
    • $\frac{3}{(4k^2+9k+3)}=\frac{3}{4k^2+8k+3}$
    • This is true
  • 2
    • Assume that $k$ is a positive integer, show that $\frac{3(k+1)}{2(k+1)+1}-\frac{3k}{2k+1}<\frac{1}{(k+1{)}^2}$
    • $\frac{3}{4k^2+9k+3}<\frac{1}{(k+1{)}^2}$
    • $3(k+1{)}^2<4k^2+9k+3$
    • $3(k+1)(k+1)<4k^2+9k+3$
    • $3(k^2+2k+1)<4k^2+9k+3$
    • $3k^2+6k+3<4k^2+9k+3$
    • $6k+3<k^2+9k+3$
    • $3<k^2+3k+3$
    • $0<k^2+3k$
    • $0<k(k+3)$
    • $k>0$ and $k+3>0$
  • 3
    • Show that for all $n>1$ we have $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}$
    • Base Case: $n=2$
      • $\frac{1}{1}+\frac{1}{2^2}>\frac{3(2)}{2(2)+1}$
      • $\frac{1}{1}+\frac{1}{4}>\frac{6}{5}$
      • $\frac{5}{4}>\frac{6}{5}$
      • True
    • Induction Hypothesis:
      • Show that $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}⟹\sum _{k=1}^{n+1}\frac{1}{k^2}>\frac{3(n+1)}{2(n+1)+1}$
    • Induction Step:
      • Re express right side
      • $\sum _{k=1}^n\frac{1}{k^2}+\frac{1}{(n+1{)}^2}>\frac{3n+3}{2n+3}$
      • $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n+3}{2n+3}-\frac{1}{(n+1{)}^2}$
      • $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}>\frac{3n+3}{2n+3}-\frac{1}{(n+1{)}^2}$
      • $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}>\frac{(3n+3)(n+1{)}^2}{(2n+3)(n+1{)}^2}-\frac{(2n+3)}{(2n+3)(n+1{)}^2}$
      • $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}>\frac{(3n+3)(n+1{)}^2}{(2n+3)(n+1{)}^2}$
      • $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}>\frac{(3n+3)(n+1)(n+1)}{(2n+3)(n+1)(n+1)}$
      • $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}>\frac{(3n+3)(n^2+2n+1)}{(2n+3)(n^2+2n+1)}$
      • $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}>\frac{(3n^3+6n^2+3n+3n^2+6n+3)}{(2n^3+4n^2+2n+3n^2+6n+3)}$
      • $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}>\frac{(3n^3+9n^2+9n+3)}{(2n^3+7n^2+8n+3)}$
      • $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}>\frac{(3n^3+9n^2+9n)}{(2n^3+7n^2+8n)}$
      • $\sum _{k=1}^n\frac{1}{k^2}>\frac{3n}{2n+1}>\frac{(3n^2+9n+9)}{(2n^2+7n+8)}$

Worksheet 7 Practice

Question 1

• a: Show that $\mathbb{Q}(\sqrt{2})$ is closed under addition and multiplication. If $x,y\in \mathbb{Q}(\sqrt{2})$, then $x+y\in \mathbb{Q}(\sqrt{2})$ and $xy\in \mathbb{Q}(\sqrt{2})$
  • Addition
    • To show it's closed under addition, I must show that $x,y\in \mathbb{Q}(\sqrt{2})$ means that $x+y\in Q(\sqrt{2})$
    • $x=a+b\sqrt{2}:a,b\in \mathbb{Q}$
    • $y=c+d\sqrt{2}:c,d\in \mathbb{Q}$
    • We have been told that addition is as if it was in $\mathbb{R}$.
    • So $x+y$
    • $x+y=(a+b\sqrt{2})+(c+d\sqrt{2})$
    • $=a+b\sqrt{2}+c+d\sqrt{2}$
    • $=a+c+b\sqrt{2}+d\sqrt{2}$
    • $=a+c+\sqrt{2}(b+d)$
    • Let's re-express some variables to show this matches the definition of what it means to be in $\mathbb{Q}(\sqrt{2})$
    • let $x_1=a+c$
    • let $y_1=b+d$
    • So we have $x_1+y_1\sqrt{2}$
    • Adding two $\mathbb{Q}$ results in a $\mathbb{Q}$, so we know that $x_1,y_1\in \mathbb{Q}$.
    • So this is closed under addition
  • Multiplication
    • To show it's closed under multiplication, we must show that $xy\in \mathbb{Q}\sqrt{2}$ by showing that it still matches the definition of what it means to even be in $\mathbb{Q}\sqrt{2}$
    • Let $x=a+b\sqrt{2}:a,b\in \mathbb{Q}$ and let $y=c+d\sqrt{2}:c,d\in \mathbb{Q}$
    • We know from the definition that these multiply like $\mathbb{R}$ numbers.
    • $xy=(a+b\sqrt{2})(c+d\sqrt{2})$
    • $=(a+b\sqrt{2})(c+d\sqrt{2})$
    • $=ac+ad\sqrt{2}+bc\sqrt{2}+2bd$
    • $=ac+2bd+ad\sqrt{2}+bc\sqrt{2}$
    • $=ac+2bd+\sqrt{2}(ad+bc)$
    • Let $x_2=ac+2bd$
    • Let $y_2=ad+bc$
    • Adding and multiplying $\mathbb{Q}$ will result in $\mathbb{Q}$.
    • So we have $xy=x_2+y_2\sqrt{2}$
    • So multiplication is closed in this field.
• b: Show that $\mathbb{Q}(\sqrt{2})$ is a field.
  • Since $\mathbb{Q}(\sqrt{2})\subseteq \mathbb{R}$, we inherit the axioms regarding commutativity and associativity.
  • These don't need to be argued.
  • We have show in part a, that $\mathbb{Q}(\sqrt{2})$ is closed under $+$ and $\times$.
  • So these have been proven.
  • Now we need to show that $\mathbb{Q}(\sqrt{2})$ has a(n):
    • Additive Inverse
    • Additive Identity
    • Multiplicative Inverse
    • Multiplicative Identity
  • Additive Inverse
    • This means that $a+(-a)=0$
    • Let $a=x+y\sqrt{2}:a,b\in \mathbb{Q}$
    • Let's prove this.
    • $(x+y\sqrt{2})+(-(x+y\sqrt{2}))=0$
    • $(x+y\sqrt{2})+(-x-y\sqrt{2})=0$
    • $x+y\sqrt{2}-x-y\sqrt{2}=0$
    • $x-x+y\sqrt{2}-y\sqrt{2}=0$
    • $\cancel{x}-\cancel{x}+y\sqrt{2}-y\sqrt{2}=0$
    • $y\sqrt{2}-y\sqrt{2}=0$
    • $\cancel{y\sqrt{2}}-\cancel{y\sqrt{2}}=0$
    • $0=0$
    • This has been proven.
  • Additive Identity
    • The additive identity goes like: $a+id=a$
    • This means that adding the 'additive identity' from the field, results in adding essentially nothing. Not changing the statement.
    • Let $a=x+y\sqrt{2}:x,y\in \mathbb{Q}$
    • $x+y\sqrt{2}+(id)=x+y\sqrt{2}$
    • $x+y\sqrt{2}-(x+y\sqrt{2})+(id)=0$
    • From the additive inverse portion, we know that these cancel.
    • $\cancel{x+y\sqrt{2}}-\cancel{(x+y\sqrt{2})}+(id)=0$
    • $id=0$
    • So thus the additive identity is $0$. Meaning if we add $0$ to anything, we should get back our original statement. Meaning nothing changes.
  • Multiplicative Inverse
    • This goes like $a\cdot a^{-1}=1$.
    • Example:
      • $2\cdot 2^{-1}=1$ is true, for $2\in \mathbb{R}$.
    • Let's show this for $\mathbb{Q}(\sqrt{2})$
    • Let $a=x+y\sqrt{2}:x,y\in \mathbb{Q}$
    • So we need to find some $b\in \mathbb{Q}(\sqrt{2})$ that $a\cdot b=1$
    • Let $b=j+k\sqrt{2}:j,k\in \mathbb{Q}$
    • $(x+y\sqrt{2})(j+k\sqrt{2})=1$
    • This means that:
    • $x+y\sqrt{2}=\frac{1}{j+k\sqrt{2}}$
    • $x+y\sqrt{2}=\frac{1}{j+k\sqrt{2}}\cdot \frac{j-k\sqrt{2}}{j-k\sqrt{2}}$
    • $x+y\sqrt{2}=\frac{j-k\sqrt{2}}{j^2+2k^2}$
    • Now let's show that the right side of the equation is in $\mathbb{Q}(\sqrt{2})$
    • $x+y\sqrt{2}=\frac{j}{j^2+2k^2}-\frac{k}{j^2+2k^2}\sqrt{2}$
    • Let $c=\frac{j}{j^2+2k^2}$ and $d=-\frac{k}{j^2+2k^2}$
    • So we have $x+y\sqrt{2}=c+d\sqrt{2}$
    • So thus we know that this can be in $\mathbb{Q}(\sqrt{2})$. But what about the denominator?
    • $j^2+2k^2$ needs to be $\in \mathbb{Q}(\sqrt{2})$
    • $\sqrt{j^2+2k^2}$
    • $=j+k\sqrt{2}$
    • This is in $\mathbb{Q}(\sqrt{2})$ so thus this has been proven.
    • We know that $\mathbb{Q}(\sqrt{2})\subseteq \mathbb{R}$. The question tells us that it multiplies and adds like $\mathbb{R}$, multiplication is simply the ${}^{-1}$ of division essentially.
    • So everything is in $\mathbb{Q}(\sqrt{2})$ so there is a multiplicative inverse
  • Multiplicative Identity
    • This goes like: $a\cdot 1_{id}=1$
    • Example in the $\mathbb{R}$:
      • $5\cdot 1=5$, in $\mathbb{R}$ the $1_{id}$ is $1$.
      • This is true
    • Let's show this for $\mathbb{Q}(\sqrt{2})$
    • Let $a=x+y\sqrt{2}:x,y\in \mathbb{Q}$
    • Let's change the variable name from $1_{id}$ to $b$ and let $b=j+k\sqrt{2}:j,k\in \mathbb{Q}$
    • $a\cdot b=1$
    • $(x+y\sqrt{2})(j+k\sqrt{2})=1$
    • The only way for this to happen is if $b=a^{-1}$ or if $b=1+0\sqrt{2}$, which works since $1,0\in \mathbb{Q}$. We can express them as so: $\{\begin{array}{ll}1& =\frac{1}{1}\in \mathbb{Q}\\ 0& =\frac{0}{1}\in \mathbb{Q}\end{array}$
    • So $(x+y\sqrt{2})(1+0\sqrt{2})=1$
    • $=(x+y\sqrt{2})(1+0\sqrt{2})=1$
    • If we expand…
    • $=x+0x\sqrt{2}+y\sqrt{2}+0y(2)=1$
    • $=x+y\sqrt{2}=1$
    • So we do have a multiplicative identity
  • Thus we have proven all field axioms for $\mathbb{Q}(\sqrt{2})$, so $\mathbb{Q}(\sqrt{2})$ is a field.

Question 2

• a
  • $\{\begin{array}{l}\varphi (1)=|\{1\}|=1\\ \varphi (2)=|\{1\}|=1\\ \varphi (3)=|\{1,2\}|=2\\ \varphi (4)=|\{1,3\}|=2\\ \varphi (5)=|\{1,2,3,4\}|=4\\ \varphi (6)=|\{1,5\}|=2\\ \varphi (7)=|\{1,2,3,4,5,6\}|=6\\ \varphi (8)=|\{1,5,7\}|=3\\ \varphi (9)=|\{1,2,4,5,7,8\}|=6\\ \varphi (10)=|\{1,3,7,9\}|=4\end{array}$
• b
  • If $p$ is prime, then $\varphi (p)=p-1$
  • This is because a prime number has no factors other than $1$ and $p$.
  • So thus, every number from $1,\dots ,p-1$ is coprime to $p$.
• c
  • if $p$ is prime and $r>0$, determine $\varphi (p^r)$
  • We know that if $p$ is prime then $\varphi (p)=p-1$
  • When we do $p^r$ it automatically violates the definition of a prime. Because now we have factors other than $1,p$.
• d
  • If $a,m\in \mathbb{Z}$ are such that $m$ is a positive integer and $gcd(a,m)=1$ then $a^{\varphi (m)}\equiv 1(\mathrm{mod}m)$
  • 1
    • When $m$ is prime, Euler's Totient Theorem is equivalent to Fermat's Little Theorem.
    • We know that FLT is $a^{p-1}\equiv 1(\mathrm{mod}p)$
    • If $m$ is prime, this means the result of $\varphi (m)=m-1$
    • So this just is the same thing.
  • 2
    • Let $b_1,b_2,\dots ,b_{\varphi (m)}$ denote the numbers less than or equal to $m$ which are coprime to $m$. Show that no two of these numbers lies in the same equivalence class module $m$.

Worksheet 8 Practice

Question 1

• b
  • $\sum _{i=1}^n{f}_i^2=f_n{f}_{n+1}$
  • Base Case: $n=1$
    • $f_1^2=f_1{f}_2$
    • $f_1^2=1(1)$
    • $f_1^2=1$
    • This is true, because $(f_1{)}^2=f_1{f}_1$
    • $(f_1{)}^2=1\cdot 1$
  • Induction Hypothesis:
    • For some arbitrary $n\in \mathbb{N}$, $\sum _{i=1}^n(f_i{)}^2=f_n{f}_{n+1}⟹\sum _{i=1}^{n+1}(f_i{)}^2=f_{n+1}{f}_{n+2}$
  • Induction Step:
    • We know that we can pull out the last term in a sum.
    • $\sum _{i=1}^n(f_i{)}^2+(f_{n+1}{)}^2=f_{n+1}{f}_{n+2}$
    • I see the induction hypothesis, which we assume was true
    • $\sum _{i=1}^n(f_i{)}^2=f_n{f}_{n+1}+(f_{n+1}{)}^2=f_{n+1}{f}_{n+2}$
    • $\sum _{i=1}^n(f_i{)}^2=f_n{f}_{n+1}+f_{n+1}{f}_{n+1}=f_{n+1}{f}_{n+2}$
    • $\sum _{i=1}^n(f_i{)}^2=f_{n+1}(f_n+f_{n+1})=f_{n+1}{f}_{n+2}$
    • $\sum _{i=1}^n(f_i{)}^2=f_{n+1}(f_n+f_{n+1})=f_{n+1}{f}_{n+2}$
    • $f_n+f_{n+1}=f_{n+2}$
    • $\sum _{i=1}^n(f_i{)}^2=f_{n+1}{f}_{n+2}=f_{n+1}{f}_{n+2}$
  • So this is proven
• c
  • Show that $\sum _{i=1}^n{f}_{2i-1}=f_{2n}$
  • Base Case: $n=1$
    • $f_{2(1)-1}=f_{2(1)}$
    • $f_{2-1}=f_{2(1)}$
    • $f_1=f_{2(1)}$
    • $f_1=f_2$
    • By definition $f_1=f_2=1$
    • So this is true
  • Induction Hypothesis:
    • Assume for some $n\in \mathbb{N}$ that $\sum _{i=1}^n{f}_{2i-1}=f_{2n}⟹\sum _{i=1}^{n+1}{f}_{2i-1}=f_{2n+2}$
  • Induction Step:
    • Let's show this
    • Pull out the last term
    • $\sum _{i=1}^{n+1}{f}_{2i-1}=f_{2n+2}$
    • $\sum _{i=1}^n{f}_{2i-1}+f_{2(n+1)-1}=f_{2n+2}$
    • $\sum _{i=1}^n{f}_{2i-1}+f_{2n+1}=f_{2n+2}$
    • I see the induction hypothesis
    • $\sum _{i=1}^n{f}_{2i-1}=f_{2n}+f_{2n+1}=f_{2n+2}$
    • $\sum _{i=1}^n{f}_{2i-1}=f_{2(n)}+f_{2(n+\frac{1}{2})}=f_{2n+2}$
    • $\sum _{i=1}^n{f}_{2i-1}=f_{2(n)}+f_{2(n+\frac{1}{2})}=f_{2(n+1)}$
    • $\sum _{i=1}^n{f}_{2i-1}=f_{2(n)}+f_{2(n+\frac{1}{2})}=f_{2(n)}+f_{2(n-1)}$
    • $\sum _{i=1}^n{f}_{2i-1}=f_{2(n)}+f_{2n+1}=f_{2(n)}+f_{2(n-1)}$

Assignment 4

• a: Show that for any integer $n\ge 2$,
  • $\sum _{k=2}^n\frac{1}{k^2}<1-\frac{1}{n}$
  • Base Case:
    • $n=2$
    • $\frac{1}{2^2}<1-\frac{1}{2}$
    • $\frac{1}{4}<\frac{2}{2}-\frac{1}{2}$
    • $\frac{1}{4}<\frac{1}{2}$
    • True
  • Induction Hypothesis:
    • Assume for some $n\in \mathbb{N}$ that $\sum _{k=2}^n\frac{1}{k^2}<1-\frac{1}{n}⟹\sum _{k=2}^{n+1}\frac{1}{k^2}<1-\frac{1}{n+1}$
  • Induction Step:
    • Show that $\sum _{k=2}^{n+1}\frac{1}{k^2}<1-\frac{1}{n+1}$ is true
    • $\sum _{k=2}^{n+1}\frac{1}{k^2}=\sum _{k=2}^n\frac{1}{k^2}+\frac{1}{(n+1{)}^2}$
    • Via IH
    • $\sum _{k=2}^{n+1}\frac{1}{k^2}<1-\frac{1}{n}+\frac{1}{(n+1{)}^2}$
    • Let's show that $1-\frac{1}{n}+\frac{1}{(n+1{)}^2}<1-\frac{1}{n+1}$
    • $-\frac{1}{n}+\frac{1}{(n+1{)}^2}<-\frac{1}{n+1}$
    • $\frac{1}{n}-\frac{1}{(n+1{)}^2}>\frac{1}{n+1}$
    • $-\frac{1}{(n+1{)}^2}>\frac{1}{n+1}-\frac{1}{n}$
    • $-\frac{1}{(n+1{)}^2}>\frac{1}{n+1}-\frac{1}{n}\frac{n+1}{n+1}$
    • $-\frac{1}{(n+1{)}^2}>\frac{1}{n+1}-\frac{n+1}{n^2+n}$
    • $-\frac{1}{(n+1{)}^2}>\frac{-n^2}{n+1}$
    • $\frac{1}{(n+1{)}^2}<\frac{n^2}{n+1}$
    • $n+1<n^2(n+1{)}^2$
    • $n+1<n^2(n^2+2n+1)$
    • $n+1<n^4+2n^3+n^2$
    • $+1<n^4+2n^3+n^2-n-1$
    • $0<n^4+2n^3+n^2-n-1$

Test 3 Multiple Choice Practice

• 1
  • Let $F$ be a field with addition and multiplication. If $x,y,z\in F$, which is not a field axiom?
  • d
• 2
  • $a^{p-1}\equiv 1(\mathrm{mod}p)$
  • $a^p\equiv a(\mathrm{mod}p)$
  • e
• 7
  • $\sum _{k=0}^5(2k-1)$
  • $\{\begin{array}{lll}k=0& 2(0)-1& =-1\\ k=1& 2(1)-1=2-1& =1\\ k=2& 2(2)-1=4-1& =3\\ k=3& 2(3)-1=6-1& =5\\ k=4& 2(4)-1=8-1& =7\\ k=5& 2(5)-1=10-1& =9\end{array}$
  • $-1+1+3+5+7+9$
  • $24$
• 8
  • How to Do Re-Indexing
  • $\frac{n}{k}\prod _{i=1}^{k-1}\frac{n-i}{i}$
  • $\prod _{i=1}^k\frac{n-i+1}{i}$
• 9
• 10
  • Prove that any postage of $12c$ or greater can be formed by using $4c$ and $5c$ stamps ($c=$ stamps).
  • Base Cases:
    • $\{\begin{array}{ll}12& =3(4)+0(5)\\ 13& =2(4)+1(5)\\ 14& =1(4)+2(5)\\ 15& =0(4)+3(5)\end{array}$
    • Notice that the amount of $4c$ stamps go from $3\to 0$, whereas the $5c$ stamps go from $0\to 3$.
    • $\{\begin{array}{ll}16& =4(4)+0(5)\\ 17& =3(4)+1(5)\\ 18& =2(4)+2(5)\\ 19& =1(4)+3(5)\\ 20& =0(4)+4(5)\end{array}$
    • We can see the same pattern here as how they increase and decrease.
  • Induction Hypothesis:
    • Assume that for some $12\le n\le k$ that $n$ can be expressed as a sum of $4c$ and $5c$ stamps.
  • Induction Step:
    • Assume $k>15$
    • We can have $k+1$
    • To re-express this as a base case.
      • $(k-4)+5$
    • $k-4=4a+5b$ By IH
      • $a,b\in {\mathbb{Z}}^{+}$
    • $(k-4)+5=4a+5b+5$
    • $(k-4)+5=4a+5(b+1)$
    • $k+1=4a+5(b+1)$
    • $◻$

• ${\mathbb{Z}}_n$
• field
• ${\mathbb{Z}}_5=\{1,2,3,4\}$
• $gcd(a,b)$
• $gcd(0,5)=5$
• $0=5a$ for some $a\in \mathbb{Z}$
• let $a=0$
• $0=5(0)$
• $5=5b$ for some $b\in \mathbb{Z}$
• $b=1$
• ${\mathbb{Z}}_n$
  • $5\cdot a=1$
  • Closed adiditon multipociation
  • $\mathbb{Z}\subseteq \mathbb{R}$
  • Additive inverse, identity and multipoicate
  • multiplicative inverse
    • $a\cdot a^{-1}=1$

Test 3 Practice Again

Question 2

• Base Case:
  • $n=1$
  • $A\cap d\bigcup _{k=1}^n{B}_k$
  • $A\cap \bigcup _{k=1}^1{B}_1$
  • $A\cap B_1$
  • By common sense and definition
  • $\bigcup _{k=1}^n(A\cap B_k)$
  • $\bigcup _{k=1}^1(A\cap B_k)$
  • $A\cap B_1$
  • Equal
• Induction Hypothesis:
  • Assume what's written
• Induction Step:
  • WTS that $n⟹n+1$
  • Left side:
    • $A\cap [\bigcup _{k=1}^{n+1}{B}_k]$
    • $A\cap [(\bigcup _{k=1}^n{B}_k)\cup B_{n+1}]$
    • $(A\cap (\bigcup _{k=1}^n{B}_k))\cup (A\cap B_{n+1})$
    • $\bigcup _{k=1}^n(A\cap B_k)\cup (A\cap B_{n+1})$
  • Right side:
    • $\bigcup _{k=1}^{n+1}(A\cap B_k)$
    • $\bigcup _{k=1}^n(A\cap B_k)\cup (A\cap B_{n+1})$
  • Thus i am right
  • $◻$
  • if$⟺$ then it must be both $⟹$ and $⟸$

Other

$\frac{3(k+1)}{2(k+1)+1}$
WTS $\frac{3}{4(k+1{)}^2-1}<\frac{1}{(k+1{)}^2}$
$\frac{3}{4(k+1{)}^2-1}<\frac{1}{(k+1{)}^2}$
$\frac{3}{4}\frac{1}{(k+1{)}^2-1}<\frac{1}{(k+1{)}^2}$
$\frac{3}{4(k+1{)}^2-1}<\frac{1}{(k+1{)}^2}$ only because $k>0$ yaya
$3(k+1{)}^2<4(k+1{)}^2-1$
$3(k+1{)}^2<4(k+1{)}^2-1$
$0<4(k+1{)}^2-1-3(k+1{)}^2$
$0<(k+1{)}^2-1$
$1<(k+1{)}^2$
$(k+1{)}^2>1$ True
I am right
$◻$