MAT102 Tutorial W10

• 1
  • Which induction do you use?:
  • $\frac{1}{3}{n}^2+\frac{1}{2}{n}^2+\frac{1}{6}$ is an integer $\mathrm{\forall }n\in \mathbb{N}$
    • Simple
    • Base case:
      • $P(1)=\frac{1}{3}+\frac{1}{2}+\frac{1}{6}$
      • $P(1)=1$
    • Induction Hypothesis:
      • $P(n)$ is true for some $n\in \mathbb{N}$
    • Induction Step:
      • $P(n)⟹P(n+1)$
      • $\frac{1}{3}{n}^2+\frac{1}{2}{n}^2+\frac{1}{6}==\frac{1}{3}(n+1{)}^2+\frac{1}{2}(n+1{)}^2+\frac{1}{6}$
      • $\frac{1}{3}{n}^2+\frac{1}{2}{n}^2+\frac{1}{6}==\frac{1}{3}(n+1)(n+1)+\frac{1}{2}(n+1)(n+1)+\frac{1}{6}$
      • $\frac{1}{3}{n}^2+\frac{1}{2}{n}^2+\frac{1}{6}==\frac{1}{3}(n^2+2n+1)+\frac{1}{2}(n^2+2n+1)+\frac{1}{6}$
      • $\frac{1}{3}{n}^2+\frac{1}{2}{n}^2+\frac{1}{6}==\frac{1}{3}(n^2+2n+1)+\frac{1}{2}(n^2+2n+1)+\frac{1}{6}$
      • Right side
        • $\frac{1}{3}{n}^2+\frac{2}{3}n+\frac{1}{3}+\frac{1}{2}{n}^2+n+\frac{1}{2}+\frac{1}{6}$
        • $n^2(\frac{1}{3}+\frac{1}{3})+n(\frac{2}{3}+1)+(\frac{1}{3}+\frac{1}{2}+\frac{1}{6})$
        • We know that $\frac{1}{3}+\frac{1}{2}+\frac{1}{6}=1$ from the base case
        • $n^2(\frac{1}{3}+\frac{1}{3})+n(\frac{2}{3}+1)+1$
        • $\frac{2}{3}{n}^2+\frac{5}{3}n+1$
• 2
  • Define a non empty binary tree as:
    • A single node is a binary tree
    • If $T_1$ is a binary tree then the tree formed by joining $r$ with $T_i$ on either left or right is also a binary tree
    • If $T_1$ and $T_2$ are binary trees, then joining them with $r$ is also a binary tree
  • Let:
    • $e(t)=$ the number of edges in a tree
    • $n(t)=$ the number of nodes
  • Prove that for any binary tree $T$
    • $n(t)=e(t)+1$
    • Base Cases:
      • Tree size is $1$
        • Nodes are $1$
        • Edges are $1$
        • ??
  • Solution
    • Proof:
      • Base Case: Single Node
        • Has one node, no edges
      • Induction Step:
        • Cases, tree on either or side, or two trees.
        • Assume $T_1$ and $T_2$ are binary trees such that $n(T_1)=e(T_1)+1$ and $n(T_2)=e(T_2)+1$.
        • First case:
          • Construct a tree $T^{\prime }$ with root $r$ and $T_1$ as its subtree on either left or right side.
          • $⟹$
            • $n(T^{\prime })=N(T_1)+1$
            • Nodes in t prime are t1's nodes + the new node
            • $e(T_1)+1+1$
            • We take the previous tree and add another node to the equation
            • $e(T^{\prime })+1$
        • Second case:
          • Construct $T^{\prime }$ with root $r$ and subtrees $T_1$ and $T_2$.
          • $⟹$
            • $n(T^{\prime })=n(T_1)+n(T_2)+1$
            • $(e(T_1)+1)+(e(T_2)+1)+1$
            • Consider that the number of edges here is just the number of edges in $t_1$ and $t_2$ then $+1$.
            • So $e(t^{\prime })+1$
• 3
  • Suppose that there are $2n+1$ airports, where $n\in \mathbb{N}$
  • The distances between any two airpots is
  • different airport. For each airport there is exactly
  • one airplane departing from it and heading towards
  • the closest airport.
  • Prove by induction that there is an airport which none of the airplanes head towards.
  • Base case
    • Suppose we have $2(1)+1$ airports, $3$ airports.
    • Let our distances be $d_i\in \mathbb{N}$
    • $0<d_1<d_2<d_3$
    • Let us have $3$ airports $a_i$
    • The distance between $\{\begin{array}{l}{a}_1\to a_2=d_1\\ a_2\to a_3=d_2\\ a_3\to a_1=d_3\end{array}$
    • Let our planes departing from each airport have their respective numbers: $\{\begin{array}{l}{p}_1|{}_{a_1}\\ p_2|{}_{a_2}\\ p_3|{}_{a_3}\end{array}$
    • $\{\begin{array}{l}{p}_1\to a_2\\ p_2\to a_3\\ p_3\to a_2\text{ Because the smallest distance is here}\end{array}$
  • Induction Hypothesis:
    • Suppose we have $2n+1$ airports.
    • Then at least one of the airports won't have a plane $p_i$ heading towards $a_1$
  • Induction Step:
    • Show that if I have $2n+1$ airports that $2(n+1)+1$ airports also won't have a plane heading towards $a_1$.
    • $2n+3$ airports
    • So we have
    • $a_1,a_2,\dots ,a_{2n+3}$
    • $p_1,p_2,\dots ,p_{2n+3}$
    • $0<d_1<d_2<\cdots <d_{2n+3}$
    • $\{\begin{array}{l}{p}_1\to a_2\\ p_2\to a_3\\ \dots \\ p_{2n+3}\to a_2\end{array}$
  • solution:
    • base case proven
      • $3$ airports
        • $a_i,a_j,a_k$
        • $i,j,k$
      • $d_{ji}<d_{jk}<d_{ik}$
      • We know that plane $a$ will go from
    • Inductino step:
      • Assume $2k+1$ airport
      • $1$ airport is empty
      • Without loss of generality
      • Consider $2k+3$
      • Cases:
        • 1
          • So $p_{2n+2}\to a_{2n+3}$
          • Then $p_{2n+3}\to a_{2n+1}$.
          • Then $a_{2n+2}$ is empty
        • 2
          • So $p_{2n+2}\to a_{2n+3}$
          • and $p_{2n+3}\to a_{2n+2}$
          • So then $a_{2n+1}$ is empty