MA0301/exercise4/main.tex

\documentclass[12pt]{article}
\usepackage{ntnu}
\usepackage{ntnu-math}

\author{Øystein Tveit}
\title{MA0301 Exercise 4}

\usepackage{amsthm}

\begin{document}
  \ntnuTitle{}
  \break{}
  
  \begin{excs}
    \exc{}
      \begin{subexcs}
        \subexc{}
          \begin{gather*}
            \overline{xy} + \overline{x}\ \overline{y} \\
            \overline{1 \cdot 0} + (\overline{1}\cdot \overline{0}) \\
            \overline{0} + (0 \cdot 1) \\
            1 + 0 \\
            1
          \end{gather*}

        \subexc{}
          \begin{gather*}
            w + \overline{x}y \\
            1 + (\overline{1} \cdot 0) \\
            1 + 0 \\
            1
          \end{gather*}

        \subexc{}
          \begin{gather*}
            wx + \overline{y} + yz \\
            (1 \cdot 1) + \overline{0} + (0 \cdot 0) \\
            1 + 1 + 0 \\
            1 
          \end{gather*}

        \subexc{}
          \begin{gather*}
            (wx + y\overline{z}) + w\overline{y} + \overline{(w + y)(\overline{x} + y)} \\
            ((1 \cdot 1) + (0 \cdot \overline{0})) + (1 \cdot \overline{0}) + \overline{(1 + 0)(\overline{1} + 0)} \\
            (1 + 0) + (1 \cdot 1) + \overline{(1)(0 + 0)} \\
            1 + 1 + \overline{(1)(0)} \\
            1 + 1 + \overline{0} \\
            1 + 1 + 1 \\
            1 
          \end{gather*}
      \end{subexcs}

    \exc{}
      \begin{subexcs}
        \subexc{}
          \begin{gather*}
            xy + (x + y)\overline{z} + y \\
            (xy + y) + \overline{z}x + \overline{z}y \\
            y + \overline{z}x + \overline{z}y \\
            \overline{z}x + (y + \overline{z}y) \\
            \overline{z}x + y
          \end{gather*}

        \subexc{}
          \begin{gather*}
            x + y + \overline{(\overline{x} + y + z)} \\
            x + y + \overline{\overline{x}}\ \overline{y}\ \overline{z} \\
            x + y + x\overline{y}\ \overline{z} \\
            (x + x\overline{y}\ \overline{z}) + y \\
            x + y
          \end{gather*}

        \subexc{}
          \begin{gather*}
            yz + wx + z +[wz(xy + wz)] \\
            (yz + z) + wx + (xywz + wz) \\
            (z + xywz + wz) + wx \\
            z + wx
          \end{gather*}

      \end{subexcs}


    \exc{}{}
     
    Base case
    \begin{align*}
      \sum^{1}_{i=0}i^2 &= \frac{1 \cdot (1 + 1)(2 \cdot 1 + 1)}{6} \\[2ex]
      1^2 &=\frac{2 \cdot 3}{6} \\[2ex]
      1 &=\frac{6}{6} \\[2ex]
      1 &= 1
    \end{align*}

    Assume:
    \[ \sum^{k}_{i=0}i^2 = \frac{k (k + 1)(2k + 1)}{6} \]

    \begin{align*}
      \sum^{k+1}_{i=0}i^2 &= 0^2 + 1^2 + 2^2 + \ldots + k^2 + (k + 1)^2 \\[2ex]
                          &= \frac{k (k + 1)(2k + 1)}{6} + (k + 1)^2 \\[2ex]
                          &= \frac{k (k + 1)(2k + 1) + 6(k + 1)^2}{6} \\[2ex]
                          &= \frac{ (k + 1)(k (2k + 1) + 6(k + 1))}{6} \\[2ex]
                          &= \frac{ (k + 1)(2k^2 + k + 6k + 6)}{6} \\[2ex]
                          &= \frac{ (k + 1)(2k^2 + 7k + 6)}{6} \\[2ex]
                          &= \frac{ (k + 1)(k + 2)(2k + 3)}{6} \\[2ex]
                          &= \frac{(k + 1) ((k + 1) + 1)(2(k + 1) + 1)}{6}
    \end{align*}

    \qed

    \exc{}
    \begin{subexcs}
      \subexc{}
      \begin{align*}
        S(0) &= 2^{-0} = 1 \\
        S(1) &= 2^{-0} + 2^{-1} = 1.5 \\
        S(2) &= 2^{-0} + 2^{-1} + 2^{-2} = 1.75 \\
        S(3) &= 2^{-0} + 2^{-1} + 2^{-2} + 2^{-3} = 1.875
      \end{align*}

      \subexc{}
      Based on the results from a, I conjecture that

        \[ S(n) = 2 - 2^{-n} \] 

      \subexc{}

      Base case
      \begin{align*}
        \sum^{0}_{i=0}2^{-i} &= 2-2^{-0} \\
        2^{-0} &= 2-1 \\
        1 &= 1
      \end{align*} 

      Assume:
      \[ \sum^{n}_{i=0}2^{-i} = 2-2^{-n} \]

      \begin{align*}
        \sum^{n+1}_{i=0}2^{-i} &= 2^{-0} + 2^{-1} + 2^{-2} + \ldots + 2^{-n} + 2^{-(n+1)} \\
                               &= 2-2^{-n} + 2^{-(n+1)} \\
                               &= 2-2^{-n} + 2^{-n-1} \\
                               &= 2-2^{-n} + 2^{-n}2^{-1} \\
                               &= 2-2^{-n}(1-2^{-1}) \\
                               &= 2-2^{-n}(\frac{2}{2}-\frac{1}{2}) \\
                               &= 2-2^{-n}(\frac{1}{2}) \\
                               &= 2-2^{-n}(2^{-1}) \\
                               &= 2-2^{-n-1} \\
                               &= 2-2^{-(n+1)}
      \end{align*}

      \qed

      \subexc{}

      \begin{align*}
        S(n) &> \epsilon \\
        2-2^{-n} &> \epsilon \\
        2^{-n} &> \epsilon - 2 \\
        -n &> \log_2(\epsilon - 2) \\
        n &< -\log_2(\epsilon - 2) \\
      \end{align*}

      Assuming $S(n)$ never can reach n,
      for $S(n)$ to be within $\epsilon$ of $2$, n has to be less than $-\log_2(\epsilon - 2)$
      
    \end{subexcs}


    \exc{}

    Base case
    \begin{align*}
      \sum^{1}_{i=1}2^{i-1} \cdot i &= 2^n \cdot (n-1) + 1 \\
      2^{1-1} \cdot 1 &= 2^1 \cdot (1-1) + 1 \\
      2^0 \cdot 1 &= 2 \cdot 0 + 1 \\
      1 \cdot 1 &= 1 \\
      1 &= 1
    \end{align*}

    Assume:
    \[ \sum^{n}_{i=1}2^{i-1} \cdot i = 2^n \cdot (n-1) + 1 \]

    \begin{align*}
      \sum^{n+1}_{i=1}2^{i-1} \cdot i &= (2^{1-1} \cdot 1) + (2^{2-1} \cdot 2) + \ldots
                                        + (2^{n-1} \cdot n) + (2^{(n+1)-1} \cdot (n+1)) \\
                                      &= 2^n \cdot (n-1) + 1 + (2^{(n+1)-1} \cdot (n+1)) \\
                                      &= 2^n \cdot (n-1) + 1 + 2^{n} \cdot (n+1) \\
                                      &= (2^n \cdot n - 2^n) + 1 + (2^{n} \cdot n + 2^{n}) \\
                                      &= 2^n \cdot n - 2^n + 1 + 2^{n} \cdot n + 2^{n} \\
                                      &= 2(2^n \cdot n) - 2^n + 2^{n}+ 1  \\
                                      &= (4^n \cdot n) + 1  \\
                                      &= (2^{n+1} \cdot ((n+1)-1)) + 1
    \end{align*}

    \qed

  \end{excs}
  
\end{document}