Problem Set 5

Recurrences

1 Fibeenaci

An unfertilized bee egg becomes a male bee, whereas a fertilized bee egg becomes a female bee.

Thus, female bees have a biological mother and a biological father, whereas male bees only have a biological mother.

Let $b(n)$ be the number of ancestors of a male bee of distance $n$. Parents are distance 1, and grandparents are distance 2... etc.

Assume every bee is its own ancestor of distance $0$, so that $b(0)=1$.

Recall

$$\mathrm{Fib}(n)=\{\begin{array}{ll}0& n=0\\ 1& n=1\\ \mathrm{Fib}(n-1)+\mathrm{Fib}(n-2)& n>1\end{array}$$

1.1

Show that $\mathrm{\forall }n\in \mathbb{N}$, $b(n)=\mathrm{Fib}(n+1)$.

Solution

Let $a(n)$ be the number of ancestors of a female bee of distance $n$.

First, note the following key observation. For $n\in \mathbb{N}$ with $n\ge 1$, $b(n)=a(n-1)$ and $a(n)=b(n-1)+a(n-1)$.

By complete induction.

Base cases. $b(0)=1=\mathrm{Fib}(1)$. Additionally, $b(1)=1=\mathrm{Fib}(2)$.

Inductive step. Let $k\in \mathbb{N}$ be any natural number at least $1$ and suppose $b(i)=\mathrm{Fib}(i+1)$ for all $i\le k$.

Then, we have $$\begin{array}{rl}b(k+1)& =a(k)\\ & =a(k-1)+b(k-1)\\ & =b(k)+b(k-1)\\ & =\mathrm{Fib}(k+1)+\mathrm{Fib}(k)\\ & =\mathrm{Fib}(k+2)\end{array}$$ as required.

1.2

Prove the following. $\mathrm{\forall }n\in \mathbb{N}.$ $$\sum _{i=0}^n\mathrm{Fib}(i{)}^2=\mathrm{Fib}(n)\cdot \mathrm{Fib}(n+1)$$

Solution

By induction.

Base case. For the base case, we have $\mathrm{Fib}(0{)}^2=0^2=0=0\cdot 1=\mathrm{Fib}(0)\cdot \mathrm{Fib}(1)$.

Inductive step. Let $k\in \mathbb{N}$ be any natural number and assume $\sum _{i=0}^k\mathrm{Fib}(i{)}^2=\mathrm{Fib}(k)\cdot \mathrm{Fib}(k+1).$ Then we have

$$\begin{array}{rl}\sum _{i=0}^{k+1}\mathrm{Fib}(i{)}^2& =\mathrm{Fib}(k+1{)}^2+\sum _{i=0}^k\mathrm{Fib}(i{)}^2\\ & =\mathrm{Fib}(k+1{)}^2+\mathrm{Fib}(k)\cdot \mathrm{Fib}(k+1)\\ & =\mathrm{Fib}(k+1)(\mathrm{Fib}(k+1)+\mathrm{Fib}(k))\\ & =\mathrm{Fib}(k+1)\cdot \mathrm{Fib}(k+2)\end{array}$$ as required.

2 Approximating Square Root of 2

It is useful to approximate irrational numbers using rational numbers. For example, a standard approximation for $\pi$ is $22/7$. For more on this interesting topic, check out this video from Numberphile (optional). In this problem, we’ll use a recurrence to find some approximations for $\sqrt{2}$.

Let $P(n)$ be the following recurrence.

$$P(n)=\{\begin{array}{ll}0& n=0\\ 1& n=1\\ 2P(n-1)+P(n-2)& n>1\end{array}$$

Note. It is important here that you do the problems in order. For example, you may not use the result of the third subpart in your solution to the second subpart.

2.1

What are $P(0),P(1),...,P(9)$?

Solution

0, 1, 2, 5, 12, 29, 70, 169, 408, 985

2.2

Find $r$ such that $P(n)=\mathrm{\Theta }(r^n)$, and prove that your choice in $r$ is correct.

Hint

Hint: Set up a quadratic equation as we did in lecture 5.

Solution

$r=(1+\sqrt{2})\approx 2.414$. Note that $r$ is the positive root of the quadratic $x^2-2x-1$. Thus $r^2=2r+1$.

First, we’ll show $P(n)=O(r^n)$.

Base cases. We have $P(0)=0\le r^0$ and $P(1)=1\le r^1$ for

Inductive step. Let $k\ge 2$ be an arbitrary integer, and assume $P(i)\le r^i$ for all $i<k$. We will show that $P(k)\le r^k$.

$$\begin{array}{rl}P(k)& =2P(k-1)+P(k-2)\\ & \le 2r^{k-1}+r^{k-2}\\ & =(r^{k-2})(2r+1)\\ & =(r^{k-2})r^2\\ & =r^k\end{array}$$

Next, we’ll show $P(n)=\mathrm{\Omega }(r^n)$.

We’ll show that for all $n\in \mathbb{N}\ge 1$, $P(n)\ge 0.1r^n$

Base cases. We have $P(1)=1\ge 0.1r$ and $P(2)=2\ge 0.1r^2$.

Inductive step. Let $k\ge 3$ be an arbitrary integer, and assume $P(i)\ge 0.1r^i$ for all $1\le i<k$. We will show that $P(k)\ge 0.1r^k$.

$$\begin{array}{rl}P(k)& =2P(k-1)+P(k-2)\\ & \ge 2\cdot 0.1r^{k-1}+0.1r^{k-2}\\ & =(0.1r^{k-2})(2r+1)\\ & =(0.1r^{k-2})r^2\\ & =0.1r^k\end{array}$$

2.3

In the previous problem, you should have found $r$ to be the root of some quadratic equation. Let $s$ be the other solution to that quadratic. An explicit definition for $P(n)$ looks like $P(n)=c{r}^n+d{s}^n$ for some $c,d\in \mathbb{R}$.

Using the base cases of $P(n)$, determine the values of $c$ and $d$ and hence find an explicit definition for $P(n)$.

Solution

Note $s=1-\sqrt{2}$. From the assumption, we have $$P(0)=0=c{r}^0+d{s}^0,$$ so $c=-d$. We also have $$P(1)=1=c(1+\sqrt{2})+d(1-\sqrt{2}),$$

Solving the system of linear equations, we find that $c=\frac{1}{2\sqrt{2}}$, and $d=-\frac{1}{2\sqrt{2}}$. Thus,

$$P(n)=\frac{(1+\sqrt{2}{)}^n-(1-\sqrt{2}{)}^n}{2\sqrt{2}}$$

2.4

What is the absolute difference between $\frac{P(9)-P(8)}{P(8)}$ and $\sqrt{2}$ to 3 significant figures.

Solution

0.00000212

2.5

Argue informally that $\frac{P(n)-P(n-1)}{P(n-1)}$ is a ‘good’ approximation for $\sqrt{2}$, and that the approximation is better as $n$ increases.

You don’t need to show this, but it can be shown that this approximation is in some sense optimal!

Solution

Note that $\frac{P(n)-P(n-1)}{P(n-1)}$ is equal to $\frac{P(n)}{P(n-1)}-1$. Which is equal to $$\frac{(1+\sqrt{2}{)}^n+(1-\sqrt{2}{)}^n}{(1+\sqrt{2}{)}^{n-1}+(1-\sqrt{2}{)}^{n-1}}-1$$ Since $|1-\sqrt{2}|<1$, $(1-\sqrt{2}{)}^n$ goes to $0$ very fast. So the expression is approximately $$\frac{(1+\sqrt{2}{)}^n}{(1+\sqrt{2}{)}^{n-1}}-1=1+\sqrt{2}-1=\sqrt{2}$$ Note that the larger $n$ is, the smaller $(1-\sqrt{2}{)}^n$ is, and we get a better approximation.

3 Postage (again)

Recall the postage problem. We showed in lecture that for all $n\ge 8$, it is possible to make a postage of $n$ cents using $3$ and $5$ cent postage stamps. In this problem, we’ll count the number of ways to make a postage of $n$ cents using $3$ and $5$ cent postage stamps.

Let $p(n)$ be the number of ways to make a postage of $n$ cents using $3$ and $5$ cent postage stamps. Formally, let $$p(n)=|\{(a,b):a\in \mathbb{N},b\in \mathbb{N},3a+5b=n\}|$$

For $n\ge 8$ define $$T(n)=\{\begin{array}{ll}1& 8\le n\le 14\\ 2& n=15\\ T(n-3)+T(n-5)-T(n-8)& n>15\end{array}$$

3.1

Prove by induction that for all $n\in \mathbb{N},n\ge 8$. ($p(n)=T(n)$). You may skip the base case and assume that $p(n)=T(n)$ for $8\le n\le 15$.

Hint

Here’s a fact about sets that might be useful: $|A\cup B|=|A|+|B|-|A\cap B|$

Solution

First let’s introduce some notation. For any $n\in \mathbb{N}$, let $A_n=\{(a,b):a\in \mathbb{N},b\in \mathbb{N},3a+5b=n\}$. Then $p(n)=|A_n|$.

We will prove by induction that $p(n)=T(n)$ for all $n\ge 8$.

As instructed in the problem, we will skip the base case and assume that $p(n)=T(n)$ for $8\le n\le 15$. (The base case is easy to check)

Inductive Step. Let $k>15$ be an arbitrary integer, and assume that for all $i$, where $8\le i<k$, $p(i)=T(i)$. We will show that $p(k)=T(k)$.

For all $(a,b)\in A_k$, either $a\ge 1$ or $b\ge 1$ (or both). Let $X=\{(a,b)\in A_k:a\ge 1\}$ and $Y=\{(a,b)\in A_k:b\ge 1\}$. Then we can write

$$A_k=X\cup Y$$

By the fact in the hint, we have $$|A_k|=|X|+|Y|-|X\cap Y|$$

Then, the idea is that if $(a,b)\in X$, then we can remove a $3$ cent stamp to get a postage of $k-3$ cents, and if $(a,b)\in Y$, then we can remove a $5$ cent stamp to get a postage of $k-5$ cents. If $(a,b)\in X\cap Y$, then we can remove a $3$ cent stamp and a $5$ cent stamp to get a postage of $k-8$ cents. Hence $X,Y$, and $X\cap Y$ can be identified with $A_{k-3},A_{k-5}$, and $A_{k-8}$ respectively. Once this is established, we can write $$\begin{array}{rl}p(k)& =|A_k|\\ & =|X|+|Y|-|X\cap Y|\\ & =|A_{k-3}|+|A_{k-5}|-|A_{k-8}|\\ & =T(k-3)+T(k-5)-T(k-8)& \text{(IH)}\\ & =T(k).\end{array}$$

We’ll show $|X|=|A_{k-3}|$, the other two cases are similar. We define a function $f:X\to A_{k-3}$ as follows: $f(a,b)=(a-1,b)$. We will show that $f$ is a bijection. First, it is clear that $f$ is injective simply by considering the first coordinate. Second, we will show that $f$ is surjective. Let $(a,b)\in A_{k-3}$. Then $3a+5b=k-3$. We can write $3(a+1)+5b=k$, so $(a+1,b)\in X$. Thus $f(a+1,b)=(a,b)$, and $f$ is surjective.

3.2 (Optional)

Write a program to check your work in the previous problem. I.e. your program should compute $T(n)$ using the recurrence relation, and $p(n)$ (e.g. by enumerating all possible pairs $(a,b)$), and check that they are equal for $n$ equals, say $500$.

If you’re implementing $T(n)$ using the recurrence relation, include the following lines of code directly above the function definition for $T(n)$ to ensure that the function is memoized (i.e. it does not recompute values it has already computed). This will make your program run much faster, especially for larger values of $n$.

import functools
@functools.lru_cache(maxsize=None)

Solution

Something like this works.

import functools
@functools.lru_cache(maxsize=None)
def T(n):
    if 8 <= n <= 14:
        return 1
    elif n == 15:
        return 2
    else:
        return T(n-3) + T(n-5) - T(n-8)
    
import itertools
def p(n):
    return sum(map(lambda x: 3*x[0] + 5*x[1] == n, itertools.product(range(n), repeat=2)))

print(T(500))
print(p(500))

34
34

3.3

Let $p(n)$ be the function from the previous question. Find a function $f(n)$ such that $p(n)=\mathrm{\Theta }(f(n))$.

Give both an informal explanation of why your choice of $f(n)$ is correct, and a formal proof.

Solution

We can show that $p(n)=\mathrm{\Theta }(n)$.

Here’s some informal explanation:

• $p(n)=O(n)$. For each $b$, $0\le b\le \frac{n}{5}$, there is at most one choice $a$ such that $3a+5b=n$. Thus, the number of pairs $(a,b)$ such that $3a+5b=n$ is at most $\frac{n}{5}+1=O(n)$.
• $p(n)=\mathrm{\Omega }(n)$. Let’s take a very large $n$ such that $n=15k$. Break $n$ into groups of $15$ cents. Each group can be made using either three $5$ cent stamps (type 1) or five $3$ cent stamps (type 2). Then I can make $n$ with $i$ groups of type 1 and $k-i$ groups of type 2, where $0\le i\le k$. Thus, there are $k+1$ ways to make $n$ cents. Since $k=\frac{n}{15}$, we have $p(n)=\mathrm{\Omega }(\frac{n}{15})=\mathrm{\Omega }(n)$. When $n$ is not a multiple of $15$, we can apply the same logic to the largest multiple of $15$ less than $n$.

The formal proof is by induction and we’ll omit it here since it is similar to other proofs we have seen already.