MTH1030/MTH1035: Project 2, 2025

From counting the number of banana trees (again!) to calculating the digits of π

The same rules as for Project 1 apply! Also, as with Project 1, we will begin work on each of the four parts of this project during the seminars. You will then complete the remaining puzzles at home and write up your solutions in your own words. As always, perform. all calculations using Mathematica.

1 Banana trees vs. tree bananas (25 Marks)

Remember the strange bananas from Project 1? Instead of growing on trees, there are trees growing in these bananas! As you showed in Project 1, just like the Fibonacci sequence, the banana tree number sequence

b2 = 3, b3 = 8, b4 = 21, b5 = 55, . . .

satisfies a simple recursion relation.

a) (15 marks) Using this recursion relation, replicate all the steps in Part 4 of the Week 6 lesson quiz (the Fibonacci interlude) to calculate and explain a closed-form. counterpart of Binet’s formula for the banana tree numbers! In other words, derive an elementary function B such that

bn = B(n),

for n = 2, 3, 4, . . ..

b) (5 marks) Find two numbers, e and f, such that bn is always equal to e f n rounded to the nearest integer. Justify your choice of numbers.

c) (5 marks) Use Binet’s formula and the formula you derived in part (a) to prove that

bn = f2n,

where fn is the nth Fibonacci number.

2 Ranking the Arcane Manuscripts (25 marks)

In the mystical realm of Arcanum, ancient manuscripts hold the secrets of untold power and wisdom. The royal archivists have discovered that these manuscripts, much like modern webpages, are interlinked by enchanted sigils (hyperlink references) that determine their prominence within the vast Library of Shadows. In a miniature model of this magical network, there are eight manuscripts.

An arrow from manuscript. j to manuscript. i indicates that manuscript. j cites or refers to manuscript. i. Part of the entrance exam for junior archivists is to rank these manuscripts; that is, to determine which is the most prominent, which is the second most prominent, and so on—thus proving one’s mastery over the arcane ranking arts.

The art of ranking these manuscripts involves magical mathematics based on the following principles:

1. The more manuscripts that reference a given manuscript, the higher its rank should be.

2. A reference coming from a manuscript. of low renown should contribute less to the rank than one from a manuscript. of high renown.

3. A manuscript. that cites many others should contribute less to the rank of those it references than a manuscript. that cites only a few.

We begin by encoding our miniature enchanted network in the form. of an adjacency matrix A. In this matrix, if manuscript. i is referenced by manuscript. j, then the (i, j)th entry is 1; otherwise, it is 0. Since there are eight manuscripts, A is an 8 × 8 matrix.

(a) (5 marks)

Below is a partially completed version of the adjacency matrix:

Complete this matrix.

(Hint: Verify your answer carefully—everything else that follows depends on you getting this matrix right.)

(b) (4 marks)

Again, the first principle says:“The more manuscripts that reference a given manuscript, the higher its rank should be.” The numbers of times that manuscript. i is referenced are given by the entries in the ith row of A. Therefore, if we just use this first principle and neglect the other two, it would make sense to define the rank of manuscript. i to be:

Let r be the vector whose ith entry is ri . We can then express these equations in matrix form. as

r = As.

Calculate r and, based on it, propose a first, rough ranking for the eight manuscripts. Find the vector s such that this matrix equation holds.

(c) (4 marks)

The second principle refines our ranking: a reference from a low-ranked manuscript. should count less. Thus, taking into account both the first and second principle, we refine the ranking definition to:

In matrix notation, this becomes

r = Ar.

This equation implies that r is an eigenvector of A with eigenvalue 1. However, for this to make sense it is necessary that A indeed has 1 as one of its eigenvalues.

Check this by calculating the eigenvalues of A and recording them in your answer.

Although the result you obtain may seem discouraging, the quest continues.

(d) (4 marks)

The third property further refines the ranking: a manuscript. with many citations should contribute less influence per citation than one with fewer citations. To incorporate this third property into our ranking calculations we have to adjust the matrix A.

The number of manuscripts that manuscript. i cites is just the sum of the entries in the ith column of A. To ensure that manuscripts with numerous citations contribute less per link, we normalize the matrix A by dividing each entry in column i by the sum of the entries in this column. This yields a new matrix D.

Calculate the matrix D.

(Check that the determinant of your D is −144/1 before proceeding.)

(e) (4 marks)

We arrive at our final ranking by replacing A with D in our last ranking formala, leading to:

or equivalently,

r = Dr.

Thus, r is now an eigenvector of D corresponding to the eigenvalue 1. Since D is a so-called Markov matrix, we are guaranteed that 1 is an eigenvalue and that there exists a unique eigenvector (up to scaling) with nonnegative entries.

So, find all eigenvalues of D and determine an eigenvector corresponding to the eigenvalue 1 whose entries sum to 1. Use this eigenvector to rank the manuscripts in our mini enchanted network.

(f) (4 marks)

Finally, envision replacing our mini enchanted network with the vast, sprawling Web of Wisdom—the World Wide Web itself. Although the same mathematical principles apply, additional challenges emerge when scaling up to such an immense network.

Re-examine part d) and identify one problem that is bound to occur and that will (at least to start with) get in the way of constructing the matrix D. Can you think of an additional potential problem that may arise when we try to unleash our ranking strategy on other webs of wisdom? Hint: Have another close look at part e). 

Final Remarks

1. The challenges identified in part (f) can be surmounted with relatively straightforward modifications.

2. There are two insightful interpretations of the Markov process underlying D. One interpretation envisions countless seekers of knowledge, each randomly traversing the labyrinthine Web; after a long time, the distribution of these seekers approximates our final ranking vector. The other views it as a solitary wanderer whose long-term visitation frequencies reflect the relative importance of each manuscript.

3. Techniques similar to those described here are also employed to generate rankings in other domains, such as competitive sports.

3 Cursed L’Hˆopitals (15 marks)

Deep within the hallowed halls of the Arcane University of Arcanum, the great wizards debate the mysteries of limits and indeterminate forms.

a) (5 marks) One such enigma is the notorious  form—a riddle that appears when we ponder f(x) g(x) where f(x) is a function that dwindles to 0 as x approaches a mysterious point a, while a companion function g(x) soars unboundedly to infinity. In precise terms, we examine the limit

with the following properties:

1.  f(x) = 0;

2.  g(x) = ∞;

3. 0 ≤ f(x) (and, strictly speaking, f(x) > 0 for all x sufficiently near a for which g(x) is defined) so that the power is always meaningful.

The ancient scrolls ask: Is 0∞ truly an indeterminate form? If you believe it is, conjure up dif-ferent functions f(x) and g(x) (satisfying properties 1–3) for which the limit limx→a f(x) g(x) takes on different values. Otherwise, provide a convincing argument that 0∞ is not indeter-minate in this context.

b) (5 marks) The sages have also uncovered a curious incantation:

You don’t have to show this! To test your numerical magic, approximate this limit by substituting x = 0.1, 0.01, 0.001, . . . , 10−10 into the expression

First, use your favored Arcane Spell Calculator (ASC), then confirm your results with Math-ematica. Record your findings in a table and explain the value of this numerical experiment for any budding Arcanum mathematician.

c) (5 marks)

is an indeterminate form. of type . Show that applying l’Hˆopital’s rule to this indeterminate form. by differentiating both numerator and denominator does not help with finding this limit. Does the limit exist regardless, and if so what is it?

May your computations be ever precise, and may the wisdom of L’Hˆopital illuminate your path!

4 Calculating the Sacred Digits of π (35 marks)

In the ancient realm of Arcanum, the value of π is more than a mere number—it is a key to unlocking the deepest secrets of magic and the universe. The wise mages have long known that approximating such elusive constants as π, e, or sin(1) requires both mathematical prowess and mystical insight. The very devices that compute these values, from enchanted calculators to the great spellbooks of Mathematica, are built upon these arcane principles.

One of the most wondrous incantations for expressing π is the Leibniz formula, attributed to the legendary sage Gottfried Wilhelm Leibniz (though its origins reach even further back into the lore of Madhava of Sangamagrama). The spell is given by:

Alas, this series converges as slowly as a snail trudging through enchanted marshes. Let the following tasks guide you through the mystical challenge of finding miraculously good approximations of π using infinite series.

a) (5 marks) Let an and Sn denote the nth term and the nth partial sum of the Leibniz series, respectively. Just in case you are wondering: a1 = 4. Your first task is to determine the smallest integer n such that

|π − Sn| < 0.0001.

To do so, you should derive an expression for an, write Sn using the Mathematica command Sum, and employ trial and error to pinpoint the smallest such n.

As you will see, you need to add thousands of terms of the series to get an approximation of π as good as 3.1415. That’s pretty terrible!!!

In 1706 the first 100 digits of π were calculated for the first time. Let’s say you are the crazy person who got it into their head to perform. this incredible task at that time and you want to use the Leibniz series for this task. Of course you know that by adding up enough terms of our series you will eventually achieve your aim, but how many terms will it take? And isn’t there some way to accelerate the convergence of this “snail” series?

As we have seen, without already knowing the sum of a convergent infinite series it is usually quite tricky to figure out how many terms need to be added to be able to guarantee that the partial sum generated like this coincides with the true sum in a given large number of digits. However, for certain series like, for example, the Leibniz series it is a very easy to get a pretty good estimate as follows.

As you can easily check the Leibniz series has the following two properties:

1. The terms alternate between being positive and negative numbers. This makes our series into an alternating series;

2. the absolute values of the terms are decreasing;

3. the terms have the limit 0.

Now it is quite easy to show (you don’t have to do this) that any series that has these three properties has a finite sum, let’s call it S, and that

|S − Sn| < |an+1|.

This result is known as the alternating series remainder estimate.

b) (5 marks) Find the smallest m such that

|am+1| < 0.0001

in the case of the Leibniz series.

The alternating series remainder estimate guarantees that for the m you just found |π −Sm| is also less than 0.0001. Now the m you found here is larger than the precise figure n that we found in a) and so is less useful. However, unlike n which was only accessible using Mathematica and using a good approximation of the true value of π built into Mathematica (we were using what we want to find which is cheating!), it is trivial to calculate m even without a computer. Also m gives you a good enough idea about what magnitude problem you are facing.

Both results of a) and b) tell you that the straightforward approach of simply adding more and more terms of our series (by hand) will not get you the first 100 digits of π within your life-time. Luckily you have a really smart idea.

From calculus we know that the Leibniz formula results when we set x = 1 in the Maclaurin series

Substituting any positive number x < 1 into this identity will result in an alternating series on the right that converges much much faster than the one for x = 1 because of those powers of x becoming very tiny very quickly.

Now the idea is to express π/4 in terms of a few numbers of the form. tan−1 (A) and then com-bine the corresponding series into a rapidly converging series that can be used to approximate π much more efficiently than if we used the Leibniz series.

Okay, here we go.

c) (10 marks) Let α = tan−1 (1/5). Using the addition formula

show that

Show that the last equation implies

or

d) (5 marks) Using Mathematica calculate an approximation of π by substituting the 3rd partial sums of the series corresponding to tan−1 (1/5) and tan−1 (1/239) for these numbers in the expression on the right. How many correct digits of π do you get this way (counting the 3 at the start as the first digit)?

Pretty spectacular, right?

e) (5 marks) Now for the real (1706) deal. Estimate using the alternating series remainder estimate how many terms of the two series you will need to add to calculate those precious first 100 digits of π. In doing so keep the following in mind. The series for tan−1 (1/239) converges much, much faster than that for tan−1 (1/5). This means that to guarantee 100 digits of π using this approach we want to find an n as small as possible such that (n + 1)st term of the series for 16 tan−1 (1/5) is less than 10−102. We use 10−102 instead of 10−100 just to be reasonably certain that carries won’t mess up things.

Your answers to parts a) through e) will demonstrate whether the ancient incantations are potent enough to reveal the hidden, sacred digits of π—a key that unlocks the treasure trove of infinite wisdom in Arcanum.