Recurrences
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{cases} 0 & n = 0 \\ 1 & n = 1 \\ \mathrm{Fib}(n-1) + \mathrm{Fib}(n-2) & n > 1 \end{cases} \]
Show that \(\forall n \in \mathbb{N}\), \(b(n) = \mathrm{Fib}(n+1)\).
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 \geq 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 \leq k\).
Then, we have \[ \begin{aligned} 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{aligned} \] as required.Prove the following. \(\forall n \in \mathbb{N}.\) \[\sum_{i=0}^n \mathrm{Fib}(i)^2 = \mathrm{Fib}(n) \cdot \mathrm{Fib}(n+1)\]
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{aligned} \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{aligned} \] as required.
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{cases} 0 & n=0 \\ 1 & n=1 \\ 2P(n-1) + P(n-2) & n>1 \end{cases} \]
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.
What are \(P(0), P(1),...,P(9)\)?
Find \(r\) such that \(P(n) = \Theta(r^n)\), and prove that your choice in \(r\) is correct.
\(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 \leq r^0\) and \(P(1) = 1 \leq r^1\) for
Inductive step. Let \(k \geq 2\) be an arbitrary integer, and assume \(P(i) \leq r^i\) for all \(i < k\). We will show that \(P(k) \leq r^k\).
\[ \begin{aligned} P(k) & = 2P(k-1) + P(k-2) \\ & \leq 2r^{k-1} + r^{k-2} \\ & = (r^{k-2})(2r + 1) \\ & = (r^{k-2})r^2 \\ & = r^k \\ \end{aligned} \]
Next, we’ll show \(P(n) = \Omega(r^n)\).
We’ll show that for all \(n \in \mathbb{N} \geq 1\), \(P(n) \geq 0.1r^n\)
Base cases. We have \(P(1) = 1 \geq 0.1r\) and \(P(2) = 2 \geq 0.1r^2\).
Inductive step. Let \(k \geq 3\) be an arbitrary integer, and assume \(P(i) \geq 0.1r^i\) for all \(1 \leq i < k\). We will show that \(P(k) \geq 0.1r^k\).
\[ \begin{aligned} P(k) & = 2P(k-1) + P(k-2) \\ & \geq 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{aligned} \]
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) = cr^n + ds^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)\).
Note \(s = 1 - \sqrt{2}\). From the assumption, we have \[P(0) = 0 = cr^0 + ds^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}}\]
What is the absolute difference between \(\frac{P(9) - P(8)}{P(8)}\) and \(\sqrt{2}\) to 3 significant figures.
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!
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.
Recall the postage problem. We showed in lecture that for all \(n \geq 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 \geq 8\) define \[ T(n) = \begin{cases} 1 & 8 \leq n \leq 14 \\ 2 & n = 15 \\ T(n-3) + T(n-5) - T(n-8) & n > 15 \end{cases} \]
Prove by induction that for all \(n \in \mathbb{N}, n \geq 8\). (\(p(n) = T(n)\)). You may skip the base case and assume that \(p(n) = T(n)\) for \(8 \leq n \leq 15\).
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 \geq 8\).
As instructed in the problem, we will skip the base case and assume that \(p(n) = T(n)\) for \(8 \leq n \leq 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 \leq i < k\), \(p(i) = T(i)\). We will show that \(p(k) = T(k)\).
For all \((a, b) \in A_k\), either \(a \geq 1\) or \(b \geq 1\) (or both). Let \(X = \{(a, b) \in A_k : a \geq 1\}\) and \(Y = \{(a, b) \in A_k : b \geq 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{aligned} 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{aligned} \]
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.
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\).
Something like this works.
Let \(p(n)\) be the function from the previous question. Find a function \(f(n)\) such that \(p(n) = \Theta(f(n))\).
Give both an informal explanation of why your choice of \(f(n)\) is correct, and a formal proof.
We can show that \(p(n) = \Theta(n)\).
Here’s some informal explanation:
The formal proof is by induction and we’ll omit it here since it is similar to other proofs we have seen already.