UH
Module 6
Chapters 10 and 11
Continued Fractions and Fibonacci numbers.
Continued Fractions
A continued fraction is a way to represent numbers that are improper fractions or, in some cases, transcendental numbers. A continued fraction takes a whole LOT of room on a page so we quickly move to an alternate representation.
For example:
[pic]
Improper fraction (fully reduced); continued fraction; decimal; mixed number
Each of these representations has its uses!
The continued fraction is called “finite and simple” because it ends and each numerator is 1. There are 2 fraction bars in the continued fraction of the number.
Now, proper fractions do not have a continued fraction representation – only mixed number and improper fractions.
0.25 = [pic] no chance for a continued fraction here!
Note that we use the Euclidean Algorithm as a way to get the CF for an improper fraction!
[pic]
There is a second way to get CFs
[pic]
Both ways are similar. You really do need a fully reduced fraction to do this work –
(numerator, denominator) = 1.
Another example: [pic]
[pic]
Simple finite continued fraction!
Another one:
[pic]
Four fraction bars! Simple finite continued fraction.
Popper 11, Question 1
Every fraction can be represented as a continued fraction.
A True
B False
Continued fractions and Diophantine equations
Here’s a surprising tie in between continued fractions and Diophantine equations!
Here’s an example that is not in the book – it’s the same process, though.
Step 1 Get the continued fraction
Step 2 Chop off the last fraction
Step 3 Reconstitute a new improper fraction
Step 4 Subtract the new fraction from the original one
Step 5 Multiply and subtract the numerators getting an equation
Step 5 Multiply both sides of the equation by the common denominator
Take [pic]
Notice that I always use a prime number in my improper fractions – it’s a guaranteed way to make sure the fraction is fully reduced!
The CF work - Step 1:
[pic]
[pic]
Step 2: chop of the ½:
[pic]
Step 3 Reconstitute the new improper fraction:
[pic]
Step 4 Subtract the new fraction from the original one
[pic]
Step 5 Multiply and subtract the numerators getting an equation
[pic]
Step 5 Multiply both sides of the equation by the common denominator
[pic]
Which is: [pic]
Now look at it hard:
[pic]
There’s a Diophantine equation! With the initial solution showing!
Popper 11, Question 2
Diophantine Equations have continued fractions as solutions.
A True
B False
Now for infinite repeating continued fractions
All irrationals of the form [pic] have infinite repeating continued fractions.
We’ll definitely need new notation for this!
Example [pic] is a nonrepeating, nonterminating decimal…no place to put a repeat superscripted bar…
[pic]
How cool is that? A nice compact and REPEATING representation?
The square root of 10 has period 1.
Example [pic]
Period 2
Other common notation:
[pic]
Example: [pic] period 6
Popper 11, Question 3
[pic] has period
A 3
B 4
We’ll explore only one theorem on how to find these. There has been a LOT of work done and lots is known.
Theorem on page 127
If an irrational number has the form [pic] where a is a natural number, then its continued fraction is [pic]
Let’s illustrate this theorem!
a = 1 [pic]
Will this work for [pic]
a = 3 [pic]
a = 4 [pic]
nope!
Let’s check the theorem:
5 = [pic]
From a calculator: [pic]
From the theorem: [pic]
2 + ¼ = 2.25
[pic] = 2.2352941
…
2 + 6 fraction bars = 2.2360648
Take a limit to inifinty…sure!
Popper 11, Question 3
[pic]
A True
B False
Now let’s take a minute and look at continued fractions from a set perspective
Reals
Algebraic:
Rationals (finite simple cf) and some irrationals (infinite repeating cf)
Transcendental:
Some have cf but they’re definitely not simple!
Example for a transcendental number:
[pic]
The nice thing is that you can see the pattern. The problem is that it’s not a repeating pattern so there’s nowhere for a repeat bar.
This is an infinite complicated continued fraction!
Example e, the Euler number
e is irrational and approximately 3.7, non-terminating and non-repeating…
It shows up in lots of natural phenomena and in continuously compounded interest in man-made phenomena.
It has an infinite complicated continued fraction with a visible pattern:
[pic]
Again, no place for a repeat bar…
But for the first time there’s a pattern to see with some of these irrational numbers!
Popper 11, Question 5
Only algebraic numbers have continued fraction representations.
A True
B False
Homework hint: Google Continued Fraction for homework help!
End video 1
Chapter 11: Fibonacci Numbers
Pages 133 – 144
Fibonacci was an Italian mathematician. He discovered a sequence of natural numbers created by addition that shows up frequently in natural phenomena. If you google the topic, you’ll get millions of hits. There is even a Fibonacci Society!
The sequence:
[pic]
[pic]
Why 3? Well if you try it with n = 1, you get [pic] and that’s not ok.
Side note: on the final you’ll have a calculator, a list of primes, and a list of
Fibonacci numbers on links. If you don’t see the links, get some help
from the proctors!
Now let’s look at n = 10 [pic] so we really need a list of these to do things!
Popper 12, Question 1
Given [pic] what is [pic]?
[pic]
Now let’s work with our formula a little bit:
[pic]
The second equation is used almost as much as the first equation so be comfy with either, please.
Popper 12, Question 2
[pic]
A 322
B [pic]
C [pic]
D [pic]
E 12
Let’s take a really nice continued fraction and see where it leads us:
[pic] it doesn’t get simpler than this one…
[pic]
Does this one converge to a number?
1 1/1 [pic] 1
1 + 1 2/1 [pic] 2
[pic] 3/2 [pic] 1.5
[pic] 5/3 [pic] 1.6
… 1.625
… 1.618
… non-terminating and non-repeating decimal [pic]
Which, after some algebra turns out to be
[pic]
Let’s look at that algebra (page 133)
[pic] If I drop below the first fraction bar, notice that I’ve got x again
[pic] incredible but true
Now, multiply both sides by x which we know is NOT zero!
And then subtract to get a quadratic = 0
[pic]
Now let’s use the quadratic formula with A = 1, B = −1, and C = −1.
[pic]
And we ignore the negative answer because it’s a negative number and not the result of adding positives.
Now, in the homework you need to look up PHI, this number. It’s used often in art!
This is an amazing result because the algebra agrees with our work on the continued fraction. And the trick to getting the algebra to work was so clever! Can you see how we’d do this to any repeating continued fraction?
Popper 12, Question 3
[pic]
A True
B False
Properties of Fibonacci Numbers
Theorem:
[pic].
The big capital sigma means add from the bottom index to the top.
So this says, the sum of n Fibonacci numbers is [pic].
Let’s illustrate this theorem. I’ll go up to n = 8.
[pic]
Adding the first 8 Fibonacci numbers:
1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 = 54
Checking the list [pic]
Perfect! It works.
Another illustration:
[pic]
On the left, well, I added them but didn’t want to type them!
Now there’s a nifty illustration of WHY this works on page 136. It’s a process called “telescoping”. And it has lots and lots of cancelling in it. It’s actually fun to check out.
Popper 12, Question 4
[pic]
A True
B False
Another property and theorem:
[pic]
Let’s illustrate this using n = 5:
[pic]
And perhaps most astonishing of all:
The Fibonacci numbers can be found in Pascal’s Triangle on diagonals! Page 137
The ” rising diagonals”
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
And on page 138, we have the Fibonacci numbers and Areas
And from this we find another theorem to illustrate:
[pic] Doesn’t that look awful?
Let’s do it with n = 6 – we’ve got the first 6 Fibonacci numbers in the area above.
The height is 8 ([pic]) and the length is 13 ([pic]). Yep!
Homework hint:
We’ll go back to geometry and learn about the “geometric mean”
If we have “b is the geometric mean of a and c” for 3 natural numbers we mean the result of this proportionality:
[pic] we only want the positive number
Now we switch subjects for the very last time this semester at the bottom of page 139.
Let’s take a line of length 1 and split it into 2 carefully chosen pieces: x and 1 – x in a way that the ancient Greeks thought was particularly pleasing:
[pic]
Now we want
[pic]
We only want the positive number so we ignore the minus!
Notice how close this is to Phi!
Now take the reciprocal of both sides:
[pic]
In the book are the steps that show you that for the reciprocal of x, we do have Phi!
The ancient Greeks called this way of breaking up a line: The Golden Section.
It turns out that the rectangles built with the Fibonacci numbers become closer and closer to length Phi with a height of 1 and a break at [pic] as you make them larger and larger by adding on to the right and top. A Golden Rectangle has sides [pic] and is supposed to be perfectly pleasing to the eye.
This is pretty cool really. The Golden Rectangle, as it is known, is used often by architects and artists.
The Pentagram also uses an arithmetic mean. And I leave that to you for homework!
Meanwhile, it has been a pleasure getting to know you over the semester. Please do remind me to publish Hints for the Final as soon as possible!
Thanks!
Ms. Leigh
Popper 12, Question 5
The final is in CASA Testing by appointment.
A True
B False
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- cis 3362 homework 2 ucf computer science
- cis 3362 homework 2
- lesson 1 introduction to congruence and modular arithmetic
- chris farley missouri state university
- introduction computer action team
- discrete mathematics mgnet
- multiplicative cipher apps for the ti89 calculator
- teaching cryptography in high school ti89