COMP 1002 Winter 2019
Homework Assignment # 5
Due: March 21, by 10pm
(Type it up and upload on D2L)

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: