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: