COMP 1002 Winter 2019

Homework Assignment # 5

Due: March 21, by 10pm

(Type it up and upload on D2L)

**YOUR NAME HERE**

**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.Show that for all $n \geq 2$, $5^n +9 \leq 6^n$.

*Solution:*Show that $\forall n \geq 0$, the number $7^{n+2}+8^{2n+1}$ is divisible by 57.

*Solution:*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:*

**Structural induction**Give a recursive definition of a set $S$ of all binary that have the same number of 0s and 1s.

*Solution:*Now show, using structural induction on your recursive definition, that every string in your set has even number of symbols.

*Solution:*