MAT102 Tutorial W11

• 1: Show if $x,y\in F$, then $-(x\cdot y)=(-x)\cdot y$

  • Assuming $F\subseteq \mathbb{R}$. Then we inherit associativity and commutativity.
  • As well as if $x\in F$ then $-x\in F$
  • $-(x\cdot y)+(x\cdot y)=(-x)\cdot y+(x\cdot y)$

  ---

  • By the inverse property
    • We know $x+(-x)=0$
  • Take this and multiply by $y$ on both sides
  • $y(x+(-x))=y\cdot 0$
  • $yx+y(-x)=0$
  • Take the additive inverse of this term
  • $(-x)\cdot y=-(x\cdot y)$

• 2: Define a sequence as follows: $\{\begin{array}{l}{a}_1=1\\ a_2=2\\ a_3=3\\ a_n=a_{n-1}+a_{n-2}+a_{n-3}\end{array}$, show that $a_n<2^n,\mathrm{\forall }n\in \mathbb{N}$

  • Strong Induction
  • Base Cases:
    • Defined above
    • $\{\begin{array}{l}1<2\\ 2<4\\ 3<8\end{array}$
    • All True
    • It suffices to show that $n=1,2,3$ hold.
    • Note that $a_1=1<2^1=2$
    • $a_2=2<2^2=4$
    • $a_3=3<2^3=8$
  • Induction Step:
    • Assume that $a_k<2^k$ for $1\le k\le n$ for $k\in \mathbb{N}$
    • We want to show that $a_{k+1}\le 2^{k+1}$
    • Notice by recursion definition, that $a_{k+1}$ can be re-expressed
    • $a_{k+1}=a_k+a_{k-1}+a_{k-2}<2^k+2^{k-1}{+}^{k-2}$ (by Induction Hypothesis)
    • $=2^k+\frac{2^k}{2}+\frac{2^k}{4}$
    • $=2^k(1+\frac{1}{2}+\frac{1}{4})$
    • $=2^k(\frac{3}{2}+\frac{1}{4})$
    • $=2^k\left(\frac{7}{4}\right)$
    • So we can see that $2^k\left(\frac{7}{4}\right)<2^k(2)=2^{k+1}$
    • And we wanted to prove that this is less that the $k+1$ term right.

• 3: Let $S$ be defined as:

  • $3\in S$
  • If $x,y\in S$ then $x+y\in S$
  • Prove $S$ is the set of all positive integer multiples of $3$
  • Let $A$ be the set of all positive integers divisible by $3$.
    • Prove this
    • $A\subseteq S$
    • Let $x\in A$
    • $3\mid x$
    • $x=3\ell ,\ell \in \mathbb{N}$
    • So then $x\in S$
    • Done
  • Automatically we know that $S\subseteq A$ because all multiples of $3$ - are divisible by $3$.
  • Show that $S=\{3n\mid n\in \mathbb{N}\}$
  • We proceed by induction
  • Base Case: $n=1$
    • $3(1)=3\in S$
  • Induction Step:
    • Assume $\mathrm{\exists }x\in S:x=3k$ for some $k\in \mathbb{N}$
      • This also means $x=3k⟹3\mid x$
    • We want to show that $\mathrm{\exists }3(k+1)\in S$
    • $x\in S$ so is $3$
    • We don't know anything else.
    • Let $x+3=3k+3=3(k+1)\in S$

• Consider a set of formal strings, define $M$ as:

  • The empty string $ϵ\in M$
  • If $a,b\in M$ then $\mathrm{♡}a\mathrm{♢}b\in M$
  • Prove $\mathrm{\forall }n\in M$ the number of $\mathrm{♡}$ and $\mathrm{♢}$ is the same
  • Proof
    • Let $f,g$ be functions to count the number of $\mathrm{♡},\mathrm{♢}$.
    • Base Case:
      • Consider $ϵ\in M$
      • $f(ϵ)=0=g(ϵ)$
      • No hearts or diamonds, because there's nothing in the string. It's str = ''
    • Induction Step:
      • Let $x,a,b\in M:f(a)=g(a)$ and $f(b)=g(b)$
      • We know that $x=\mathrm{♡}a\mathrm{♢}b$
      • So $f(x)=f(a)+f(b)+1$
      • $g(x)=g(a)+g(b)+1$ Because $f(a)=g(a)$.
      • So $f(x)=g(a)+g(b)+1$
      • $f(x)=g(x)$