COMP 1002 Winter 2019\ Homework Assignment \# 5\ Due: March 21, by 10pm\ (Type it up and upload on D2L)\ **YOUR NAME HERE**\ ------------------------------------------------------------------------ 1. **Induction examples**\ Prove the following by math. induction. The format of the proof should be as follows: 1) state what statement you are proving (it should have a variable on which you do induction as a parameter). 2) state the base case(s) and prove them. 3) state the induction hypothesis 4) state and prove the induction step. 1. Show that for all $n \geq 2$, $5^n +9 \leq 6^n$. *Solution:\ * 2. Show that $\forall n \geq 0$,   the number $7^{n+2}+8^{2n+1}$ is divisible by 57. *Solution:\ * 3. Consider a sequence defined as follows: $s_0 = 1$, $s_1 = 2$ and for $n \geq 2$, $s_n = 1 + \max\{s_{\lfloor {n/2}\rfloor}, s_{\lceil{n/2}\rceil}\}$ (Recall that $\lfloor x \rfloor$ is the floor of $x$, that is, largest integer $y \leq x$, and $\lceil x \rceil$ is the ceiling of $x$, smallest integer $y \geq x$.)\ Prove by **strong induction** that $\forall n > 0, s_{n} \geq s_{n-1}$. Hint: compare $s_{\lfloor (n+1)/2 \rfloor }$, $s_{\lceil (n+1)/2 \rceil}$, $s_{\lfloor n/2 \rfloor }$ and $s_{\lceil n/2 \rceil}​$. Which of them are the same and when? What is the relationship among ones that are not the same? *Solution:\ * 2. **Structural induction** 1. Give a recursive definition of a set $S$ of all binary that have the same number of 0s and 1s. *Solution:\ * 2. Now show, using structural induction on your recursive definition, that every string in your set has even number of symbols. *Solution:\ *