Description
1. The Fibonacci numbers and nature. The Fibonacci numbers are defined by F1 = 1, F2 = 1, F3 = F2 + F1 = 2, F4 = F3 + F2 = 3, etc. In general, Fj+1 = Fj + Fj1, j =2 ,3,… . Write down F5, F6, and F7.
F5 = F4 + F3 = 5, F6 = F5 + F4 = 8, F7 = F6 + F5 = 13.
It is often observed that the number of petals on a flower or the number of branches on a tree is a Fibonacci number. For example, most daisies have either 34, 55, or 89 petals, and these are the 9th, 10th, and 11th Fibonacci numbers. The reason four-leaf clovers are so rare is that 4 is not a Fibonacci number.
To see the reason for this, consider the following model of branch growth in trees. We start with the main trunk (F1 = 1), which spends one season growing (F2 = 1), and then after another season, develops two branches (F3 = 2) – a major one and a minor one. After the next season, the major branch develops two branches – a major one and a minor one – while the minor branch grows into a major one, ready to divide in the following season. At this point there are F4 = 3 branches – two major ones and one minor one. At the end of the next season, the two major branches divide, producing two major branches and two minor ones, while the minor one from the previous season grows into a major one. Thus at this point there are F5 = 5 branches, with F4 = 3 of these being major branches ready to divide during the next season. Explain why the Fibonacci numbers arise from this model of branch growth.
1 1 2 3 5
Homework 1
Friday, September 14, 12
2. Drunkard’s walk. A drunkard starts at position x in the diagram below and with each step moves right one space with probability .5 and left one space with probability .5. If he reaches the bar, he stays there, drinking himself into oblivion. If he reaches home, he goes to bed and stays there. You wish to know the probability p(x) that he reaches home before reaching the bar.
0 1 5
bar home
24 3
x
This is a typical Markov chain problem that will be discussed later in the text. Note that p(0) = 0 and p(5) = 1, since the drunk does not leave either the bar or his home. For x =1 ,2,3,4, p(x)=.5p(x1)+.5p(x+1), since he moves left with probability .5 and right with probability .5.
(a) Let the drunk’s starting position be x = 3. What are the possible positions that he could be in after one step, and what are the probabilities of each? How about after two steps?
(b) For which initial positions x would you expect him to reach the bar first and for which would you expect him to reach home first, and why?
Friday, September 14, 12
This is a typical random walk problem, and while it is posed as a silly story, it has real physical applications. Consider an electrical network with equal resistors in series and a unit voltage across the ends. 1 2 3 4
0
5
v(0)=0
v(5)=1
Voltages v(x) will be established at points x =0 ,1,2,3,4,5. We have grounded the point x = 0 so that v(0) = 0, and there is no resistor between the source and point x = 5, so that v(5) = 1. By Kircho↵’s laws, the current flowing into x must be equal to the current flowing out. By Ohm’s Law, if points x and y are separated by a resistor of strength R, then the current ixy that flows from x to y is
ixy =
v(x)v(y) R
.
Thus for x =1 ,2,3,4, we have v(x1)v(x) R
=
v(x)v(x + 1) R
. Multiplying by R and combining like terms we see that v(x)=.5v(x1) + .5v(x + 1). This is exactly the same formula (with the same boundary conditions) that we found for p(x) in the drunkard’s walk problem. Can you think of other situations that might be modeled in this same way? The behavior of a stock price perhaps? Suppose you generalize by allowing di↵erent probabilities of the drunkard moving right or left, say, the probability of moving right is .6 while that of moving left is .4. What generalization of the resistor problem would this correspond to? [Hint: Consider resistors of di↵erent strengths.]
Friday, September 14, 12
6. Plot each of the functions below over the range specified. Produce 4 plots on the same page using the subplot command. (a) f(x)=|x1| for 3x3. (Use abs in MATLAB) (b) f(x)=p|x| for 4x4. (Use sqrt in MATLAB) (c) f(x)=ex2 = exp(x2) for 4x4. (Use exp in MATLAB) (d) f(x)= 1 10×2 +1 for 2x2
Problem 3
Chapt 2
Friday, September 14, 12
This exercise uses the MATLAB M-file koch.m, which you will find on the web page. The M-file contains all the necessary commands to create the fractal, except for the necessary plotting commands. Edit this M-file so that each stage of the fractal is plotted. (Hint: This can be accomplished by adding a plot command just before the completion of the outer for loop.) Add the following commands to keep consistency between plots in the animation:
axis([-0.75 0.75 -sqrt(3)/6 1]); axis equal
Note that the cla command clears the axes. Finally, add the command pause(0.5) in appropriate places to slow the animation. (The fill command, as opposed to plot, produced the filled fractals depicted above.) We will create fractals using Newton’s Method in Chapter ??.
8. In this exercise, you will plot initial stages of a process that creates a fractal known as Koch’s Snowflake, which is depicted below.
Koch’s Snowflake
Stage 0 Stage 1 Stage 2
Chapt 2
Problem 4
4.
Friday, September 14, 12
6
6
13. In the 7th season episode Treehouse of Horror VI of The Simpsons, Homer has a nightmare in which the following equation flies past him
178212 + 184112 = 192212. (6)
Note that this equation, if true, would contradict Fermat’s Last Theorem, which states: For n3, there do not exist any natural numbers x,y and z that satisfy the equation xn+yn = zn. Did Homer dream up a counterexample to Fermat’s Last Theorem?
(a) Compute 12 p178212 + 184112 by typing the following into MATLAB:
format short (1782^12 + 1841^12)^(1/12)
What result does Matlab report? Now look at the answer using format long.
Problem 5
Chapt 5
(b) Determine the absolute and relative error in the approximation 178212+184112 ⇡192212. [Such an example is called a Fermat near-miss because of the small relative error. This example was created by The Simpsons writer David S. Cohen with the intent of catching the eye of audience members with a mathematical interest.] ⇥ (c) Note that the right-hand side of equation (6) is even. Use this to prove that the equation cannot be true.
(d) In a later episode entitled The Wizard of Evergreen Terrace, Homer writes the equation 398712 + 436512 = 447212. Can you debunk this equation?
Friday, September 14, 12
3. Newton’s method can be used to compute reciprocals, without division. To compute 1/R, let f(x)=x1 R so that f(x) = 0 whenx =1/R. Write down the Newton iteration for this problem and compute (by hand or with a calculator) the first few Newton iterates for approximating 1/3, starting with x0 =0 .5, and not using any division. What happens if you start with x0 = 1? For positive R, use the theory of fixed point iteration to determine an interval about 1/R from which Newton’s method will converge to 1/R.
Problem 6
Chapt 4
4. Use Newton’s method to approximate p2 to 6 decimal places