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.

Questions 1 through 5 are related to induction and recurrences.
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 \geq 1 [i = 1 \sum n i^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}]

Question 2

Using mathematical induction, prove that:

\forall n \geq 1, \exists k \in N [6^{n} - 1 = 5 \cdot k]

Question 3 [Graded for Participation]

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

A (n) = ⎩ ⎨ ⎧ 1, 3, 2 \times A (n - 1) - A (n - 2), n = 0 n = 1 n \geq 2

Sub-question 1

Compute the following values:

$A (0)$
$A (1)$
$A (2)$
$A (5)$

Sub-question 2

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

Question 4

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

M (n) = ⎩ ⎨ ⎧ 02 2 \times M (⌊ \frac{n}{2} ⌋) + n, n = 1, n = 2, n \geq 3

Prove via strong induction that:

\forall n \geq 3 [M (n) \leq n lo g_{2} (n)]

You may find the following facts useful:

$⌊ \frac{n}{2} ⌋ \leq \frac{n}{2}$
$a \leq b \to lo g_{2} (a) \leq lo g_{2} (b)$

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

Question 5

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

B (n) = {1, 3 \times B (n - 1), n = 0 n \geq 1

Prove by induction that:

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

Question 6 [Graded for Participation]

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

B (n) = {1, 3 \times B (n - 1), n = 0 n \geq 1

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})$

Sub-part 2

True or false? $B (n) \in Ω (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 $Ω (3^{n})$

Sub-part 3

True or false? $B (n) \in Θ (3^{n})$

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

(Hint: What is the definition of $Θ$ ?)

Question 7

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

Prove that:

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

Question 8 (Challenging!)