## Exercise 1
Let $q_{n}=2 q_{n-1}+2 n+5$, and $q_{0}=4 .$ Compute $q_{1}, q_{2}, q_{3}$ and $q_{4}$.

---
$$
\begin{aligned}
q_{1} &=2 \cdot q_{1-1}+2 \cdot 1+5 \\
&=2 \cdot 4+2 \cdot 1+5 \\
&=15 \\
& \\
q_{2} &=2 \cdot q_{2-1}+2 \cdot 2+5 \\
&=2 \cdot 15+2 \cdot 2+5 \\
&=39 \\
& \\
q_{3} &=2 \cdot q_{3-1}+2 \cdot 3+5 \\
&=2 \cdot 39+2 \cdot 3+5 \\
&=89 \\
& \\
q_{4}&= 2 \cdot q_{4-1}+2 \cdot 4+5 \\
&=2 \cdot 89+2 \cdot 4+5 \\
&=191
\end{aligned}
$$

## Exercise 2

Define a sequence $\left\{x_{n}\right\}$ by $x_{0}=1$, and $x_{n}=2 x_{n-1}$ if $n \geq 1$. Find a closed form for the $n$ 'th term of this sequence. Prove that your
solution is correct.

---
We calculate the first few terms:
$$
\begin{array}{l}
x_{0}=1 \\
x_{1}=2 \cdot 1=2 \\
x_{2}=2 \cdot 2=4 \\
x_{3}=2 \cdot 4=8 \\
x_{4}=2 \cdot 8=16
\end{array}
$$

We recognize the sequence as $2^{n}$ for the first 4 iterations.

Let the predicate be $P(n)=``x_n=2^n"$.

**Basecase**

Since $2^0=1$, $P(0)$ is true.

**Inductive hypothesis**
Let $k\in \mathbb N$ and $k\geq1$.
Assume:

$$
x_{k-1}=2^{k-1}
$$

**Goal**
We want to prove the claim $P(k)$ that
$$x_k=2^k$$

**Inductive step**
$$
\begin{aligned}
x_{k}&=2 x_{k-1} \quad\left(\text { Definition of } x_{k}\right)\\
&=2 \cdot 2^{k-1} \quad \text { (Inductive Hypothesis) }\\
&=2^{k}
\end{aligned}
$$

Since the exponent rule is $c^a\cdot c^b =c^{a+b}$ and $2^1\cdot 2^{k-1}=2^{k-1+1}$.

We managed to rewrite the LH side to the RH side, thus proving the equation in our goal.

**Summary**
Since we proved that the base case $P(0)$ is true, and that $P(k)→P(k+1)$ for $k∈\mathbb{N}$, then by the principle of mathematical induction, we can conclude that $P(n)$ is true for all $n∈\mathbb{N}$.

## Exercise 3
Use the substitution method to prove that the following functions solve the given recurrence relations.
1. $\frac{4 n^{2}}{3}+1$ solves
$$
t(n)=\left\{\begin{array}{ll}
1 & \text { if } n=0 \\
t(n / 2)+n^{2} & \text { if } n \geq 1 .
\end{array}\right.
$$
---

### 3.1)
$\frac{4 n^{2}}{3}+1$ solves
$$
t(n)=\left\{\begin{array}{ll}
1 & \text { if } n=0 \\
t(n / 2)+n^{2} & \text { if } n \geq 1
\end{array}\right.
$$

Let the predicate $P(n)$ be
$P(n)=``t(n)=\frac{4n^2}{3}+1"$

**Base case:**
Since,
$$t(0)=1$$
<center>
and
</center>

$$\frac{4 \left ( \frac{0}{2} \right )^2 }{3} +1=1$$

P(0) is true.

**Inductive hypothesis**

Let $k\in \mathbb N$.
We assume that everything up to $P(k-1)$ is true
Then we have also assumed $P(\frac{k}{2})$ is true because $\frac{k}{2}<k-1$ when $2|k$ and $k≥1$. So we assume
$$t \left ( \frac{k}{2} \right )=\frac{4 \left ( \frac{k}{2}\right ) ^2}{3}+1$$

**Goal**
We want to prove the claim $P(k)$ that
$$t(k)=\frac{4 k^2 }{3}+1$$
So we will look at $t(k)$, the LH side, and we will rewrite it to the RH side.
#### Inductive step
$$t(k)=t(k/2)+k^2$$
We know what $t(\frac{k}{2})$ is from our inductive hypothesis, so we substitute in
$$
\begin{align}
t(k)&= \frac{4 \left ( \frac{k}{2}\right ) ^2}{3}+1+k^2\\
&= \frac{k^2}{3}+1+k^2
\end{align}
$$
We can expand $k^2=\frac{3\cdot k^2}{3}$
$$
\begin{align}
&=\frac{ k^2}{3} +\frac{3\cdot k^2}{3}+1\\
&= \frac{4\cdot k^2}{3}+1
\end{align}
$$
It is the same as the RH side, thus proving the equation in our goal.
**Summary**
Since we proved that the base case $P(0)$ is true, and that $P(k)→P(k+1)$ for $k∈\mathbb{N}$, then by the principle of mathematical induction, we can conclude that $P(n)$ is true for all $n∈\mathbb{N}$.

### 3.2)

2. $\frac{1}{4}\left(n^{2}(n+1)^{2}+4\right)$ solves
$$
r(n)=\left\{\begin{array}{ll}
1 & \text { if } n=0 \\
r(n-1)+n^{3} & \text { if } n \geq 1
\end{array}\right.
$$

---
Let the predicate $P(n)$ be
$P(n)=``r(n)=\frac{1}{4}\left(n^{2}(n+1)^{2}+4\right)"$
**Base case:**

Since $r(0)=1$ and
$$\begin{align}
\frac{1}{4}\left(0^{2}(0+1)^{2}+4\right)&=\\
\frac{1}{4}\cdot 4&=1
\end{align}$$

$P(0)$ is true.

**Inductive hypothesis:**
Let $k\in \mathbb N$ and $k\geq 2$.
Assume that $P(k-1)$ is true.
$$
\begin{aligned}
r(k-1)&=r(k-2)+(k-1)^{3}\\
&=\frac{1}{4}\left((k-1)^{2}(k+1-1)^{2}+4\right)\\
&=\frac{1}{4}\left((k-1)^{2}\cdot k^{2}+4\right)
\end{aligned}
$$
**Goal**
Then we make the claim that
$$ r(k)=\frac{1}{4}\left(k^{2}\cdot(k+1)^{2}+4\right)
$$
**Inductive step**
Then, we rewrite the LH side.
$$
\begin{aligned}
r(k) &=r(k-1)+k^{3}\\
&=r(k)+k^{3}\quad \text {(definition of $r(k+1)$}\\
&=\left [\frac{1}{4}((k-1)^2\cdot k^2+4)\right]+k^3 \quad\text{(Inductive hypothesis)}\\
&= \frac{1}{4}(k^{4} - 2 k^{3} + k^{2}+4)+k^3\\
&= \frac{1}{4}k^{4} - \frac{2}{4}k^{3} + \frac{1}{4}k^{2}+1+k^3\\
&= \frac{1}{4}k^{4} + \frac{2}{4}k^{3} + \frac{1}{4}k^{2}+1\\
&= \frac{1}{4}(k^{4} + 2 k^{3} + k^{2}+4)\\
&=\frac{1}{4}(k^{2}\cdot \left(k + 1\right)^{2}+4)\\
\end{aligned}
$$
It is the same as the RH side, thus proving the equation in our goal.
**Summary**
Since we proved that the base case $P(0)$ is true, and that $P(k)→P(k+1)$ for $k∈\mathbb{N}$, then by the principle of mathematical induction, we can conclude that $P(n)$ is true for all $n∈\mathbb{N}$.

## Exercise 4

Let $a, b \in \mathbb{R}$. Use the iteration method to find a solution to the following recurrence relations.
$$
\begin{array}{c}
t(n)=\left\{\begin{array}{ll}
b & \text { if } n=0 \\
a t(n-1) & \text { if } n \geq 1
\end{array}\right. \\
r(n)=\left\{\begin{array}{ll}
0 & \text { if } n=0 \\
2 r(n-1)+1 & \text { if } n \geq 1
\end{array}\right.
\end{array}
$$
Hint: To solve $r(n)$ you will need that $\sum_{i=0}^{k-1} 2^{i}=1+2+4+\cdots+2^{k-1}=2^{k}-1$ for all $k \in \mathbb{N}$ (you can use this without proof).

---

### 4.1)

We start by backwards substitution, so we expand the recurrence
$$
t(n)=a \cdot t(n-1)
$$
Then
$$
\begin{aligned}
t(n-1)&=a \cdot t(n-2) \\
\end{aligned}$$
So
$$
\begin{aligned}
t(n)&=a \cdot a \cdot t(n-2) \\
t(n)&=a \cdot a \cdot a \cdot t(n-3) \\
t(n)&=a \cdot a \cdot a \cdot a \cdot t(n-4) \\
\end{aligned}
$$
At some point, if we continue to iterate, $t(n-k)$, where k is the number of iterations, will reach our base case $t(0)=b$. Therefore, we see that the closed form of $t(n)$ is
$$t(n)=a^{n} \cdot b$$

Now that we have guessed the pattern, we'll prove it is correct.
**Predicate**
$$P(n)=``at(n-1)=a^n \cdot b"$$

**Base case**
$$t(0)=a^0\cdot b = b $$
So we've proven P(0).

**Inductive hypothesis**
Let $k\in \mathbb N$ where $k\geq0$.
We assume $P(k)$ to be true, so the following is our IH
$$t(k)=a^k \cdot b$$

**Goal**
The claim is that
$$t(k+1)=a^{k+1} \cdot b$$

**Inductive step**

We take the LH side and rewrite it.
$$\begin{aligned}
t(k+1)&=at(k) \quad\left(\text { From the initial conditions }\right)\\
t(k+1)&=a\cdot a^k \cdot b\quad\left(\text { From inductive hypothesis }\right)\\
&=a^{k+1} \cdot b
\end{aligned}$$
It is the same as the RH side, thus proving the equation in our goal.
**Summary**
Since we proved that the base case $P(0)$ is true, and that $P(k)→P(k+1)$ for $k∈\mathbb{N}$, then by the principle of mathematical induction, we can conclude that $P(n)$ is true for all $n∈\mathbb{N}$.

---

### 4.2)
$r(n)=\left\{\begin{array}{ll}
0 & \text { if } n=0 \\
2 r(n-1)+1 & \text { if } n \geq 1
\end{array}\right.$

---

We start by backward substitution:

$$
\begin{aligned}
r(n) &= 2r(n-1)+1\\\
&= 2[2r(n-2)+1]+1\\
&= 2\cdot 2 [2r(n-3)+1]+2+1\\
&= 2\cdot 2 \cdot 2[2r(n-4)+1]+4+2+1\\
&= 2^4r(n-4)+8+4+2+1\
\end{aligned}
$$

Let $k\in \mathbb N$ where $k\geq1$.
So it appears that we can generalize the pattern to:

$$
r(n)=2^kr(n-k)+\sum_{i=0}^{k-1} 2^{i}
$$
And when we reach the base case, r(n-k) becomes 0.
$$
\begin{aligned}
r(n)&=\sum_{i=0}^{k-1} 2^{i}\\
&=1+2+4+8+\cdots+2^{k-1}\\
&=2^{k}-1
\end{aligned}
$$

**Predicate**
$$
\begin{aligned}
P(n)=``r(n)&=2r(n-1)+1, r(0)=0\\
&\Downarrow \\
r(n)&=2^n-1"
\end{aligned}
$$
**Base case**
Since $r(0)=0$ and $2^0-1=0$, $P(0)$ is true.

**Inductive hypothesis**
Let $k\in \mathbb N$ and $k\geq 0$. And assume that:

$$
\begin{aligned}
P(k)=``r(k)&=2r(k-1)+1, r(0)=0\\
&\Downarrow \\
r(k)&=2^k-1"
\end{aligned}
$$

**Goal**
Then we make the claim that
$$ r(k+1)=2^{k+1}-1
$$

**Inductive step**

We make the proof by rewriting LH side to our goal.

$$
\begin{aligned}
r(k+1)&=2r(k)+1\quad \text { (Definition of $r(n)$) }\\
&=2[2^k-1]+1 \quad \text { (Inductive hypothesis) }\\
&=2\cdot2^k-2+1\\
&=2^{k+1}-1
\end{aligned}
$$
It is the same as the RH side, thus proving the equation in our goal.
**Summary**
Since we proved that the base case $P(0)$ is true, and that $P(k)→P(k+1)$ for $k∈\mathbb{N}$, then by the principle of mathematical induction, we can conclude that $P(n)$ is true for all $n∈\mathbb{N}$.

## Exercise 5

Using the Master Theorem, give tight bounds on solutions to the following recurrence relations.

$$
\begin{array}{c}
t(n)=\left\{\begin{array}{ll}
47 & \text { if } n=1 \\
8 t(n / 2)+7 n^{3}+6 n^{2}+5 n+4 & \text { if } n \geq 2
\end{array}\right. \\
r(n)=\left\{\begin{array}{ll}
119 & \text { if } n=1 \\
3 r(n / 5)+n^{2}-4 n+23 & \text { if } n \geq 2
\end{array}\right. \\
s(n)=\left\{\begin{array}{ll}
1 & \text { if } n=1 \\
3 s(n / 2)+3 & \text { if } n \geq 2
\end{array}\right.
\end{array}
$$

---

### 5.1)

We will be using the Master Theorem, as defined in the following.
<div style="background-color: #FFFFAA; padding: 2em; border: solid black;">

**Theorem 8.63 (Master Theorem)**. Let $T(n)$ be a monotomically increasing function satisfying
$$
\begin{array}{l}
T(n)=a T(n / b)+f(n) \\
T(1)=c
\end{array}
$$
where $a \geq 1, b>1$, and $c>0 .$ If $f(n)=\Theta\left(n^{d}\right)$, where $d \geq 0$, then
$$
T(n)=\left\{\begin{array}{ll}
\Theta\left(n^{d}\right) & \text { if } a<b^{d} \\
\Theta\left(n^{d} \log n\right) & \text { if } a=b^{d} \\
\Theta\left(n^{\log _{b} a}\right) & \text { if } a>b^{d}
\end{array}\right.
$$

The *Big O notation*, $\Theta\left(n^{d}\right)$, indicates the highest order of the function.
</div>

Rewritten on the form of Big O notation we get:
$$
\begin{aligned}
t(n)
&=\left\{\begin{array}{ll}
47 & \text { if } n=1 \\
8 t(n / 2)+7 n^{3}+6 n^{2}+5 n+4 & \text { if } n \geq 2
\end{array}\right. \\
&=\left\{\begin{array}{ll}
47 & \text { if } n=1 \\
8 t(n / 2)+\Theta(n^3) & \text { if } n \geq 2
\end{array}\right. \\
\end{aligned}
$$

This means that when we use the master theorem for recurrence we get:

$$
a=8,\quad b=2,\quad c=47,\quad d=3
$$

Since $8=2^3$, we get:
$$a=b^d \Rightarrow \Theta\left(n^{d} \log n\right)$$

Thus, the tight bound describing the function's growth is:

$$\Theta(n^3\log n)$$

### 5.2)

Rewritten on the form of Big O notation we get:
$$
\begin{aligned}
r(n)&=\left\{\begin{array}{ll}
119 & \text { if } n=1 \\
3 r(n / 5)+n^{2}-4 n+23 & \text { if } n \geq 2\\
\end{array}\right. \\
&=\left\{\begin{array}{ll}
119 & \text { if } n=1 \\
3 r(n / 5)+\Theta (n^2) & \text { if } n \geq 2
\end{array}\right. \\
\end{aligned}
$$

$$
a=3,\quad b=5,\quad c=119,\quad d=2
$$

Since $3<5^2$, we get:
$$a=b^d \Rightarrow \Theta\left(n^{d} \right)$$

Thus, the tight bound describing the function's growth is:
$$\Theta\left(n^{2} \right)$$

### 5.3)

Rewritten on the form of Big O notation get:
$$
\begin{aligned}
s(n)&=\left\{\begin{array}{ll}
1 & \text { if } n=1 \\
3 s(n / 2)+3 & \text { if } n \geq 2\\
\end{array}\right. \\
&=\left\{\begin{array}{ll}
1 & \text { if } n=1 \\
3 s(n / 2)+\Theta (1) & \text { if } n \geq 2\\
\end{array}\right. \\
\end{aligned}
$$

$$
a=3,\quad b=2,\quad c=1,\quad d=1
$$

Since $3>2^1$, we get:
$$a>b^d \Rightarrow \Theta\left(n^{\log _{b} a}\right)$$

Thus, the tight bound describing the function's growth is:
$$\Theta\left(n^{\log _{2} 3}\right)$$