As­sign­ment 2

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

Name and Stu­dent Num­ber

Write your name and stu­dent num­ber on the top of the as­sign­ment

Grad­ing (5 marks): Five marks for in­clud­ing their name and stu­dent num­ber on the first page of the as­sign­ment. Zero marks for omit­ting it.

Re­peated sub­strings in bit­strings

Ar­bi­trary bit­strings

Let $B=b_1,\ldots,b_{1200}$ be a bit­string of length $1200$. Prove that $B$ con­tains at least two iden­ti­cal $10$-bit sub­strings. More pre­cisely, prove that there are dis­tinct in­dices $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}$.

So­lu­tion: There are only $2^{10}=1024$ dif­fer­ent $10$-bit strings, but there are $1191>1024$ in­dices that de­fine a $10$-bit sub­string of $B$. By the Pi­geon­hole Prin­ci­ple, some pair of in­dices $i$ and $j$ must de­fine the same $10$-bit string. ∎

Grad­ing (5 marks): 5 marks for a well-ex­plained and cor­rect use of the Pi­geon­hole Prin­ci­ple. Re­duce marks for a poor ex­pla­na­tion or an ar­gu­ment with a small cal­cu­la­tion error or over­sight. Give zero for a com­pletely in­cor­rect an­swer. ▶

$00$-free bit­strings

Re­call that a bit­string is $00$-free if it does not con­tain two con­sec­u­tive zeros. Let $B=b_1,\ldots,b_{1200}$ be a $00$-free bit­string of length $1200$. Prove that $B$ con­tains at least two iden­ti­cal $14$-bit sub­strings. More pre­cisely, prove that there are dis­tinct in­dices $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}$.

So­lu­tion: In class (and in Sec­tion 4.1.2 of the text­book) we saw that the num­ber of $00$-free bit­strings of length $n$ is $f_{n+2}$. Since every sub­string of $B$ is $00$-free, there are at most $f_{16}=987$ dis­tinct $14$-bit sub­strings in $B$. Since there are $1187>987$ in­dices that each de­fine a $14$-bit sub­string of $B$, there must be two dis­tinct in­dices $i$ and $j$ that de­fine the same $14$-bit sub­string. ∎

Grad­ing (5 marks): 5 marks for a well-ex­plained and cor­rect use of the Pi­geon­hole Prin­ci­ple. Re­duce marks for a poor ex­pla­na­tion or an ar­gu­ment with a small cal­cu­la­tion error or over­sight. Give zero for a com­pletely in­cor­rect an­swer. ▶

Re­cur­rences

An easy re­cur­rence

Con­sider the fol­low­ing re­cur­sive func­tion: $$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$.

So­lu­tion: We prove this by in­duc­tion on $n$. The base case $n=0$ is sat­is­fied since $\tfrac{1}{2}(7\cdot 3^0-5)=\tfrac{1}{2}(7-5)=1=f(0)$. Now as­sume that $f(k)=\tfrac{1}{2}(7\cdot 3^k-5)$ for all $k\in\{0,\ldots,n-1\}$ and prove the state­ment for an ar­bi­trary in­te­ger $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*}$$

Grad­ing (5 marks): 5 marks for a well-ex­plained and cor­rect use of in­duc­tion. Re­duce marks for a poor ex­pla­na­tion or an ar­gu­ment with a small cal­cu­la­tion error or over­sight. Give zero for a com­pletely in­cor­rect an­swer. ▶

A wild re­cur­rence

Con­sider the fol­low­ing re­cur­sive func­tion: $$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$.

So­lu­tion: We prove this by in­duc­tion 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 as­sume $f(k)=2^{k-2}\left((-1)^{k+1}+1\right)$ for all $k\in\{0,\ldots,n-1\}$ and prove the state­ment for an ar­bi­trary in­te­ger $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*}$$

Grad­ing (5 marks): 5 marks for a well-ex­plained and cor­rect use of in­duc­tion. Re­duce marks for a poor ex­pla­na­tion or an ar­gu­ment with a small cal­cu­la­tion error or over­sight. Give zero for a com­pletely in­cor­rect an­swer. ▶

Break­ing bad

Con­sider the fol­low­ing re­cur­sive func­tion: $$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 so­lu­tion for $f(n)$ and then prove that your closed form so­lu­tion is cor­rect.

So­lu­tion: Cal­cu­lat­ing the first few val­ues of $f(n)$ is enough to con­vince you that $f(n)=n$. This is ob­vi­ously true for $n=1$. Now as­sume $f(k)=k$ for all $k\in\{1,\ldots,n-1\}$ and prove the state­ment 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*}$$

Grad­ing (5 marks): 5 marks for a cor­rect an­swer and well-ex­plained and cor­rect use of in­duc­tion. Re­duce marks for a poor ex­pla­na­tion or an ar­gu­ment with a small cal­cu­la­tion error or over­sight. Give zero for a com­pletely in­cor­rect an­swer. ▶

Lay­ing out chop­sticks

You have $n$ chop­sticks that you want to place on a long table. Start­ing at the left end of the table and work­ing right, you can ei­ther place a sin­gle chop­stick ver­ti­cally or you can place two chop­sticks hor­i­zon­tally, one above the other, or you can place two chop­sticks so that they form an X. Here are ex­am­ples of two dif­fer­ent place­ments when $n=8$.

Note that we can ex­press a chop­stick place­ment as a string over the al­pha­bet $\{{\times},{=},{|}\}$, where the num­ber of ${|}$ sym­bols plus twice the num­ber of ${\times}$ and ${=}$ sym­bols is $n$. Two place­ments above would be rep­re­sented by "${|}{=}{\times}{|}{\times}$" and "${\times}{|}{|}{=}{=}$".

Let $F(n)$ be the num­ber of ways of plac­ing $n$ chop­sticks.

• We'll use the con­ven­tion that $F(0)=1$.

• $F(1)=1$ be­cause the only valid place­ment is "${|}$".

• $F(2)=3$ be­cause we have the place­ments "${|}{|}$", "${\times}$", and "${=}$".

• $F(3)=5$ be­cause we have the place­ments "${|}{|}{|}$", "${{|}{\times}}$", "${{\times}{|}}$", "${{|}{=}}$", and "${=}{|}$".

Find the re­cur­rence

Write a re­cur­sive for­mula for the num­ber of ways, $F(n)$, to place $n\ge 0$ chop­sticks. Ex­plain how you get this for­mula using our usual rules for count­ing (Prod­uct Rule, Sum Rule, Com­ple­ment Rule, etc). Check that your for­mula gives the cor­rect value of $F(n)$ for at least two con­sec­u­tive val­ues of $n$ that are not ex­plic­itly de­fined in your for­mula.

So­lu­tion: For $n\ge 2$, a place­ment of chop­sticks can ei­ther begin with a ${|}$, a ${\times}$, or a ${=}$. In the first case, what fol­lows is any place­ment of $n-1$ chop­sticks. In the sec­ond case, what fol­lows is any place­ment of $n-2$ chop­sticks. In the third case, what fol­lows is any place­ment of $n-2$ chop­sticks. Using the Sum Rule, this gives the re­cur­rence $$F(n) = F(n-1) + 2F(n-2)$$ with the base cases $F(0)=1$ and $F(1)=1$ given in the ques­tion. With this re­cur­rence, 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 cor­rect.

Grad­ing (5 marks): 5 marks for a cor­rect re­cur­rence that has an ex­pla­na­tion sim­i­lar to the one pro­vided above and that checks the an­swer for $n=2$ and $n=3$ (or some larger val­ues of $n$). Re­duce marks for a poor ex­pla­na­tion or an ar­gu­ment with a small cal­cu­la­tion error or over­sight. Lose 1 mark for not ver­i­fy­ing the so­lu­tion for two small val­ues of $n$. Give zero for a com­pletely in­cor­rect an­swer. ▶

Solve the re­cur­rence

Once you're sure that your re­cur­sive for­mula is cor­rect, find a closed form so­lu­tion and prove (by in­duc­tion) that this closed form matches your re­cur­sive for­mula. It's ok to use some­thing like Wol­fram Alpha to find the closed form, but you will still have to prove by in­duc­tion that the for­mula it gives you is cor­rect. Note: It's also ok to give a for­mula with two sep­a­rate cases (maybe one for even val­ues of $n$ and one for odd val­ues of $n$) as long as its not re­cur­sive.

So­lu­tion: Using Wol­fram Alpha to solve this gives the so­lu­tion $F(n)=\tfrac{1}{3}((-1)^n + 2^{n+1})$. I know what's com­ing, 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 an­swer is cor­rect by in­duc­tion 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 as­sume $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 deal­ing with the ex­pres­sion $(-1)^{n-1}+2(-1)^{n-2}$, it can be avoided by defin­ing your re­cur­sive for­mula 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 con­se­quence of this is that $2^{k}-1$ is di­vis­i­ble by $3$ for any pos­i­tive even in­te­ger $k$.

Grad­ing (5 marks): 5 marks for a cor­rect closed form and a com­plete proof by in­duc­tion that it is a cor­rect so­lu­tionto the re­cur­rence. Re­duce marks for an ar­gu­ment with a small cal­cu­la­tion error or over­sight. Give zero for a com­pletely in­cor­rect an­swer. ▶

Simon is at it again

Simon goes to the pub with $n=4^k$ dol­lars in his pocket for some non-neg­a­tive in­te­ger $k$. This is Peel Pub circa 1980, so one beer costs one dol­lar and and a plate of na­chos also costs one dol­lar. Simon re­peat­edly does the fol­low­ing, until he is left with only one dol­lar:

• Simon spends half his re­main­ing money on beer
• Simon spends half his re­main­ing money on na­chos

Let $B(k)$ be the num­ber of beers Simon drinks. Let $N(k)$ be the num­ber of plates of na­chos Simon eats.

Hint: In solv­ing the ques­tions below, it's help­ful to re­mem­ber that $4^k=2^{2k}$.

How much beer

Give a re­cur­rence (with an ex­pla­na­tion) for $B(k)$. Find a closed form for your re­cur­rence and prove it is cor­rect.

So­lu­tion: If Simon has only $1=4^0$ dol­lars then Simon gets no beer, so $B(0)=0$. Oth­er­wise, Simon starts with $n=4^{k}=2^{2k}$ dol­lars for some $k\ge 2$. He then spends half his money on beer, drink­ing $2^{2k-1}$ beers and leav­ing him with $2^{2k-1}$ dol­lars. He then spends half his money on na­chos, leav­ing him with $2^{2k-2}=2^{2(k-1)}=4^{k-1}$ dol­lars. He then re­peats this process with his re­main­ing $4^{k-1}$ dol­lars. This gives the re­cur­rence $$B(k) = \begin{cases} 0 & \text{if $k=0$} \\ 2^{2k-1} + B(k-1) & \text{if $k\ge 1$} \end{cases}$$ The eas­i­est way to guess the so­lu­tion here is just to re­peat­edly ex­pand the re­cur­rence: $$\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 eval­u­ate the sum $\sum_{j=1}^{k} 4^j$ di­rectly. For now, we can just check that our guess was cor­rect using in­duc­tion.

When $k=0$, we have $\tfrac{2}{3}(4^0-1)=\tfrac{2}{3}(1-1)=0=B(0)$, which han­dles the base case. Now we can as­sume $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*}$$

Grad­ing (5 marks): $2.5$ marks for get­ting the cor­rect re­cur­rence and $2.5$ marks for solv­ing it cor­rectly (in­clud­ing a proof that the guess is cor­rect).

How much na­chos

Give a re­cur­rence (with an ex­pla­na­tion) for $N(k)$. Find a closed form for your re­cur­rence and prove it is cor­rect.

So­lu­tion: If Simon has only $1=4^0$ dol­lars then Simon gets no na­chos, so $B(0)=0$. Oth­er­wise, Simon starts with $n=4^{k}=2^{2k}$ dol­lars for some $k\ge 2$. He then spends half his money on beer, leav­ing him with $2^{2k-1}$ dol­lars. He then spends half his money on na­chos, eat­ing $2^{2k-2}$ plates of na­chos, and leav­ing him with $2^{2k-2}=2^{2(k-1)}=4^{k-1}$ dol­lars. He then re­peats this process with his re­main­ing $4^{k-1}$ dol­lars. This gives the re­cur­rence $$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 ei­ther re­peat all the steps used to solve $B(k)$ or you can no­tice that $N(k)=\tfrac{1}{2}B(k)$. In ei­ther case, you get the an­swer $N(k)=\tfrac{1}{3}(4^k-1)$.

Grad­ing (5 marks): $2.5$ marks for get­ting the cor­rect re­cur­rence and $2.5$ marks for solv­ing it cor­rectly (in­clud­ing a proof that the guess is cor­rect).

A weird re­cur­rence

Con­sider the fol­low­ing func­tion

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 ter­mi­nate?

Ex­plain why, for any in­te­ger $n\ge 1$, $P(n)$ even­tu­ally ter­mi­nates.

So­lu­tion: If we trace the value of $n$ dur­ing a re­cur­sive call, it is in­cre­mented at most $3$ times, then it is de­creased by $7$, so it de­creases by at least $4$ dur­ing any se­quence of $4$ con­sec­u­tive calls. This en­sures that, after at most $n$ re­cur­sive calls, the value of $n$ is less than or equal to zero. The only ques­tion is what hap­pens when $n\in\{1,2,3,4,5,6,7\}$ gets close to zero. When $n\in\{1,2,3\}$, it is re­peat­edly in­cre­mented until $n=4$ then $P(n-7)=P(-3)$ is called and the func­tion ter­mi­nates. When $n\in\{5,6,7\}$ it is re­peat­edly in­cre­mented until $n=8$ and then $P(n-7)=P(1)$ is called and we've al­ready es­tab­lished that this ter­mi­nates.

Grad­ing (5 marks): Any rea­son­able ex­pla­na­tion for why this ter­mi­nates should be given five marks. Some stu­dents may do a proof by in­duc­tion on $n$, for ex­am­ple.

How much does it print?

Write and solve a re­cur­rence that de­scribes ex­actly how many times $P(n)$ prints "hello" for any pos­i­tive in­te­ger $n$.

So­lu­tion: From the de­f­i­n­i­tion of the func­tion we get the fol­low­ing re­cur­rence: $$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 de­f­i­n­i­tion is an­noy­ing be­cause it al­lows for non-pos­i­tive val­ues of $n$, and we're only asked to study what hap­pens for pos­i­tive val­ues of $n$. In the pre­vi­ous ques­tion, we al­ready fig­ured out what hap­pens for small pos­i­tive val­ues, 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 al­ready show a pat­tern that leads us to guess that $K(n)=n-2$ when $n\bmod 4=0$. When $n\bmod 4\neq 0$ we need to ac­count for the $4\lceil n/4\rceil-n$ steps re­quired to count up to the next mul­ti­ple of $4$. Fid­dling around with the for­mula 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 as­sume 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*}$$

Grad­ing (5 marks): There are lots of ways to go wrong here. Stu­dents should be given $2.5$ marks for get­ting the right re­cur­rence and $2.5$ marks for solv­ing it cor­rectly. Be gen­er­ous with part marks. Be sure to watch out for stu­dents ap­ply­ing the in­duc­tive hy­poth­e­sis in­cor­rectly. In par­tic­u­lar, un­less they jus­tify a dif­fer­ent in­duc­tive hy­poth­e­sis, they can not apply the in­duc­tive hy­poth­e­sis to de­duce that $K(n+1)=8\lceil (n + 1)/4\rceil - n - 3$.