Assignment 2

$\newcommand{\IN}{\mathbb{N}}$

Name and Student Number

Write your name and student number on the top of the assignment

Grading (5 marks): Five marks for including their name and student number on the first page of the assignment. Zero marks for omitting it.

Repeated substrings in bitstrings

Arbitrary bitstrings

Let $B=b_1,\ldots,b_{1200}$ be a bitstring of length $1200$. Prove that $B$ contains at least two identical $10$-bit substrings. More precisely, prove that there are distinct indices $i,j\in\{1,\ldots,1191\}$ such that $b_{i},b_{i+1},\ldots,b_{i+9}=b_j,b_{j+1},\ldots,b_{j+9}$.

Solution: There are only $2^{10}=1024$ different $10$-bit strings, but there are $1191>1024$ indices that define a $10$-bit substring of $B$. By the Pigeonhole Principle, some pair of indices $i$ and $j$ must define the same $10$-bit string. ∎

Grading (5 marks): 5 marks for a well-explained and correct use of the Pigeonhole Principle. Reduce marks for a poor explanation or an argument with a small calculation error or oversight. Give zero for a completely incorrect answer. ▶

$00$-free bitstrings

Recall that a bitstring is $00$-free if it does not contain two consecutive zeros. Let $B=b_1,\ldots,b_{1200}$ be a $00$-free bitstring of length $1200$. Prove that $B$ contains at least two identical $14$-bit substrings. More precisely, prove that there are distinct indices $i,j\in\{1,\ldots,1187\}$ such that $b_{i},b_{i+1},\ldots,b_{i+13}=b_j,b_{j+1},\ldots,b_{j+13}$.

Solution: In class (and in Section 4.1.2 of the textbook) we saw that the number of $00$-free bitstrings of length $n$ is $f_{n+2}$. Since every substring of $B$ is $00$-free, there are at most $f_{16}=987$ distinct $14$-bit substrings in $B$. Since there are $1187>987$ indices that each define a $14$-bit substring of $B$, there must be two distinct indices $i$ and $j$ that define the same $14$-bit substring. ∎

Grading (5 marks): 5 marks for a well-explained and correct use of the Pigeonhole Principle. Reduce marks for a poor explanation or an argument with a small calculation error or oversight. Give zero for a completely incorrect answer. ▶

Recurrences

An easy recurrence

Consider the following recursive function: \[ f(n) = \begin{cases} 1 & \text{if $n=0$} \\ 3\cdot f(n-1)+5 & \text{if $n\ge 1$} \end{cases} \]

Prove that $f(n)=\tfrac{1}{2}(7\cdot 3^n-5)$ for all $n\ge 0$.

Solution: We prove this by induction on $n$. The base case $n=0$ is satisfied since $\tfrac{1}{2}(7\cdot 3^0-5)=\tfrac{1}{2}(7-5)=1=f(0)$. Now assume that $f(k)=\tfrac{1}{2}(7\cdot 3^k-5)$ for all $k\in\{0,\ldots,n-1\}$ and prove the statement for an arbitrary integer $n\ge 1$.
\begin{align*} f(n) & = 3f(n-1)+5 & \text{(by the definition of $f(n)$)} \\ & = 3\cdot\tfrac{1}{2}(7\cdot 3^{n-1}-5) + 5 & \text{(by the inductive hypothesis with $k=n-1$)} \\ & = \tfrac{1}{2}(7\cdot 3^{n}-15) + 5 & \text{(by algebra)} \\ & = \tfrac{1}{2}(7\cdot 3^{n}-5) & \text{(by algebra).} \end{align*}

Grading (5 marks): 5 marks for a well-explained and correct use of induction. Reduce marks for a poor explanation or an argument with a small calculation error or oversight. Give zero for a completely incorrect answer. ▶

A wild recurrence

Consider the following recursive function: \[ f(n) = \begin{cases} 0 & \text{if $n=0$} \\ 1 & \text{if $n=1$} \\ 4\cdot f(n-2) & \text{if $n\ge 2$} \end{cases} \]

Prove that $f(n)=2^{n-2}\left((-1)^{n+1}+1\right)$ for all $n\ge 0$.

Solution: We prove this by induction on $n$. There are two base cases:
When $n=0$, $2^{0-2}\left((-1)^{0+1}+1\right)= 2^{-2}\cdot 0=0=f(0)$.
When $n=1$, $2^{1-2}\left((-1)^{1+1}+1\right)= 2^{-1}\cdot (1+1)=2^{-1}\cdot 2^1=2^0=1=f(1)$.
Now assume $f(k)=2^{k-2}\left((-1)^{k+1}+1\right)$ for all $k\in\{0,\ldots,n-1\}$ and prove the statement for an arbitrary integer $n\ge 2$. For $n\ge 2$,
\begin{align*} f(n) & = 4\cdot f(n-2) & \text{(by the definition of $f(n)$)} \\ & = 4\cdot 2^{n-4}\left((-1)^{n-1}+1\right) & \text{(by the inductive hypothesis)} \\ & = 2^2\cdot 2^{n-4}\left((-1)^{n-1}+1\right) & \text{(since $4=2^2$)} \\ & = 2^{n-2}\left((-1)^{n-1}+1\right) \\ & = 2^{n-2}\left((-1)^{n+1}+1\right) & \text{(since $(-1)^2=1$).} \end{align*}

Grading (5 marks): 5 marks for a well-explained and correct use of induction. Reduce marks for a poor explanation or an argument with a small calculation error or oversight. Give zero for a completely incorrect answer. ▶

Breaking bad

Consider the following recursive function: \[ f(n) = \begin{cases} 1 & \text{if $n=1$} \\ \max\{f(\ell)+f(n-\ell): \ell\in\{1,\ldots,n-1\}\} & \text{if $n\ge 2$} \end{cases} \]

Give a closed form solution for $f(n)$ and then prove that your closed form solution is correct.

Solution: Calculating the first few values of $f(n)$ is enough to convince you that $f(n)=n$. This is obviously true for $n=1$. Now assume $f(k)=k$ for all $k\in\{1,\ldots,n-1\}$ and prove the statement for $n\ge 2$. For $n\ge 2$ we have

\begin{align*} f(n) & = \max\{f(k)+f(n-k): k\in\{1,\ldots,n-1\}\} & \text{(by the definition of $f(n)$)} \\ & = \max\{\ell+f(n-\ell): \ell\in\{1,\ldots,n-1\}\} & \text{(by the inductive hypothesis, since $\ell\in\{1,\ldots,n-1\}$)} \\ & = \max\{\ell+ (n-\ell): \ell\in\{1,\ldots,n-1\}\} & \text{(by the inductive hypothesis, since $n-\ell\in\{1,\ldots,n-1\}$)} \\ & = \max\{n: \ell\in\{1,\ldots,n-1\}\} & \text{(by algebra)} \\ & = n \end{align*}

Grading (5 marks): 5 marks for a correct answer and well-explained and correct use of induction. Reduce marks for a poor explanation or an argument with a small calculation error or oversight. Give zero for a completely incorrect answer. ▶

Laying out chopsticks

You have $n$ chopsticks that you want to place on a long table. Starting at the left end of the table and working right, you can either place a single chopstick vertically or you can place two chopsticks horizontally, one above the other, or you can place two chopsticks so that they form an X. Here are examples of two different placements when $n=8$.

Note that we can express a chopstick placement as a string over the alphabet $\{{\times},{=},{|}\}$, where the number of ${|}$ symbols plus twice the number of ${\times}$ and ${=}$ symbols is $n$. Two placements above would be represented by "${|}{=}{\times}{|}{\times}$" and "${\times}{|}{|}{=}{=}$".

Let $F(n)$ be the number of ways of placing $n$ chopsticks.

• We'll use the convention that $F(0)=1$.

• $F(1)=1$ because the only valid placement is "${|}$".

• $F(2)=3$ because we have the placements "${|}{|}$", "${\times}$", and "${=}$".

• $F(3)=5$ because we have the placements "${|}{|}{|}$", "${{|}{\times}}$", "${{\times}{|}}$", "${{|}{=}}$", and "${=}{|}$".

Find the recurrence

Write a recursive formula for the number of ways, $F(n)$, to place $n\ge 0$ chopsticks. Explain how you get this formula using our usual rules for counting (Product Rule, Sum Rule, Complement Rule, etc). Check that your formula gives the correct value of $F(n)$ for at least two consecutive values of $n$ that are not explicitly defined in your formula.

Solution: For $n\ge 2$, a placement of chopsticks can either begin with a ${|}$, a ${\times}$, or a ${=}$. In the first case, what follows is any placement of $n-1$ chopsticks. In the second case, what follows is any placement of $n-2$ chopsticks. In the third case, what follows is any placement of $n-2$ chopsticks. Using the Sum Rule, this gives the recurrence \[ F(n) = F(n-1) + 2F(n-2) \] with the base cases $F(0)=1$ and $F(1)=1$ given in the question. With this recurrence, we get $F(2)=F(1)+2F(0)=1+2=3$ and $F(3)=F(2)+2F(1)= 3+2=5$, both of which are correct.

Grading (5 marks): 5 marks for a correct recurrence that has an explanation similar to the one provided above and that checks the answer for $n=2$ and $n=3$ (or some larger values of $n$). Reduce marks for a poor explanation or an argument with a small calculation error or oversight. Lose 1 mark for not verifying the solution for two small values of $n$. Give zero for a completely incorrect answer. ▶

Solve the recurrence

Once you're sure that your recursive formula is correct, find a closed form solution and prove (by induction) that this closed form matches your recursive formula. It's ok to use something like Wolfram Alpha to find the closed form, but you will still have to prove by induction that the formula it gives you is correct. Note: It's also ok to give a formula with two separate cases (maybe one for even values of $n$ and one for odd values of $n$) as long as its not recursive.

Solution: Using Wolfram Alpha to solve this gives the solution $F(n)=\tfrac{1}{3}((-1)^n + 2^{n+1})$. I know what's coming, so I'll point out now that \[ (-1)^k + 2(-1)^{k-1} = (-1)^{k+1} \] (If $k$ is odd, then $(-1)^k + 2\cdot(-1)^{k-1}=-1+2=1=(-1)^{k+1}$ and if $k$ is even, then $(-1)^k + 2\cdot(-1)^{k-1}=1-2=-1=(-1)^{k+1}$.)

Now we can prove this answer is correct by induction on $n$.

• When $n=0$ we have $\tfrac{1}{3}((-1)^0+2^{0+1})=\tfrac{1}{3}(1+2)=1=F(0)$.

• When $n=1$ we have $\tfrac{1}{3}((-1)^1+2^{1+1})=\tfrac{1}{3}(-1+4)=1=F(1)$.

• Now we assume $F(k)=\tfrac{1}{3}((-1)^k + 2^{k+1})$ for all $k\in\{0,\ldots,n-1\}$ and prove that $F(n)=\tfrac{1}{3}((-1)^n + 2^{n+1})$ for each $n\ge 2$. For $n\ge 2$, \begin{align*} F(n) & = F(n-1) + 2F(n-2) & \text{(by the definition of $F(n)$)} \\ & = \tfrac{1}{3}((-1)^{n-1}+2^{n}) + \tfrac{2}{3}((-1)^{n-2}+2^{n-1}) & \text{(by the inductive hypothesis)} \\ & = \tfrac{1}{3}((-1)^{n-1}+ 2(-1)^{n-2} + 2^{n} + 2^n) & \text{(by algebra)} \\ & = \tfrac{1}{3}((-1)^{n-1}+ 2(-1)^{n-2} + 2^{n+1}) & \text{(by algebra)} \\ & = \tfrac{1}{3}((-1)^{n} + 2^{n+1}) & \text{(by the observation made above)} \end{align*} If you don't like dealing with the expression $(-1)^{n-1}+2(-1)^{n-2}$, it can be avoided by defining your recursive formula as \[ F(n) = \begin{cases} \tfrac{1}{3}(2^{n+1}) & \text{if $n$ is even} \\ \tfrac{1}{3}(2^{n+1}-1) & \text{if $n$ is odd} \end{cases} \] One cool consequence of this is that $2^{k}-1$ is divisible by $3$ for any positive even integer $k$.

Grading (5 marks): 5 marks for a correct closed form and a complete proof by induction that it is a correct solutionto the recurrence. Reduce marks for an argument with a small calculation error or oversight. Give zero for a completely incorrect answer. ▶

Simon is at it again

Simon goes to the pub with $n=4^k$ dollars in his pocket for some non-negative integer $k$. This is Peel Pub circa 1980, so one beer costs one dollar and and a plate of nachos also costs one dollar. Simon repeatedly does the following, until he is left with only one dollar:

• Simon spends half his remaining money on beer
• Simon spends half his remaining money on nachos

Let $B(k)$ be the number of beers Simon drinks. Let $N(k)$ be the number of plates of nachos Simon eats.

Hint: In solving the questions below, it's helpful to remember that $4^k=2^{2k}$.

How much beer

Give a recurrence (with an explanation) for $B(k)$. Find a closed form for your recurrence and prove it is correct.

Solution: If Simon has only $1=4^0$ dollars then Simon gets no beer, so $B(0)=0$. Otherwise, Simon starts with $n=4^{k}=2^{2k}$ dollars for some $k\ge 2$. He then spends half his money on beer, drinking $2^{2k-1}$ beers and leaving him with $2^{2k-1}$ dollars. He then spends half his money on nachos, leaving him with $2^{2k-2}=2^{2(k-1)}=4^{k-1}$ dollars. He then repeats this process with his remaining $4^{k-1}$ dollars. This gives the recurrence \[ B(k) = \begin{cases} 0 & \text{if $k=0$} \\ 2^{2k-1} + B(k-1) & \text{if $k\ge 1$} \end{cases} \] The easiest way to guess the solution here is just to repeatedly expand the recurrence: \begin{align*} B(k) & = 2^{2k-1} + B(k-1) \\ & = 2^{2k-1} + 2^{2(k-1)-1} + B(k-2) \\ & = 2^{2k-1} + 2^{2k-3} + B(k-2) \\ & = 2^{2k-1} + 2^{2k-3} + 2^{2k-5} + B(k-3) \\ & = 2^{2k-1} + 2^{2k-3} + 2^{2k-5} + 2^{2k-7} + \cdots + 32 + 8 + 2 \\ & = \tfrac{1}{2}(2^{2k} + 2^{2k-2} + 2^{2k-4} + \cdots + 2^6 + 2^4 + 2^2) \\ & = \tfrac{1}{2}\sum_{j=1}^k 4^j \\ & = \tfrac{2}{3}(4^k - 1) \end{align*} Later in the course, we'll learn how to evaluate the sum $\sum_{j=1}^{k} 4^j$ directly. For now, we can just check that our guess was correct using induction.

When $k=0$, we have $\tfrac{2}{3}(4^0-1)=\tfrac{2}{3}(1-1)=0=B(0)$, which handles the base case. Now we can assume $B(\ell)=\tfrac{2}{3}(4^{\ell}-1)$ for all $\ell\in\{0,\ldots,k-1\}$ and use this to prove that $B(k)=\tfrac{2}{3}(4^k-1)$, for $k\ge 1$. For $k\ge 1$, \begin{align*} B(k) & = 2^{2k-1} + B(k-1) & \text{(by the definition of $B(k)$)} \\ & = 2^{2k-1} + \tfrac{2}{3}(4^{k-2}-1) & \text{(by the inductive hypothesis with $\ell=k-1$)} \\ & = 2^{2k-1} + \tfrac{2}{3}(2^{2k-2}-1) & \text{(by algebra)} \\ & = 2^{2k-1} + \tfrac{1}{3}(2^{2k-1}-2) & \text{(by algebra)} \\ & = \tfrac{4}{3}\cdot 2^{2k-1} -\tfrac{2}{3} \\ & = \tfrac{2}{3}\cdot 2^{2k} -\tfrac{2}{3} \\ & = \tfrac{2}{3}(4^{k} -1) \\ \end{align*}

Grading (5 marks): $2.5$ marks for getting the correct recurrence and $2.5$ marks for solving it correctly (including a proof that the guess is correct).

How much nachos

Give a recurrence (with an explanation) for $N(k)$. Find a closed form for your recurrence and prove it is correct.

Solution: If Simon has only $1=4^0$ dollars then Simon gets no nachos, so $B(0)=0$. Otherwise, Simon starts with $n=4^{k}=2^{2k}$ dollars for some $k\ge 2$. He then spends half his money on beer, leaving him with $2^{2k-1}$ dollars. He then spends half his money on nachos, eating $2^{2k-2}$ plates of nachos, and leaving him with $2^{2k-2}=2^{2(k-1)}=4^{k-1}$ dollars. He then repeats this process with his remaining $4^{k-1}$ dollars. This gives the recurrence \[ N(k) = \begin{cases} 0 & \text{if $k=0$} \\ 2^{2k-2} + N(k-1) & \text{if $k\ge 1$} \end{cases} \] At this point you can either repeat all the steps used to solve $B(k)$ or you can notice that $N(k)=\tfrac{1}{2}B(k)$. In either case, you get the answer $N(k)=\tfrac{1}{3}(4^k-1)$.

Grading (5 marks): $2.5$ marks for getting the correct recurrence and $2.5$ marks for solving it correctly (including a proof that the guess is correct).

A weird recurrence

Consider the following function

P(n):
  print("hello")
  if n = -3
    return
  else if n is divisible by 4:
    P(n-7)
  else
    P(n+1)

Why does it terminate?

Explain why, for any integer $n\ge 1$, $P(n)$ eventually terminates.

Solution: If we trace the value of $n$ during a recursive call, it is incremented at most $3$ times, then it is decreased by $7$, so it decreases by at least $4$ during any sequence of $4$ consecutive calls. This ensures that, after at most $n$ recursive calls, the value of $n$ is less than or equal to zero. The only question is what happens when $n\in\{1,2,3,4,5,6,7\}$ gets close to zero. When $n\in\{1,2,3\}$, it is repeatedly incremented until $n=4$ then $P(n-7)=P(-3)$ is called and the function terminates. When $n\in\{5,6,7\}$ it is repeatedly incremented until $n=8$ and then $P(n-7)=P(1)$ is called and we've already established that this terminates.

Grading (5 marks): Any reasonable explanation for why this terminates should be given five marks. Some students may do a proof by induction on $n$, for example.

How much does it print?

Write and solve a recurrence that describes exactly how many times $P(n)$ prints "hello" for any positive integer $n$.

Solution: From the definition of the function we get the following recurrence: \[ K(n) = \begin{cases} 1 & \text{if $n=-3$} \\ K(n+1) & \text{if $n\ge -2$ and $n\bmod 4\neq 0$} \\ K(n-7) & \text{if $n\ge 0$ and $n\bmod 4= 0$} \end{cases} \] This definition is annoying because it allows for non-positive values of $n$, and we're only asked to study what happens for positive values of $n$. In the previous question, we already figured out what happens for small positive values, so we can use those: \[ K(n) = \begin{cases} 5 & \text{if $n=1$} \\ 4 & \text{if $n=2$} \\ 3 & \text{if $n=3$} \\ 2 & \text{if $n=4$} \\ 9 & \text{if $n=5$} \\ 8 & \text{if $n=6$} \\ 7 & \text{if $n=7$} \\ 6 & \text{if $n=8$} \\ K(n+1) & \text{if $n\ge 9$ and $n\bmod 4\neq 0$} \\ K(n-7) & \text{if $n\ge 9$ and $n\bmod 4= 0$} \end{cases} \] The small cases already show a pattern that leads us to guess that $K(n)=n-2$ when $n\bmod 4=0$. When $n\bmod 4\neq 0$ we need to account for the $4\lceil n/4\rceil-n$ steps required to count up to the next multiple of $4$. Fiddling around with the formula a bit leads to the guess $K(n)=2\cdot 4\lceil n/4\rceil-n-2=8\lceil n/4\rceil-n-2$.

• When $n=1$, $8\lceil 1/4\rceil-1-2 = 8-3 = 5 = K(1)$

• When $n=2$, $8\lceil 2/4\rceil-2-2 = 8-4 = 4 = K(2)$

• When $n=3$, $8\lceil 3/4\rceil-3-2 = 8-5 = 3 = K(3)$

• When $n=4$, $8\lceil 4/4\rceil-4-2 = 8-6 = 2 = K(4)$

• When $n=5$, $8\lceil 5/4\rceil-5-2 = 16-7 = 9 = K(5)$

• When $n=6$, $8\lceil 6/4\rceil-6-2 = 16-8 = 8 = K(6)$

• When $n=7$, $8\lceil 7/4\rceil-7-2 = 16-9 = 7 = K(7)$

• When $n=8$, $8\lceil 8/4\rceil-8-2 = 16-10 = 6 = K(8)$

Now we can assume that $K(k)=8\lceil k/4\rceil-k-2$ for all $k\in\{1,\ldots,n-1\}$ and use this to prove that $K(n)=8\lceil n/4\rceil-n-2$ for $n\ge 9$. For $n\ge 9$, we have \begin{align*} K(n) & = K(4\lceil n/4\rceil) + 4\lceil n/4\rceil-n & \text{(working through the definition)} \\ & = K(4\lceil n/4\rceil-7) + 1 + 4\lceil n/4\rceil-n & \text{(working through the definition)} \\ & = 8\lceil (4\lceil n/4\rceil-7)/4\rceil - ( 4\lceil n/4\rceil-7) - 2 + 1 + 4\lceil n/4\rceil-n & \text{(by the inductive hypothesis with $k=4\lceil n/4\rceil-7$)} \\ & = 8\lceil (4\lceil n/4\rceil-7)/4\rceil - n+6 \\ & = 8\lceil \lceil n/4\rceil-7/4\rceil - n+6 \\ & = 8(\lceil n/4\rceil- \lceil 7/4\rceil) - n+6 \\ & = 8(\lceil n/4\rceil-1) - n+6 \\ & = 8\lceil n/4\rceil - n-2 \end{align*}

Grading (5 marks): There are lots of ways to go wrong here. Students should be given $2.5$ marks for getting the right recurrence and $2.5$ marks for solving it correctly. Be generous with part marks. Be sure to watch out for students applying the inductive hypothesis incorrectly. In particular, unless they justify a different inductive hypothesis, they can not apply the inductive hypothesis to deduce that $K(n+1)=8\lceil (n + 1)/4\rceil - n - 3$.