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

Fib(n)={0n=01n=1Fib(n1)+Fib(n2)n>1

1.1

Show that nN, b(n)=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 nN with n1, b(n)=a(n1) and a(n)=b(n1)+a(n1).

By complete induction.

Base cases. b(0)=1=Fib(1). Additionally, b(1)=1=Fib(2).

Inductive step. Let kN be any natural number at least 1 and suppose b(i)=Fib(i+1) for all ik.

Then, we have b(k+1)=a(k)=a(k1)+b(k1)=b(k)+b(k1)=Fib(k+1)+Fib(k)=Fib(k+2) as required.

1.2

Prove the following. nN. i=0nFib(i)2=Fib(n)Fib(n+1)

Solution

By induction.

Base case. For the base case, we have Fib(0)2=02=0=01=Fib(0)Fib(1).

Inductive step. Let kN be any natural number and assume i=0kFib(i)2=Fib(k)Fib(k+1). Then we have

i=0k+1Fib(i)2=Fib(k+1)2+i=0kFib(i)2=Fib(k+1)2+Fib(k)Fib(k+1)=Fib(k+1)(Fib(k+1)+Fib(k))=Fib(k+1)Fib(k+2) 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 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 2.

Let P(n) be the following recurrence.

P(n)={0n=01n=12P(n1)+P(n2)n>1

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)=Θ(rn), 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+2)2.414. Note that r is the positive root of the quadratic x22x1. Thus r2=2r+1.

First, we’ll show P(n)=O(rn).

Base cases. We have P(0)=0r0 and P(1)=1r1 for

Inductive step. Let k2 be an arbitrary integer, and assume P(i)ri for all i<k. We will show that P(k)rk.

P(k)=2P(k1)+P(k2)2rk1+rk2=(rk2)(2r+1)=(rk2)r2=rk

Next, we’ll show P(n)=Ω(rn).

We’ll show that for all nN1, P(n)0.1rn

Base cases. We have P(1)=10.1r and P(2)=20.1r2.

Inductive step. Let k3 be an arbitrary integer, and assume P(i)0.1ri for all 1i<k. We will show that P(k)0.1rk.

P(k)=2P(k1)+P(k2)20.1rk1+0.1rk2=(0.1rk2)(2r+1)=(0.1rk2)r2=0.1rk

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)=crn+dsn for some c,dR.

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=12. From the assumption, we have P(0)=0=cr0+ds0, so c=d. We also have P(1)=1=c(1+2)+d(12),

Solving the system of linear equations, we find that c=122, and d=122. Thus,

P(n)=(1+2)n(12)n22

2.4

What is the absolute difference between P(9)P(8)P(8) and 2 to 3 significant figures.

Solution 0.00000212

2.5

Argue informally that P(n)P(n1)P(n1) is a ‘good’ approximation for 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 P(n)P(n1)P(n1) is equal to P(n)P(n1)1. Which is equal to (1+2)n+(12)n(1+2)n1+(12)n11 Since |12|<1, (12)n goes to 0 very fast. So the expression is approximately (1+2)n(1+2)n11=1+21=2 Note that the larger n is, the smaller (12)n is, and we get a better approximation.

3 Postage (again)

Recall the postage problem. We showed in lecture that for all n8, 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):aN,bN,3a+5b=n}|

For n8 define T(n)={18n142n=15T(n3)+T(n5)T(n8)n>15

3.1

Prove by induction that for all nN,n8. (p(n)=T(n)). You may skip the base case and assume that p(n)=T(n) for 8n15.

Hint Here’s a fact about sets that might be useful: |AB|=|A|+|B||AB|
Solution

First let’s introduce some notation. For any nN, let An={(a,b):aN,bN,3a+5b=n}. Then p(n)=|An|.

We will prove by induction that p(n)=T(n) for all n8.

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

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

For all (a,b)Ak, either a1 or b1 (or both). Let X={(a,b)Ak:a1} and Y={(a,b)Ak:b1}. Then we can write

Ak=XY

By the fact in the hint, we have |Ak|=|X|+|Y||XY|

Then, the idea is that if (a,b)X, then we can remove a 3 cent stamp to get a postage of k3 cents, and if (a,b)Y, then we can remove a 5 cent stamp to get a postage of k5 cents. If (a,b)XY, then we can remove a 3 cent stamp and a 5 cent stamp to get a postage of k8 cents. Hence X,Y, and XY can be identified with Ak3,Ak5, and Ak8 respectively. Once this is established, we can write p(k)=|Ak|=|X|+|Y||XY|=|Ak3|+|Ak5||Ak8|=T(k3)+T(k5)T(k8)(IH)=T(k).

We’ll show |X|=|Ak3|, the other two cases are similar. We define a function f:XAk3 as follows: f(a,b)=(a1,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)Ak3. Then 3a+5b=k3. We can write 3(a+1)+5b=k, so (a+1,b)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)=Θ(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)=Θ(n).

Here’s some informal explanation:

  • p(n)=O(n). For each b, 0bn5, 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 n5+1=O(n).
  • p(n)=Ω(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 ki groups of type 2, where 0ik. Thus, there are k+1 ways to make n cents. Since k=n15, we have p(n)=Ω(n15)=Ω(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.