Tutorial 3 Solutions

How to submit:

• Submit before actual tutorial time for it to be graded. There are 2 ways to do this:
  1. There is a submission box on Canvas for you to submit your document. Either .docx, .pdf, or a picture of your written solutions are acceptable as long as we can read your attempts.
  2. Submit your written attempts in-person during our tutorial.

• Official due date for submission : 18-Mar-2025, 23:59 or during tutorial itself.

Collaboration Policy:

• You may discuss high-level ideas with your classmates or friends. You should list your collaborators if you do so.
• Do not share your solutions.
• ChatGPT (and other LLMs) are not allowed.
• Your submission must be of your own write-up.

Late Policy:

• < 1 week after submission deadline: 50% penalty
• < 2 weeks after submission deadline: 75% penalty
• No submissions after 2 weeks.

Overview

This tutorial gives practice questions to be discussed during the relevant tutorial in person. This particular tutorial sheet corresponds to Unit 4 and Unit 5. It is recommended to either watch the lectures or read the notes for each respective parts before attempting the tutorial sheet.

1. Questions 1 through 5 are related to induction and recurrences.
2. Questions 6 through 8 are related to asymptotic notation.

After week 7’s content, you should be able to attempt questions 1 through 5. After week 8’s content, you should be able to attempt questions 6 through 8.

Questions 1, 3, 6, are graded for participation.

That said, we encourage you to try all the questions, this way when you come for tutorial we can best make use of your time since you can either verify your solutions, or understand the discussions when our tutors go through the solutions.

---

Question 1 [Graded for Participation]

Using mathematical induction, prove that:

$$\forall n\ge 1\left[\sum _{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}\right]$$

Solution:

Proof

1. (Base case) Let $n=1$, then ${\sum }_{i=1}^1{i}^2=\frac{1(1+1)(2(1)+1)}{6}=1$. [Basic algebra]
2. (Inductive step) Assume that for $n=j$, where $j\in \mathbb{N},{\sum }_{i=1}^1{i}^2=\frac{j(j+1)(2j+1)}{6}$
3. ${\sum }_{i=1}^{j+1}{i}^2={\sum }_{i=1}^j{i}^2+(j+1{)}^2$ [Basic algebra]
4. $=\frac{j(j+1)(2j+1)}{6}+(j+1{)}^2$ [By assumption on line 2]
5. $=(j+1)[\frac{j(2j+1)}{6}+(j+1)]$ [Basic algebra]
6. $=(j+1)\left(\frac{2j^2+j+6j+6}{6}\right)$ [Basic algebra]
7. $=(j+1)\left(\frac{2j^2+7j+6}{6}\right)$ [Basic algebra]
8. $=(j+1)\left[\frac{(j+2)(2j+3)}{6}\right]$ [Basic algebra]
9. $=\frac{(j+1)[(j+1)+1][2(j+1)+1]}{6}$ [Basic algebra]
10. $\therefore \forall n\in \mathbb{N}[{\sum }_{i=1}^n{i}^2=\frac{(n)(n+1)(2n+1)}{6}]$ [Principle of mathematical induction]

---

Question 2

Using mathematical induction, prove that:

$$\forall n\ge 1,\exists k\in \mathbb{N}\left[6^n-1=5\cdot k\right]$$

Solution:

Proof

1. (Base case) Let $n=1$. Then, $6^n-1=6^1-1=5=5\cdot 1$. [Basic algebra]

• Since $1\in \mathbb{N}$, $\exists k\in \mathbb{N}[6^n-1=5\cdot k]$. [Existential generalisation on line 1]

2. (Inductive step) Assume that for $n=j$, where $j\in \mathbb{N}$, $\exists k\in \mathbb{N}[6^j-1=5\cdot k]$.
3. Let $m\in \mathbb{N}$ be such that $6^j-1=5m$. [Existential instantiation on line 3]
4. $6^{j+1}-1=6^j\cdot 6-1=6\cdot (6^j-1)+5$. [Basic algebra]
5. $6\cdot (6^j-1)+5=6\cdot 5m+5=30m+5=5\cdot (6m+1)$. [By assumption on line 3]
6. $6^{j+1}-1=5\cdot (6m+1)$. [Basic algebra, from lines 5, 6]
7. Since $m\in \mathbb{N}$, $6m+1\in \mathbb{N}$. [Basic algebra]
8. $\exists k\in \mathbb{N}[6^{j+1}-1=5\cdot k]$ [Existential generalisation on lines 7, 8]
9. $\forall n\ge 1,\exists k\in \mathbb{N}[6^n-1=5\cdot k]$ [Principle of mathematical induction]

---

Question 3 [Graded for Participation]

Let $A(n)$ be a recurrence defined in the following way.

$$A(n)=\{\begin{array}{ll}1,& n=0\\ 3,& n=1\\ 2\times A(n-1)-A(n-2),& n\ge 2\end{array}$$

Sub-question 1

Compute the following values:

1. $A(0)$
2. $A(1)$
3. $A(2)$
4. $A(5)$

Sub-question 2

Prove via strong induction that $\forall n\ge 0[A(n)=2n+1]$.

Solution:

Sub-question 1:

1. $A(0)=1$
2. $A(1)=3$
3. $A(2)=2\times A(1)-A(0)=5$
4. Since $A(3)=2\times A(2)-A(1)=7$ and $A(4)=2\times A(3)-A(2)=9$, we have $A(5)=2\times A(4)-A(3)=11$.

Sub-question 2:

Proof

1. (Base cases) We prove the statement for $n=0$ and $n=1$. Clearly, $A(0)=1=2(0)+1$ and $A(1)=3=2(1)+1$.
2. (Inductive step) Let $k\ge 2$, and assume that $\forall 0\le j<k[A(j)=2j+1]$.
3. $A(k)=2\times A(k-1)-A(k-2)$ [By definition of $A(n)$]
4. Since $0\le k-1<k$ and $0\le k-2<k$, we have $A(k-1)=2(k-1)+1=2k-1$ and $A(k-2)=2(k-2)+1=2k-3$, respectively. [By assumption on line 2]
5. $A(k)=2\times (2k-1)-(2k-3)=4k-2-2k+3=2k+1$ [Basic algebra, from lines 3, 4]
6. $\forall n\ge 0[A(n)=2n+1]$ [Principle of mathematical induction]

---

Question 4

Let $M(n)$ be a recurrence defined in the following way.

$$M(n)=\{\begin{array}{ll}0& ,n=1\\ 2& ,n=2\\ 2\times M(\lfloor \frac{n}{2}\rfloor )+n& ,n\ge 3\end{array}$$

Prove via strong induction that:

$$\forall n\ge 3[M(n)\le n{\log }_2(n)]$$

You may find the following facts useful:

1. $\lfloor \frac{n}{2}\rfloor \le \frac{n}{2}$
2. $a\le b\to {\log }_2(a)\le {\log }_2(b)$

You may alternatively use the substitution method to prove that this is $O(n\log n)$.

Solution:

Proof

1. (Base cases) We will prove the statement for $n=3$, $n=4$ and $n=5$.

• For $n=3$: $M(3)=2\times M(1)+3=2\times 0+3=3\le 3{\log }_2(3)$
• For $n=4$: $M(4)=2\times M(2)+4=2\times 2+4=8\le 4{\log }_2(4)$
• For $n=5$: $M(5)=2\times M(2)+5=2\times 2+5=9\le 5{\log }_2(5)$

2. (Inductive step) Let $k\ge 6$, and assume that $\forall 3\le j<k[M(j)\le j{\log }_2(j)]$.
3. Since $k\ge 6$, $\lfloor \frac{k}{2}\rfloor \ge 3$, so our assumption applies to $\lfloor \frac{k}{2}\rfloor$.
4. $M(k)=2\times M(\lfloor \frac{k}{2}\rfloor )+k\le 2\lfloor \frac{k}{2}\rfloor {\log }_2(\lfloor \frac{k}{2}\rfloor )+k$ [By assumption on line 2]
5. $2\lfloor \frac{k}{2}\rfloor {\log }_2(\lfloor \frac{k}{2}\rfloor )+k\le 2(\frac{k}{2}){\log }_2(\frac{k}{2})+k=k{\log }_2(\frac{k}{2})+k$ [Facts 1, 2]
6. $k{\log }_2(\frac{k}{2})+k=k{\log }_{2}k-k{\log }_{2}2+k=k{\log }_{2}k-k+k=k{\log }_{2}k$ [Basic algebra]
7. $M(k)\le k{\log }_{2}k$ [From lines 4, 6]
8. $\forall n\ge 3[M(n)\le n{\log }_2(n)]$ [Principle of mathematical induction]

---

Question 5

Let $B(n)$ be a recurrence defined in the following way.

$$B(n)=\{\begin{array}{ll}1,& n=0\\ 3\times B(n-1),& n\ge 1\end{array}$$

Prove by induction that:

$$\forall n\in \mathbb{N}[B(n)=3^n]$$

Solution:

Proof

1. (Base case) Let $n=0$. Then, $B(0)=1=3^0$.
2. (Inductive step) Assume that for $n=j$, where $j\in \mathbb{N}$, $B(j)=3^j$.
3. $B(j+1)=3^{j+1}=3\times 3^j=3\times B(j)$ [By assumption on line 2]
4. $\forall n\in \mathbb{N}[B(n)=3^n]$ [Principle of mathematical induction]

---

Question 6 [Graded for Participation]

Let $B(n)$ be a recurrence defined in the following way.

$$B(n)=\{\begin{array}{ll}1,& n=0\\ 3\times B(n-1),& n\ge 1\end{array}$$

Sub-part 1

True or false? $B(n)\in O(3^n)$

(Hint: You may want to use the statement at end of question 4)

If it is true, explicitly give values $n_0$ and $c$ to justify that $B(n)$ is indeed in $O(3^n)$

Solution:

True. From Q5, we have that $B(n)=3^n$.

Proof

1. Let $n_0=1\in \mathbb{N}$ and $c=1\in {\mathbb{R}}^{+}$.

• Then, $B(n)=3^n\le c\cdot 3^n$, for all $n\ge n_0$. [Basic algebra]

2. $\exists n_0\in \mathbb{N},\exists c\in {\mathbb{R}}^{+},\forall n\ge n_0[B(n)\le c\cdot 3^n]$ [Existential generalisation on line 1]
3. $B(n)\in O(3^n)$ [Definition of $O$]

Sub-part 2

True or false? $B(n)\in \Omega (3^n)$

(Hint: You may want to use the statement at end of question 4)

If it is true, explicitly give values $n_0$ and $c$ to justify that $B(n)$ is indeed in $\Omega (3^n)$

Solution:

True.

Proof

1. Let $n_0=1\in \mathbb{N}$ and $c=1\in {\mathbb{R}}^{+}$.

• Then, $B(n)=3^n\ge c\cdot 3^n$, for all $n\ge n_0$. [Basic algebra]

1. $\exists n_0\in \mathbb{N},\exists c\in {\mathbb{R}}^{+},\forall n\ge n_0[B(n)\ge c\cdot 3^n]$ [Existential generalisation on line 1]
2. $B(n)\in \Omega (3^n)$ [Definition of $\Omega$]

Sub-part 3

True or false? $B(n)\in \Theta (3^n)$

Why/why not? You do not have to give a proof.

(Hint: What is the definition of $\Theta$?)

Solution:

True. Since $B(n)\in O(3^n)\wedge B(n)\in \Omega (3^n)$, we have that $B(n)\in O(3^n)\cap \Omega (3^n)$, which means that $B(n)\in \Theta (3^n)$.

---

Question 7

Let $f(n),g(n)$ be functions such that $\forall n\in \mathbb{N}[f(n)\ge 0]$ and $\forall n\in \mathbb{N}[g(n)\ge 0]$. I.e. the functions are always non-negative.

Prove that:

$$\max (f(n),g(n))\in O(f(n)+g(n))$$

Solution:

We refer to the following definition:

$$\max (a,b)=\{\begin{array}{ll}a,& a\ge b\\ b,& b>a\end{array}$$

Proof

1. Let $f(n)$ and $g(n)$ be arbitrarily chosen functions.
2. Observe that $\max (f(n),g(n))\le f(n)+g(n)$ since both functions are always non-negative. [Basic algebra]
3. Then, $\max (f(n),g(n))\le f(n)+g(n)=1\cdot (f(n)+g(n))$, for all $n\in \mathbb{N}$, i.e. for all $n\ge 0$. [Basic algebra]
4. Letting $n_0=0\in \mathbb{N}$, $c=1\in {\mathbb{R}}^{+}$, we see that $\exists n_0\in \mathbb{N},\exists c\in {\mathbb{R}}^{+},\forall n\ge n_0\left[\max \right(f(n),g(n))\le c\cdot (f(n)+g(n))]$. [Existential generalisation on line 3]
5. $\max (f(n),g(n))\in O(f(n)+g(n))$ [Definition of $O$]

---

Question 8 (Challenging!)

Prove that:

$$2^{2n}\notin O(2^n)$$

[Hint: Assume that $2^{2n}\in O(2^n)$. What kind of contradiction will you derive?]

Proof

1. Assume for the sake of contradiction that $2^{2n}\in O(2^n)$.
2. $\exists n_0\in \mathbb{N},\exists c\in {\mathbb{R}}^{+},\forall n\ge n_0[2^{2n}\le c\cdot 2^n]$ [Unpacking definition of O]
3. Let $m\in \mathbb{N},k\in {\mathbb{R}}^{+}$ such that $\forall n\ge m[2^{2n}\le k\cdot 2^n]$ [Existential instantiation on line 2]
4. $\forall n\ge m[\frac{2^{2n}}{2^n}\le k]$ [Basic algebra]
5. $\forall n\ge m[2^n\le k]$ [Basic algebra]
6. As $n$ approaches infinity, $2^n>k$. [Basic algebra; see below for a more rigorous proof]
7. $\therefore \exists n\ge m[2^n>k]$ [Existential generalization on line 6]
8. $\neg (\forall n\ge m[2^n\le k])$ [Logically equivalent to line 7]
9. $\neg (\forall n\ge m[2^n\le k])\wedge (\forall n\ge m[2^n\le k])$ [Conjunction on lines 5 and 8]
10. $\therefore \perp$ [Contradiction rule on line 9]
11. $\therefore 2^{2n}\notin O(2^n)$ [Proof by contradiction on line 10]

To prove the idea that one can always find a value of $n$ such that $2^n>k$, we can do the following:

Sub-Proof:

1. Consider $n=\max (1+{\log }_{2}k,m)$.
2. Then, $n>{\log }_{2}k$. [Basic algebra]
3. $2^n>2^{{\log }_{2}k}=k$. [Basic algebra]
4. Also, $n\ge m$. [Basic algebra, from line 2]
5. $\exists n\ge m[2^n>k]$. [Existential generalisation on line 3, 4]