Challenge #1 Solution

Read on for the solution to Challenge #1… but give it a try first if you haven’t already!

So let’s find a value for that strange infinite beast from Challenge #1, which is known as an infinite continued fraction.

We’ll start by using a time-tested problem solving technique: NAME AND CONQUER. (In other words, one of the first steps toward getting a handle on a difficult or complex expression is often to simply give it a name.) Let’s call our infinite continued fraction x:

$\displaystyle x = 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \ddots}}}$

And now for the “creative leap” I hinted at in the challenge: notice that if we look only at the expression in the denominator of the first fraction, it looks like this:

$1 + \cfrac{1}{1 + \cfrac{1}{1 + \ddots}}$

But wait a minute! That’s just the same thing as x itself. In other words, x seems to contain entire copies of itself as subparts! Since the denominator of the first fraction is equal to the expression as a whole, we can replace the denominator by x, like this:

$\displaystyle x = 1 + \frac{1}{x}$

You can see why it was so helpful to give our expression a name! Now we can proceed to solve for x. First, we multiply both sides of the equation by x:

$\displaystyle x^2 = x + 1$

Now, moving everything to the left side, we get a quadratic equation which we can solve using the quadratic formula:

$\begin{array}{rcl} x^2 - x - 1 & = & 0 \\ x & = & \frac{1 \pm \sqrt{(-1)^2 - 4(1)(-1)}}{2(1)} \\ x & = & \frac{1 \pm \sqrt{5}}{2} \end{array}$

The positive solution, $\frac{1 + \sqrt{5}}{2} \approx 1.618$ , is the one we want — this is the “value” of the infinite continued fraction. One way to think about this is that if you try various “stopping points” you will see that the values you get seem to be getting closer and closer to 1.618 (more on this later):

$\begin{array}{rcl} 1 & = & 1 \\ 1 + \frac{1}{1} & = & 2 \\ 1 + \cfrac{1}{1 + \cfrac{1}{1}} & = & 1.5 \\ 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1}}} & = & 1.666\dots \end{array}$
and so on. It turns out that this is actually a very famous — and beautiful — number with a special name: the golden ratio, or sometimes the golden mean. It is so special and famous that it has its own special symbol, phi (pronounced “fie”, not “fee”), which looks like this: $\phi$ . (Phi is the twenty-first letter of the Greek alphabet.)

$\displaystyle 1 + \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \ddots}}} = \frac{1 + \sqrt{5}}{2} = \phi = 1.6180339887\dots$

In subsequent posts I’ll explore some of the reasons that the golden ratio is such a beautiful and famous number — it shows up in a lot of different places, some quite unexpected! See Challenge #2 for more infinite expressions to evaluate…

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

7 Responses to Challenge #1 Solution

Dylan says:

October 5, 2006 at 5:31 pm

What problems might arise when you try and determine the 200th term of the fraction?
Ashley says:

September 17, 2007 at 2:54 am

What problems arise when you try to work out the 200th term in the infinite continued fraction used in challenge 1
Brent says:

October 2, 2007 at 2:48 pm

Dylan, Ashley: I’m not entirely sure what you’re asking, but I can try to answer.

Here’s how you can work out successive approximations to the infinite continued fraction. Start with the number 1. Then, at each step, find the reciprocal of the current term, and add 1. If you keep track of this as a fraction, there are no problems; all the arithmetic involves integers. So

1/1 + 1 = 2
1/2 + 1 = 1/2 + 2/2 = 3/2
1/(3/2) + 1 = 2/3 + 3/3 = 5/3
1/(5/3) + 1 = 3/5 + 5/5 = 8/5

and so on. Now, doing this by hand out to the 200th term would be extremely tedious and error-prone. So you would probably write a computer program. You might run into problems here if you use a language with limited-precision integers, since the 200th term expressed as a fraction involves rather large integers. In fact, the 200th term is 734544867157818093234908902110449296423351 over 453973694165307953197296969697410619233826. But if you use a language with arbitrary-precision integers (such as Ruby, Haskell, J, Mathematica, or even Java’s BigInteger class), this is no problem. Another problem would arise if you try to use a floating-point (decimal) data type to compute the 200th term instead of explicit fractions; standard floating-point data types do not have enough precision to show any difference between (say) the 199th and 200th terms.
Brian says:

November 19, 2007 at 12:13 am

For all you guys obviously working on your IB portfolios:
I think that all the teacher wants to know about the 200th term is that you understand the continued fraction has no decimal or fractal equivalent, at least not using real numbers (Hint!). All I said is that by the time one calculates the 200th term, it’s obvious the value won’t solidify and therefore it must be expressed in another fashion. This assumption is further evidenced by the fact the next question asks you to find an exact value for the fraction.
rongrong says:

January 21, 2008 at 11:32 pm

i dont really get what you meant bythe continued fraction no decimal or fractal equivlen. and why the value will not solidfy and how can it e expressed in another fashion?
Pingback: Challenge #2 Solution « The Math Less Traveled
Pingback: Challenge #5 Solution « The Math Less Traveled