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 be the number of ancestors of a male bee of distance . Parents are distance 1, and grandparents are distance 2... etc.
Assume every bee is its own ancestor of distance , so that .
Recall
1.1
Show that , .
Solution
Let be the number of ancestors of a female bee of distance .
First, note the following key observation. For with , and .
By complete induction.
Base cases.. Additionally, .
Inductive step. Let be any natural number at least and suppose for all .
Then, we have as required.
1.2
Prove the following.
Solution
By induction.
Base case. For the base case, we have .
Inductive step. Let be any natural number and assume Then we have
as required.
2 Approximating Square Root of 2
It is useful to approximate irrational numbers using rational numbers. For example, a standard approximation for is . 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 .
Let be the following recurrence.
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 ?
Solution
0, 1, 2, 5, 12, 29, 70, 169, 408, 985
2.2
Find such that , and prove that your choice in is correct.
Hint
Hint: Set up a quadratic equation as we did in lecture 5.
Solution
. Note that is the positive root of the quadratic . Thus .
First, we’ll show .
Base cases. We have and for
Inductive step. Let be an arbitrary integer, and assume for all . We will show that .
Next, we’ll show .
We’ll show that for all ,
Base cases. We have and .
Inductive step. Let be an arbitrary integer, and assume for all . We will show that .
2.3
In the previous problem, you should have found to be the root of some quadratic equation. Let be the other solution to that quadratic. An explicit definition for looks like for some .
Using the base cases of , determine the values of and and hence find an explicit definition for .
Solution
Note . From the assumption, we have so . We also have
Solving the system of linear equations, we find that , and . Thus,
2.4
What is the absolute difference between and to 3 significant figures.
Solution
0.00000212
2.5
Argue informally that is a ‘good’ approximation for , and that the approximation is better as increases.
You don’t need to show this, but it can be shown that this approximation is in some sense optimal!
Solution
Note that is equal to . Which is equal to Since , goes to very fast. So the expression is approximately Note that the larger is, the smaller is, and we get a better approximation.
3 Postage (again)
Recall the postage problem. We showed in lecture that for all , it is possible to make a postage of cents using and cent postage stamps. In this problem, we’ll count the number of ways to make a postage of cents using and cent postage stamps.
Let be the number of ways to make a postage of cents using and cent postage stamps. Formally, let
For define
3.1
Prove by induction that for all . (). You may skip the base case and assume that for .
Hint
Here’s a fact about sets that might be useful:
Solution
First let’s introduce some notation. For any , let . Then .
We will prove by induction that for all .
As instructed in the problem, we will skip the base case and assume that for . (The base case is easy to check)
Inductive Step. Let be an arbitrary integer, and assume that for all , where , . We will show that .
For all , either or (or both). Let and . Then we can write
By the fact in the hint, we have
Then, the idea is that if , then we can remove a cent stamp to get a postage of cents, and if , then we can remove a cent stamp to get a postage of cents. If , then we can remove a cent stamp and a cent stamp to get a postage of cents. Hence , and can be identified with , and respectively. Once this is established, we can write
We’ll show , the other two cases are similar. We define a function as follows: . We will show that is a bijection. First, it is clear that is injective simply by considering the first coordinate. Second, we will show that is surjective. Let . Then . We can write , so . Thus , and is surjective.
3.2 (Optional)
Write a program to check your work in the previous problem. I.e. your program should compute using the recurrence relation, and (e.g. by enumerating all possible pairs ), and check that they are equal for equals, say .
If you’re implementing using the recurrence relation, include the following lines of code directly above the function definition for 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 .
import functools@functools.lru_cache(maxsize=None)def T(n):if8<= n <=14:return1elif n ==15:return2else:return T(n-3) + T(n-5) - T(n-8)import itertoolsdef p(n):returnsum(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 be the function from the previous question. Find a function such that .
Give both an informal explanation of why your choice of is correct, and a formal proof.
Solution
We can show that .
Here’s some informal explanation:
. For each , , there is at most one choice such that . Thus, the number of pairs such that is at most .
. Let’s take a very large such that . Break into groups of cents. Each group can be made using either three cent stamps (type 1) or five cent stamps (type 2). Then I can make with groups of type 1 and groups of type 2, where . Thus, there are ways to make cents. Since , we have . When is not a multiple of , we can apply the same logic to the largest multiple of less than .
The formal proof is by induction and we’ll omit it here since it is similar to other proofs we have seen already.