(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 81192, 2664]*) (*NotebookOutlinePosition[ 89607, 2933]*) (* CellTagsIndexPosition[ 88171, 2879]*) (*WindowFrame->Normal*) Notebook[{ Cell["\[Copyright] 2003 K. Sutner ", "RCS"], Cell[TextData[StyleBox["Fibonacci", FontFamily->"Charter"]], "Title", CellTags->"c:1"], Cell[CellGroupData[{ Cell[" Rabbits and Fibonacci Numbers", "Section", CellTags->"c:2"], Cell[CellGroupData[{ Cell[" Leonardo's Rabbits", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Definition Fibonacci", "c:3"}], Cell[TextData[{ "Leonardo di Pisa, aka Fibonacci, was the only notable European \ mathematician during the Middle Ages. Perhaps you would like to read the \ book: ", StyleBox["Liber Abaci, Leonardo di Pisa, 1202", FontSlant->"Italic"], ". It helped bring arithmetic in Europe up to Arab standards (the dark ages \ were really quite dark in Europe, fortunately the Arabs preserved a little \ bit of culture). One of Fibonacci's accomplishments was to determine how \ rabbits reproduce, numerically, that is. \nThe cover story is the following \ problem." }], "Text"], Cell[TextData[StyleBox["A man has one pair of rabbits at a certain place \ entirely surrounded by a wall. We wish to know how many pairs can be bred \ from it in one year, if the nature of these rabbits is such that they breed \ every month one other pair, and begin to breed in the second month after \ their birth. \nIn two months these rabbits begin their breeding cycle, \ producing one pair of rabbits, male and female. The original rabbits and \ their offspring continue to breed in this fashion: no offspring during the \ first two months after birth, and then one pair each following month. ", FontSlant->"Italic"]], "Text", Background->RGBColor[1, 1, 0]], Cell["\<\ To simplify things, we assume that the starting pair of rabbits is \ newly born, one male and one female, and that no rabbit ever dies. Since \ some rabbits have reached reproductive age, and others haven't yet, we need \ to keep track of two counts as follows. One should think of snapshots taken \ at the end of the month: \tmonth\t\trepro. \t\tnon-repro.\ttotal \t1\t\t0\t\t1\t\t1 \t2\t\t1\t\t0\t\t1 \t3\t\t1\t\t1\t\t2 \t4\t\t2\t\t1\t\t3 \t5\t\t3\t\t2\t\t5 \t6\t\t5\t\t3\t\t8 \t and so on and so forth. \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell[" Computing Fibonacci Numbers by Recursion", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Recursive Computation", "c:4"}], Cell[TextData[{ "It is clear from the table that there is a reccurrence hiding. To simplify \ things for the future, it is best to start at time 0, and the sequence we \ are interested in looks like this: \n\n\t", Cell[BoxData[ \(TraditionalForm\`\[Bullet]\ \ \ F\_0\ \ = \ 0, \n\[Bullet]\ \ \ F\_1\ \ = \ 1, \n\[Bullet]\ \ \ F\_\(n + 1\) = \ F\_n\ + \ \(\(F\_\(n - 1\)\)\(.\)\)\)]], "\n\nThese so-called ", StyleBox["Fibonacci numbers", FontColor->RGBColor[0, 0, 1]], " ", Cell[BoxData[ \(TraditionalForm\`F\_n\)]], " turn out to be extremely important in combinatorics and pop up in \ unexpected places in the analysis of algorithms. At any rate, here are the \ first few values: \n\n\t", Cell[BoxData[ \(TraditionalForm\`0, \ 1, \ 1, \ 2, \ 3, \ 5, \ 8, \ 13, \ 21, \ 34, \ 55, \ 89, \ 144, \ 233, \ 377, \ 610, \ 987, 1597, \ 2584, \ 4181, \[Ellipsis]\)]], " \n\nNote that the recurrence is just about the easiest second order \ recurrence imaginable: we must use two previous values, and the most simple \ minded operation we can apply is addition. " }], "Text"], Cell[TextData[{ "We can think of the Fibonacci numbers as a function\n\t", Cell[BoxData[ \(TraditionalForm\`F\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], StyleBox[" ", FontSize->12], "\nHere is a simple recursive implementation of this function in \ Mathematica. " }], "Text"], Cell[BoxData[{ \(Clear[F]\), "\n", \(\(F[0] = 0;\)\), "\n", \(\(F[1] = 1;\)\), "\n", \(\(F[n_Integer] := F[n - 1] + F[n - 2];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Map[\ F, \ Range[0, 10]\ ]\)], "Input", AspectRatioFixed->True], Cell["\<\ Actually, this implementation is quite useless. The problem lies in \ the fact each recursive call tends to trigger 2 more, which trigger 4 more, 8 \ more, and so on: just like rabbits. Moreover, many of these calls are made \ on the same value. Consider the following trace:\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["tr = Flatten[ Trace[ F[11], F[_] ] ]", "Input", AspectRatioFixed->True], Cell[BoxData[ RowBox[{"Count", "[", " ", RowBox[{"tr", ",", TagBox[\(F[2]\), HoldForm]}], "]"}]], "Input", AspectRatioFixed->True], Cell[TextData[{ "There are 55 calls to ", StyleBox["F[2]", "SmallText"], " alone. Here is a table of all the call frequencies:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["tr // Frequencies // TableForm", "Input"], Cell[BoxData[ \(TableForm[ Table[With[{tr = Flatten[Trace[F[n], F[_]]]}, {n, Count[tr, HoldForm[F[0]]], Count[tr, HoldForm[F[1]]], Count[tr, HoldForm[F[2]]], Count[tr, HoldForm[F[3]]], Count[tr, HoldForm[F[4]]]}], {n, 0, 10}]]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(TableForm[ Table[{n, Fibonacci[n], Plus @@ Fibonacci[Range[n]]}, {n, 0, 10}]]\)], "Input"], Cell[BoxData[ \(TableForm[ Table[With[{tr = Flatten[Trace[F[n], F[_]]]}, {n, Length[tr], Fibonacci[n], Plus @@ Fibonacci[Range[n]]}], {n, 0, 12}]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Note that the call frequencies for specific values seem to be Fibonacci \ numbers themselves. More about this later. \n\nIn order to avoid such \ re-computation, Mathematica has a mechanism to keep track of already computed \ values. It stores all known values of F internally in a so-called hash table, \ and when some value ", StyleBox["F[m]", "SmallText"], " is requested, it first checks the table to see if it is already known. \ Otherwise, it makes recursive calls. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[F]\), "\n", \(F[0] = 0; \), "\n", \(F[1] = 1; \), "\n", \(F[n_Integer] := \(F[n] = F[n - 1] + F[n - 2]\); \)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Flatten[Trace[F[10], F[_]]]\)], "Input", AspectRatioFixed->True], Cell["\<\ Much better. All the known values of F are now stored, together \ with the general rule on how to compute more values if needed. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["??F", "Input"], Cell["\<\ If you want to compute large Fibonacci numbers, you will also have \ to change the recursion limit. By default, Mathematica only allows 256 nested \ calls. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \($RecursionLimit = 1024\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Timing[F[500]]\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Dynamic Programming", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Dynamic Programming", "c:5"}], Cell[TextData[{ "Hashing (or memoizing as it is often called) is a general purpose method \ to avoid recomputation in recursive functions. For Fibonacci numbers, \ though, it is not hard to come up with an entirely non-recursive solution. \ The approach here is actully of independent interest and is sometimes \ referred to as ", StyleBox["dynamic programming", FontColor->RGBColor[0, 0, 1]], ". We use a do-loop to repeatedly add the two last values in a sequence \ starting at 0 and 1. " }], "Text"], Cell[BoxData[{ \(Clear[fib]\), "\n", \(fib[n_] := \n Module[\ {a = 0, b = 1}, \ \n\t\t\t\tDo[\ {a, b}\ = \ {b, a + b}, \ {n}\ ]; \n\t\ta\n]\)}], "Input", AspectRatioFixed->True], Cell["fib /@ Range[10]", "Input"], Cell[TextData[{ "This version is quite fast, even when ", Cell[BoxData[ \(TraditionalForm\`n\)]], " is relatively large. " }], "Text"], Cell["Timing[fib[1000]]", "Input"] }, Closed]], Cell[CellGroupData[{ Cell[" An Iterative Solution", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Iterative Computation", "c:6"}], Cell[TextData[{ "The dynamic programming approach can also be viewed as iteration: we \ iterate the update operation for the two local variables ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], " in the last program. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[fibb, fib]\), "\n", \(\(fibb[{x_, y_}] := {y, x + y};\)\), "\n", \(fib[n_Integer] := First[Nest[fibb, {0, 1}, n]]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(fib /@ Range[0, 10]\)], "Input"], Cell[BoxData[ \(Timing[fib[1000]]\)], "Input"], Cell[TextData[{ "The real work is done by iterating ", StyleBox["fibb", "SmallText"], ", but we need a little wrapper function to obtain a useable main function. \ \n\nAs far as speed is concerned, the iterative method is about as fast as \ the dynamic programming solution. Both are faster than the hashed recursive \ one (at least for the first call; after that memoizing stores the value), \ which in turn is much faster than the brute-force recursive method. \n" }], "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Pinning Down Fibonacci Numbers", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:7"], Cell[CellGroupData[{ Cell[" DeMoivre-Binet Formula", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Binet Formula", "c:8"}], Cell[TextData[{ StyleBox["Recall the basic recurrence \n", FontFamily->"Times"], "\t", Cell[BoxData[ \(TraditionalForm\`\(\(\ \ \)\(F\_\(n + 1\) = \ F\_n\ + \ F\_\(n - 1\)\)\)\)]], StyleBox["\nand the computational results from the last section. It seems \ that the Fibonacci numbers grow exponentially fast. ", FontFamily->"Times"], "A crude upper bound for ", Cell[BoxData[ \(TraditionalForm\`F\_n\)]], " would be ", Cell[BoxData[ \(TraditionalForm\`2\^\(\(\ \)\(n\)\)\)]], " (strightforward by induction). Can we get a better description? Here is \ log-plot." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(gr\ = \ LogListPlot[Fibonacci[Range[20]], PlotStyle \[Rule] {Blue, PointSize[0.02]}]\)], "Input"], Cell[TextData[{ StyleBox["Let's assume for the sake of an argument that ", FontFamily->"Times"], Cell[BoxData[ FormBox[ StyleBox[\(F\_n = \ x\^\(\(\ \)\(n\)\)\), FontColor->RGBColor[0, 0, 1]], TraditionalForm]]], ". That is probably not quite right, but perhaps we can determine what \ corrections we have to make to get an accurate description. First, what can \ we say about ", Cell[BoxData[ \(TraditionalForm\`x\)]], " ?\nWe must have \n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\ \ \)\(x\^\(\(\ \)\(n + 1\)\) = \ x\^\(\(\ \)\(n\)\)\ + \ x\^\(\(\ \)\(n - 1\)\)\)\)\)]], StyleBox["\nand therefore", FontFamily->"Times"], "\n\t", Cell[BoxData[ \(TraditionalForm\`x\^\(\(\ \)\(2\)\) = \ \(\(x\)\(\ \)\(+\)\(\ \)\(1\)\ \(\ \)\)\)]], ". \nHence, we have to solve a quadratic equation:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ {\[Alpha],\[CurlyPhi]} = x /. Solve[ x^2 == x + 1, x ]\ \>", "Input"], Cell["{\[Alpha],\[CurlyPhi]} // N", "Input"], Cell[TextData[{ "Note that ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\ + \ \[CurlyPhi]\ = \ 1\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\ \[CenterDot]\ \[CurlyPhi]\ = \ \ \(-1\)\)]], " (this follows from Vieta's theorem or from direct computation). Which of \ the two roots will produce the Fibonacci numbers? A little experimentation \ shows that neither one works." }], "Text"], Cell["\<\ \[Alpha]^Range[0,5] // Simplify \[CurlyPhi]^Range[0,5] // Simplify\ \>", "Input"], Cell[TextData[{ "Not surprising. But, if we add the two sequences we get a bit closer, \ since the ", Cell[BoxData[ \(TraditionalForm\`\@5\)]], " terms cancel out and we obtain a sequence of integers." }], "Text"], Cell["\<\ \[Alpha]^Range[0,10]+ \[CurlyPhi]^Range[0,10] // Simplify\ \>", \ "Input"], Cell[TextData[{ "This is a Fibonacci-like sequence, but the initial conditions are wrong: \ the sequence starts with 2 and 1 (as opposed to 0 and 1). These are the \ so-called ", StyleBox["Lucas numbers ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`L\_\(\(\ \)\(n\)\)\)]], ".\n\nClose, but no cigar. Let's take another look at the positive root. " }], "Text"], Cell["\<\ \[CurlyPhi]^Range[0,8] // Expand // TableForm\ \>", "Input"], Cell["Let's get rid of the 1/2 factors everywhere. ", "Text"], Cell["\<\ 2 \[CurlyPhi]^Range[0,8] // Expand // TableForm\ \>", "Input"], Cell[TextData[{ "There are really two sequences: \n\t- the plain, additive coeffiecents: \ Lucas numbers,\n\t- the multiplicative coefficients of ", Cell[BoxData[ \(TraditionalForm\`\@5\)]], ": Fibonacci numbers.\nA similar picture emerges for the other root \ \[Alpha]:" }], "Text"], Cell["\<\ 2 \[Alpha]^Range[0,8] // Expand // TableForm\ \>", "Input"], Cell["Now we can combine the two sequences the right way:", "Text"], Cell["\<\ (\[CurlyPhi]^Range[0,10] - \[Alpha]^Range[0,10])/Sqrt[5] // \ Simplify\ \>", "Input"], Cell["We can eliminate the negative root by rewriting ", "Text"], Cell["\<\ (\[CurlyPhi]^Range[0,10] - (-1/\[CurlyPhi])^Range[0,10])/Sqrt[5] // \ Simplify\ \>", "Input"], Cell[BoxData[ \(GoldenRatio^20/Sqrt[5]\ - \ Fibonacci[20]\ // \ N\)], "Input"], Cell[BoxData[ \(\((1\ - \ Sqrt[5])\)/2\ // N\)], "Input"], Cell[TextData[{ "Note that Mathematica gives up on the expressions involving large powers. \ But we can force it to be more active by switching to ", ButtonBox["FullSimplify", ButtonStyle->"RefGuideLink"], "." }], "Text"], Cell["\<\ (\[CurlyPhi]^Range[0,10] - (-1/\[CurlyPhi])^Range[0,10])/Sqrt[5] // \ FullSimplify\ \>", "Input"], Cell[TextData[{ "So, we have a computational proof of the following theorem.\n\n", StyleBox["Theorem", FontWeight->"Bold"], ": ", StyleBox["DeMoivre-Binet Formula", FontColor->RGBColor[0, 0, 1]], "\nFor all ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 0\)]], ": ", Cell[BoxData[ \(TraditionalForm\`F\_\(\(\ \)\(n\)\(\ \)\) = \ \(1\/\@5\) \((\ \[CurlyPhi]\^\(\(\ \)\(n\)\) - \ \((\(-1\)/\[CurlyPhi])\)\^\(\(\ \)\(n\)\))\)\ \)]], " .\n\nProof:\n\tInduction on ", Cell[BoxData[ \(TraditionalForm\`n\)]], ".\n\[EmptySquare]" }], "Text"], Cell[TextData[{ "A similar result holds for the Lucas number we stumbled across.\nFor all \ ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 0\)]], ": ", Cell[BoxData[ \(TraditionalForm\`L\_\(\(\ \)\(n\)\(\ \)\) = \ \[CurlyPhi]\^\(\(\ \ \)\(n\)\) + \ \((\(-1\)/\[CurlyPhi])\)\^\(\(\ \)\(n\)\)\)]], " .\n" }], "Text"], Cell[CellGroupData[{ Cell[TextData[{ "Application: The Size of ", Cell[BoxData[ \(TraditionalForm\`F\_n\)]] }], "Subsubsection", CellTags->"c:9"], Cell[TextData[{ "We can exploit the DeMoivre-Binet formula to determine the size of ", Cell[BoxData[ \(TraditionalForm\`F\_\(\(\ \)\(n\)\)\)]], " as follows. Numerically, we have " }], "Text"], Cell["\<\ GoldenRatio // N Log[2,%] 1/Sqrt[5] // N\ \>", "Input"], Cell[TextData[{ "so that ", Cell[BoxData[ \(TraditionalForm\`F\_\(\(\ \)\(n\)\)\)]], " is approximately ", Cell[BoxData[ \(TraditionalForm\`0.45\ \ \[CenterDot]\ 1.62\^\(\(\ \)\(n\)\)\ \[TildeTilde] \ 1/2\ \[CenterDot]\ 2\^\(\(\ \)\(0.7\ n\)\)\)]], ". \nHence we should expect ", Cell[BoxData[ \(TraditionalForm\`F\_n\)]], " to have slightly less than ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\( .7\ n\)\)\)]], " bits in binary. " }], "Text"], Cell[BoxData[ \(IntegerDigits[Fibonacci[1000], 2]\)], "Input"], Cell["IntegerDigits[ Fibonacci[1000], 2 ] // Length", "Input"], Cell["Amazingly close. ", "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" The Golden Ratio", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Golden Ratio", "c:10"}], Cell[TextData[{ "The root ", StyleBox[" ", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`\[CurlyPhi] = \((1\ + \ \@5)\)/2\)]], " of ", Cell[BoxData[ \(TraditionalForm\`x\^\(\(\ \)\(2\)\) = \ x\ - \ 1\)]], " is quite well-known, it is usually called the ", StyleBox["Golden Ratio", FontColor->RGBColor[0, 0, 1]], ". This number is considered to represent particularly harmonious \ proportions (a rectangle with sides 1 and Golden Ratio has the same \ proportions as the rectangle obtained from it by removing a unit square, see \ the fabulous graphics below). The Golden Ratio is a built-in constant in \ Mathematica. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(N[GoldenRatio]\), "\n", \(N[1\/\(GoldenRatio - 1\)]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Sincce ", StyleBox[" ", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`\[CurlyPhi] = 1\/\(\[CurlyPhi]\ - \ 1\)\)]], " we can write down a continued fraction for \[CurlyPhi]." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["Fold[ 1/#1+#2&, x, {1,1,1,1,1,1,1,1,1,1,1,1,1} ]", "Input"], Cell["Truncating and evaluating more Fibonacci numbers pop up. ", "Text"], Cell["% // Simplify", "Input"], Cell["\<\ In the limit, we would get the ratio of two consecutive Fibonacci \ numbers, which limit turns out to be \[CurlyPhi]. I hope you appreciate the intrinsic beauty of the following picture. Think \ Greek temple.\ \>", "Text"], Cell["\<\ With[ {GR=GoldenRatio}, Show[Graphics[{ \t{Red,Rectangle[{0,0},{GR,1}]}, \t{Cyan,Rectangle[{0,0},{1,1}]}, \t{Blue,Rectangle[{1,0},{GR,GR-1}]}, \tLine[{{0,0},{GR,1}}]}], \tAspectRatio\[Rule]Automatic,Frame\[Rule]True,FrameTicks\[Rule]None]];\ \>", \ "Input", AspectRatioFixed->True], Cell["\<\ And, the inverse of GoldenRatio is used as the default aspect ratio \ in plotting commands. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(First[Options[Plot]]\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Combinatorial Identities", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Identities", "c:11"}], Cell[TextData[StyleBox["Fibonacci numbers are an endless source of curious \ little facts. You can manipulate them in many different ways, and you wind up \ with new Fibonacci numbers. Here are some examples. ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell["Sums", "Subsubsection", CellTags->"c:12"], Cell[TextData[StyleBox["What happens if one adds up a few Fibonacci numbers? \ ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Table[\ Sum[Fibonacci[i], {i, k}], {k, 20}]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Fibonacci[\ Range[20]]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(FullSimplify[\ Sum[\ Fibonacci[i], {i, k}]\ - \ Fibonacci[k + 2]\ , \ {k\ \[Element] \ Integers}\ ]\)], "Input"], Cell[TextData[{ StyleBox["Conjecture", FontWeight->"Bold"], ": ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\_\(\(i\)\(\ \)\(\[LessEqual]\)\(\ \)\(n\)\(\ \ \)\)F\_i\ = \ F\_\(n + 2\) - 1\)]], " . \n\nProof:\n\tInduction on ", Cell[BoxData[ \(TraditionalForm\`n\)]], ".\n\[EmptySquare]" }], "Text"], Cell[TextData[StyleBox["How about summing up only the even indices? ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(Sum[Fibonacci[2 i], {i, #}] &\)\ /@ \ Range[20]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Fibonacci[\ Range[20]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["Conjecture", FontWeight->"Bold"], ": ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\_\(\(i\)\(\ \)\(\[LessEqual]\)\(\ \)\(n\)\(\ \ \)\)F\_\(2 i\)\ = \ F\_\(2 n + 1\) - 1\)]], " . \n\nProof:\n\tInduction on ", Cell[BoxData[ \(TraditionalForm\`n\)]], ".\n\[EmptySquare]" }], "Text"], Cell[TextData[StyleBox["Another way to mess up the summation would be to make \ it an alternating sum.", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(Sum[\ \((\(-1\))\)^i\ Fibonacci[i], {i, #}] &\)\ /@ \ Range[20]\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(Fibonacci[\ Range[20]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["Conjecture", FontWeight->"Bold"], ": ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\_\(\(i\)\(\ \)\(\[LessEqual]\)\(\ \)\(n\)\(\ \ \)\)\(\((\(-1\))\)\^\(\(\ \)\(i\)\)\) F\_i\ = \ \(\(\((\(-1\))\)\^\(\(\ \)\(n\)\)\ F\_\(n - 1\)\)\(-\)\ \(1\)\(\ \)\)\)]], ".\n\nProof:\n\tInduction on ", Cell[BoxData[ \(TraditionalForm\`n\)]], ".\n\[EmptySquare]" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Squares: Cassini's Identity", "Subsubsection", CellTags->"c:13"], Cell[TextData[{ StyleBox["Here is an identity involving squares of Fibonacci numbers. \n\n", FontFamily->"Times"], StyleBox["Claim", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": \t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`F\_n\%\(\(\ \)\(2\)\)\ - \ \(F\_\(n - 1\)\) F\_\(n + 1\) = \ \((\(-1\))\)\^n\)]], ". \n\t\t\n", StyleBox["As usual, a computational test is straightforward.", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\((Fibonacci[#]\^2 - Fibonacci[# - 1]\ Fibonacci[# + 1] &)\) /@ Range[100]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Proof:\n\tInduction on ", Cell[BoxData[ \(TraditionalForm\`n\)]], ".\n\[EmptySquare]" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Sums of Squares", "Subsubsection", CellTags->"c:14"], Cell[TextData[StyleBox["Here is the last sum we will consider: sums of \ squares of Fibonacci numbers. Perhaps that will produce some new result? ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(Sum[Fibonacci[i]^2, {i, #}] &\)\ /@ \ Range[20]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["At last, something that looks different from Fibonacci numbers. \ But let's take a closer look. Since the sum includes ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`F\_n\%\(\(\ \)\(2\)\)\)]], ", perhaps we could split off a factor ", Cell[BoxData[ \(TraditionalForm\`F\_n\)]], " -- OK, so it's a wild guess. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(Sum[Fibonacci[i]^2, {i, #}]/Fibonacci[#] &\)\ /@ \ Range[20]\)], "Input", AspectRatioFixed->True], Cell[TextData[StyleBox["Back to rabbits. Hence we have another conjecture. ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Conjecture", FontWeight->"Bold"], ": ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\_\(\(i\)\(\ \)\(\[LessEqual]\)\(\ \)\(n\)\(\ \ \)\)F\_\(\(\ \)\(i\)\)\%\(\(\ \)\(2\)\)\ = \ \(F\_n\) F\_\(n + 1\)\)]], " . \n\nProof:\n\tInduction on ", Cell[BoxData[ \(TraditionalForm\`n\)]], ".\n\[EmptySquare]" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Lucas Numbers", "Subsubsection", CellTags->"c:15"], Cell[TextData[{ "Recall the Lucas numbers we stumbled across in our attempt to get a good \ description of the Fibonacci numbers. \n\n\t", Cell[BoxData[ \(TraditionalForm\`\[Bullet]\ \ \ L\_0\ \ = \ 2, \n\[Bullet]\ \ \ L\_1\ \ = \ 1, \n\[Bullet]\ \ \ L\_\(n + 1\) = \ L\_n\ + \ \(\(L\_\(n - 1\)\)\(.\)\)\)]], "\n\nHow do they compare to the Fibonacci numbers? " }], "Text"], Cell["\<\ Clear[luc] luc[0] = 2; luc[1] = 1; luc[n_] := luc[n-1] + luc[n-2];\ \>", "Input"], Cell["\<\ luc /@ Range[0,10] Fibonacci /@ Range[0,10]\ \>", "Input"], Cell[TextData[{ StyleBox["Conjecture", FontWeight->"Bold"], ": ", Cell[BoxData[ \(TraditionalForm\`L\_\(\(\ \)\(n\)\) = \ F\_\(\(\ \)\(n - 1\)\)\ + \ F\_\(n + 1\)\)]], " . \n\nProof:\n\tInduction on ", Cell[BoxData[ \(TraditionalForm\`n\)]], ".\n\[EmptySquare]" }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Bounds", "Subsubsection", CellTags->"c:16"], Cell[TextData[{ "Here is another connection between the Golden Ratio and Fibonacci numbers. \ \n\n", StyleBox["Claim:", FontWeight->"Bold"], " For all integers ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 2\)]], ": ", Cell[BoxData[ \(TraditionalForm\`\[CurlyPhi]\^\(\(\ \)\(n - 2\)\) \[LessEqual] \ F\_n \[LessEqual] \ \[CurlyPhi]\^\(\(\ \)\(n\)\)\)]], ".", StyleBox["\n", FontWeight->"Bold"], "\nThus, the sequence ", Cell[BoxData[ \(TraditionalForm\`F\_n\)]], " grows essentially just like the exponential function ", Cell[BoxData[ \(TraditionalForm\`\[CurlyPhi]\^\(\(\ \)\(n\)\)\)]], ". Here is a computational check for the upper bound, and a lovely \ Mathematica hack to compare lists pointwise. Make sure to also check the \ lower bound. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(F /@ Range[20]\), "\n", \(N[GoldenRatio]\^Range[20]\), "\n", \(Thread[%% < %]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "\nProof: \nWe only prove the upper bound, the argument for the lower \ bound is almost verbatim the same. The upper bound actually holds for all ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 0\)]], ". Since we need two previous values to compute the next Fibonacci number, \ we need a slightly stronger base case than usual. More precisely, we will \ establish the property \n\t", Cell[BoxData[ \(TraditionalForm\`P(n)\)]], ": ", Cell[BoxData[ \(TraditionalForm\`F\_n \[LessEqual] \ \[CurlyPhi]\^\(\(\ \ \)\(n\)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`F\_\(n + 1\) \[LessEqual] \ \[CurlyPhi]\^\(n + \ 1\)\)]], ". \n for all ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 0\)]], ", rather than the more obvious ", Cell[BoxData[ \(TraditionalForm\`P(n)\)]], ": ", Cell[BoxData[ \(TraditionalForm\`F\_n \[LessEqual] \ \[CurlyPhi]\^\(\(\ \ \)\(n\)\)\)]], " .\nBase case: ", Cell[BoxData[ \(TraditionalForm\`n = 0\)]], ". \nWe have ", Cell[BoxData[ \(TraditionalForm\`F\_0 = \ \(0\ < \ 1\ = \ \[CurlyPhi]\^0\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`F\_1 = \ \(1\ < \ \[CurlyPhi]\ = \ \ \[CurlyPhi]\^1\)\)]], ".\nInduction step: Assume ", Cell[BoxData[ \(TraditionalForm\`P(n)\)]], " holds, ", Cell[BoxData[ \(TraditionalForm\`n \[GreaterEqual] 0\)]], ". To establish ", Cell[BoxData[ \(TraditionalForm\`P(n + 1)\)]], " we only have to show that ", Cell[BoxData[ \(TraditionalForm\`F\_\(n + 2\)\ \[LessEqual] \ \[CurlyPhi]\^\(\(\ \ \)\(n + 2\)\)\)]], " (why?). \n\t", Cell[BoxData[ \(TraditionalForm\`F\_\(n + 2\) = \ \(F\_\(n + 1\) + \ F\_n\ \[LessEqual] \ \[CurlyPhi]\^\(\(\ \)\(n + 1\)\) + \ \ \[CurlyPhi]\^\(\(\ \)\(n\)\) = \ \(\(\[CurlyPhi]\^\(\(\ \)\(n\)\)\)(\ 1\ + \ \[CurlyPhi])\ = \ \(\(\[CurlyPhi]\^\(\(\ \)\(n\)\)\) \ \[CurlyPhi]\^\(\(\ \)\(2\)\) = \ \[CurlyPhi]\^\(\(\ \)\(n + 2\)\)\)\)\)\)]], ". \nQED " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Make sure you understand why the simple version of ", Cell[BoxData[ \(TraditionalForm\`P(n)\)]], " would not work in the last proof. Needless to say, strong induction also \ does the job. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Approximations", "Subsubsection", CellTags->"c:17"], Cell[TextData[{ "The DeMoivre-Binet Formula\n\n\t", Cell[BoxData[ \(TraditionalForm\`F\_\(\(\ \)\(n\)\(\ \)\) = \ \(1\/\@5\) \((\ \[CurlyPhi]\^\(\(\ \)\(n\)\) - \ \((\(-1\)/\[CurlyPhi])\)\^\(\(\ \)\(n\)\))\)\ \)]], " \n\t\nsuggests that ", Cell[BoxData[ \(TraditionalForm\`F\_\(\(\ \)\(n\)\)\)]], " should be fairly close to ", Cell[BoxData[ \(TraditionalForm\`\[CurlyPhi]\^\(\(\ \)\(n\)\)/\@5\)]], ": the second term tends to 0 as ", Cell[BoxData[ \(TraditionalForm\`n\)]], " tends to infinity. How close is fairly close? \n" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\((GoldenRatio\^Range[0, 20])\)/\@5\ // \ N\)], "Input", AspectRatioFixed->True], Cell["Round[%]", "Input"], Cell[TextData[{ "Thus we need only to round to the nearest integer, and we get the \ corresponding Fibonacci number. Easy. \n\nTo prove that this is really true, \ we only need to show that ", Cell[BoxData[ \(TraditionalForm\`\[CurlyPhi]\^\(\(\ \)\(-n\)\)/\@5\)]], " has absolute value less than 1/2. Again, that's not hard: the sequence \ starts out less than 1/2, and is monotonically decreasing. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\((\((1/GoldenRatio)\)\^Range[0, 10])\)/\@5\ // \ N\)], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" A General Recurrence", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Extended Recurrence", "c:18"}], Cell[TextData[{ "Another useful observation is that we can generalize the basic recurrence \ as follows:\n\nFor all ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ m, \ n\)]], ": ", Cell[BoxData[ \(TraditionalForm\`F\_\(n + m\)\ = \ \ F\_\(m + 1\)\ F\_n\ + \ F\_m\ F\_\(n - 1\)\)]], ".\n\nThe special case ", Cell[BoxData[ \(TraditionalForm\`m = 1\)]], " is simply the basic recurrence, but for ", Cell[BoxData[ \(TraditionalForm\`m > 1\)]], " we get a description of ", Cell[BoxData[ \(TraditionalForm\`F\_\(n + m\)\)]], " in terms of earlier Fibonacci numbers. The proof is a simple induction on \ ", Cell[BoxData[ \(TraditionalForm\`m\)]], ". \n\nThis has a number of interesting consequences. First off, \n\n\t", Cell[BoxData[ \(TraditionalForm\`F\_\(2 n\)\ \ \ \ \ \ = \ \ \ F\_n\%\(\(\ \ \)\(2\)\)\ + \ 2 F\_n\ F\_\(n - 1\)\)]], " and \n\t", Cell[BoxData[ \(TraditionalForm\`F\_\(2 n + 1\)\ = \ \ \ F\_\(n + 1\)\%\(\(\ \ \)\(2\)\)\ + \ F\_n\%\(\(\ \)\(2\)\)\)]], ".\n\t\nFurthermore, \n\n\t", Cell[BoxData[ \(TraditionalForm\`gcd(\ F\_n, \ F\_\(\(\ \)\(m\)\(\ \)\))\ = \ F\_\(gcd(n, m)\)\)]] }], "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[" From Iteration To Matrix Powers", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Matrix Computation", "c:19"}], Cell[TextData[{ StyleBox["We have seen a number of methods to compute Fibonacci numbers, \ all based on the basic recurrence \n\n", FontFamily->"Times"], "\t", Cell[BoxData[ \(TraditionalForm\`\(\(\ \ \)\(F\_\(n + 1\) = \ F\_n\ + \ \(\(F\_\(n - 1\)\)\(.\)\)\)\)\)]], "\n", StyleBox["\nSo far we have focused on computation, rather than algebra. \ Here is another look at the iterative method. \nThe method is very important \ to deal with recurrences in general, try to understand what is going on.\n\ The main trick is to replace the second order recurrence over the integers by \ a first order recurrence over matrices of integers: the complexity of the \ recurrence goes down, but we have to pay a price: the algebra becomes more \ complicated. This is already \nThe so-called companion matrix for our basic \ recurrence is ", FontFamily->"Times"], Cell[BoxData[ FormBox[ RowBox[{"M", " ", "=", " ", RowBox[{"(", GridBox[{ {"0", "1"}, {"1", "1"} }], ")"}]}], TraditionalForm]]], ".", StyleBox["\n", FontFamily->"Times"], "The recurrence translates into \n\t", Cell[BoxData[ \(TraditionalForm\`A\_\(n + 1\)\ = \ M\[CenterDot]\ A\_n\)]], "\nwhere ", Cell[BoxData[ \(TraditionalForm\`A\_\(\(\ \)\(n\)\)\)]], " is the current vector of numbers, and ", Cell[BoxData[ \(TraditionalForm\`A\_\(\(\ \)\(n + 1\)\)\)]], " the next, just as in the iterative algorithm. The starting vector is ", Cell[BoxData[ \(TraditionalForm\`A\_\(\(\ \)\(0\)\) = \ \((0, 1)\)\)]], ". Therefore, \n\t", Cell[BoxData[ \(TraditionalForm\`A\_n\ = \ M\^\(\(\ \)\(n\)\)\[CenterDot]\ A\_\(\(\ \)\(0\)\)\)]], "\nwhere ", Cell[BoxData[ \(TraditionalForm\`A\_\(\(\ \)\(n\)\)\ = \ \((F\_\(\(\ \)\(n\)\), \ F\_\(\(\ \)\(n + 1\)\))\)\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ M = {{0,1},{1,1}}; A0 = {0,1};\ \>", "Input"], Cell["MatrixPower[M,10] . A0", "Input"], Cell["\<\ So, all we need to do is compute matrix powers to get the \ Fibonacci numbers. We can get the Binet formula out of the matrix representation, too. First, we \ rewrite the matrix in diagonal form, so it is easier to compute the powers. \ \ \>", "Text"], Cell["{{\[Alpha],\[CurlyPhi]},{u,v}} = Eigensystem[M]", "Input"], Cell[TextData[{ "Here ", Cell[BoxData[ \(TraditionalForm\`u\)]], " and ", Cell[BoxData[ \(TraditionalForm\`v\)]], " are the eigenvectors, and ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[CurlyPhi]\)]], " are the eigenvalues - note that these are just the roots of ", Cell[BoxData[ \(TraditionalForm\`x\^\(\(\ \)\(2\)\) - x\ - \ 1\ \ = \ 0\)]], ". At any rate, we need to change our coordinate system to ", Cell[BoxData[ \(TraditionalForm\`\((u, v)\)\)]], ". The corresponding transformation and its inverse are " }], "Text"], Cell["\<\ P = {u,v}; Q = Inverse[P];\ \>", "Input"], Cell[TextData[{ "We can diagonalize ", Cell[BoxData[ \(TraditionalForm\`M\)]], " like so:" }], "Text"], Cell[BoxData[{ \(\(MM\ = \ P\ . M\ . \ Q\ // \ Simplify;\)\), "\n", \(MM // \ MatrixForm\)}], "Input"], Cell["\<\ Thus, the diagonal elements are the eigenvalues \[Alpha] and \ \[CurlyPhi], as required by matrix theory. Computing the powers of such a \ matrix is easy: we just compute the powers of the diagonal elements. \ \>", \ "Text"], Cell["\<\ n = 10; Q . {{\[Alpha]^n,0},{0,\[CurlyPhi]^n}} . P . A0 // Simplify\ \>", "Input"], Cell[TextData[{ "Since ", Cell[BoxData[ \(TraditionalForm\`P\ \[CenterDot]\ A\_0\ = \ \((1, 1)\)\)]], ", the whole computation simplifies to " }], "Text"], Cell["\<\ Clear[n] Q . {\[Alpha],\[CurlyPhi]}^n // FullSimplify\ \>", "Input"], Cell[TextData[{ "So, we have another proof of the DeMoivre-Binet formula ", Cell[BoxData[ \(TraditionalForm\`F\_\(\(\ \)\(n\)\(\ \)\) = \ \(1\/\@5\) \((\ \[CurlyPhi]\^\(\(\ \)\(n\)\) - \ \((\(-1\)/\[CurlyPhi])\)\^\(\(\ \)\(n\)\))\)\ \)]], " ." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" The 1/2 Problem and Fast Fibonacci", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Fast Fibonacci", "c:20"}], Cell[TextData[{ StyleBox["To finish our discussion, we return to the problem of computing \ Fibonacci numbers. We can exploit the generalized recurrence from the \ previous section to get a very fast divide-and-conquer algorithm based on the \ observation \n", FontFamily->"Times"], "\n\t", Cell[BoxData[ \(TraditionalForm\`F\_\(2 n\)\ \ \ \ \ \ = \ \ \ F\_n\%\(\(\ \ \)\(2\)\)\ + \ 2 F\_n\ F\_\(n - 1\)\)]], " and \n\t", Cell[BoxData[ \(TraditionalForm\`F\_\(2 n + 1\)\ = \ \ \ F\_\(n + 1\)\%\(\(\ \ \)\(2\)\)\ + \ F\_n\%\(\(\ \)\(2\)\)\)]], "\n\t\nfrom above. ", StyleBox["However, we need to do some groundwork first. We will simplify \ the problem a little and consider a hypothetical recursion where the indices \ on the right hand side are ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\[LeftFloor]n/2\[RightFloor]\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\[LeftCeiling]n/2\[RightCeiling]\)]], ". It is not much harder to tackle the analagous problem for the Fibonacci \ recurrence above. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell["Divide and Conquer, taken seriously", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"1/2 Problem", "c:21"}], Cell[TextData[{ StyleBox["Many recursive algorithms call for an input number or list to be \ cut in half, and the algorithm then is applied recursively to each half. As \ long as the number is a power of 2 (or the list has length a power of 2), \ this is quite straightforward. However, in the general case one has to deal \ with uneven splits: number ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" breaks up into ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\[LeftFloor]n/2\[RightFloor]\)]], StyleBox[" and", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\[LeftCeiling]n/2\[RightCeiling]\)\)\)]], StyleBox[", and likewise for lists. \nThe question arises: how many \ recursive calls will there be? More precisely, suppose we have a recursive \ function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(f(n)\)\(\ \)\)\)]], StyleBox[" that makes calls to ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(\[LeftFloor]n/2\[RightFloor])\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(\[LeftCeiling]n/2\[RightCeiling])\)]], StyleBox[", and that we store known values in a table. How many recursive \ calls will the evaluation ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(f(n)\)\(\ \)\)\)]], StyleBox[" trigger? \nPhrased in slightly more mathematical language, we \ have the following question. \n\n", FontFamily->"Times"], StyleBox["Problem: ", FontFamily->"Times", FontWeight->"Bold"], StyleBox["\nCount the number of predecessors of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ > \ 0\)]], StyleBox[" under the operations ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\[LeftFloor]n/2\[RightFloor]\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\[LeftCeiling]n/2\[RightCeiling]\)]], StyleBox[".\n\nThis is not exactly the problem we encounter with the \ Fibonacci recursion above, but very similar. Unlike with previous problem \ dealing with iteration, this time we iterate two functions on the input. We \ will write \n\tHalf[x] := set of predecessors and \n\thalf[x] := the \ number of predecessors.\nFor the sake of completeness, we set ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`Half[0]\ = \ {0}\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`Half[1]\ = \ {0, 1}\)]], StyleBox[", though we are only interested in larger inputs. \nNote that \ for all ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ \[GreaterEqual] 2\)]], StyleBox[": ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`y\ \[Element] \ Half[x]\)]], StyleBox[" implies ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`y\ < \ x\)]], ", so a recursive algorithm can assume that the values of the function to \ be computed are already determined on ", Cell[BoxData[ \(TraditionalForm\`Half[x]\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell[" A Conjecture", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:22"], Cell["\<\ First, a brute force simulation: compute all the numbers that are \ encountered in the chain of recursive calls. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[half, Half]\), "\n", \(\(Half[0] = {0};\)\), "\n", \(\(Half[1] = {0, 1};\)\), "\n", \(\(Half[x_] := \(Half[x] = Half[Floor[x\/2]] \[Union] Half[Ceiling[x\/2]] \[Union] {x}\);\)\), "\n", \(\(half[x_] := Length[Half[x]];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(Half[100]\), "\n", \(Half[101]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(L500 = half /@ Range[5000];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(ListPlot[L500, PlotStyle \[Rule] Blue];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["\nIt looks like half grows no more than logarithmically. If we \ look more closely, we are lead to the following conjecture. \n", FontFamily->"Times"], StyleBox["Conjecture", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`half[x]\ \[LessEqual] \ 2\ \ \[LeftCeiling]\ \(log\_2\) x\ \[RightCeiling]\)]], StyleBox[" for ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ > \ 2\)]], StyleBox[".\nWe can verify this bound for the first few values of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], StyleBox[". ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(L1 = \((2\ Ceiling[N[Log[2, #1]]] &)\) /@ Range[100]\), "\n", \(L2 = Take[L500, 100]\), "\n", \(And @@ Drop[Thread[L1 \[GreaterEqual] L2], 2]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Here is another piece of evidence: the jump points of half. Let us \ determine all x such that \n ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(z\ < \ x\ \ \ implies\ \ \ half[z]\ < \ half[x]\)\)\)]], "\ni.e., the places where the function jumps to a larger value than all \ previous values. For ", Cell[BoxData[ \(TraditionalForm\`x\ \[LessEqual] \ 500\)]], " we can compute as follows:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(L = half /@ Range[500];\)\), "\n", \(\(LL = Thread[{L, Range[500]}];\)\), "\n", \(\(LL = Sort[LL];\)\), "\n", \(\(LLL = Partition[LL, 2, 1];\)\), "\n", \(\(Ls = Select[LLL, #1\[LeftDoubleBracket]1, 1\[RightDoubleBracket] < #1\[LeftDoubleBracket]2, 1\[RightDoubleBracket] &];\)\), "\n", \(\(jump = Last /@ \(Last /@ Ls\);\)\), "\n", \(TableForm[Thread[{jump, half /@ jump}]]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["From the table, it seems that the jump set only contains numbers \ of the form \n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`2\^\(\(\ \)\(k\)\)\ + \ 1\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(2\^\(\(\ \)\(k\)\)\ + \ 2\^\(\(\ \)\(k - 1\)\)\ + \ 1\)\)\)]], StyleBox[".", FontFamily->"Times", FontWeight->"Bold"], StyleBox["\nand that \n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`half[2\^\(\(\ \)\(k\)\)\ + \ 1]\ = \ 2 k\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`half[ 2\^\(\(\ \)\(k\)\)\ + \ 2\^\(\(\ \)\(k - 1\)\)\ + \ 1]\ = \ 2 k\ + \ 1\)]], StyleBox[".\nThe conjecture looks good, so far. But we have no proof. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Half Orbits", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:23"], Cell["\<\ For a real proof, we have to take a look at actual the numbers in \ Half[x], rather than just half[x]. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(half[545]\), "\n", \(half[546]\), "\n", \(Half[545]\), "\n", \(Half[546]\)}], "Input", AspectRatioFixed->True], Cell["\<\ Only one point where the lists differ. Don't jump at conclusions, \ though. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(half[560]\), "\n", \(half[561]\), "\n", \(Half[560]\), "\n", \(Half[561]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["Looking at these orbits suggests that Half[x] contains at most \ two numbers in each interval ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`Range[\ 2\^\(\(\ \)\(k\)\), \ 2\^\(\(\ \)\(k + 1\)\) - 1\ ]\)]], StyleBox[". In other words, if we write the numbers in Half[x] in binary, \ there are only at most two k-digit numbers, for each k. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ TableForm[ IntegerDigits[Half[561],2], \t\t\tTableAlignments\[Rule]{Center}, TableSpacing->1 ]\ \>", "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["Moreover, if there are indeed two numbers, then their difference \ is only 1. \n\n", FontFamily->"Times"], StyleBox["Lemma", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": For all k, the intersection of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`Half[x]\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`Range[\ 2\^\(\(\ \)\(k\)\), \ 2\^\(\(\ \)\(k + 1\)\) - 1\ ]\)]], StyleBox[" ", FontFamily->"Times"], StyleBox[" ", FontFamily->"Times", FontWeight->"Bold"], StyleBox["has size at most 2. If there are two numbers in this \ intersection, then they are consecutive. \nProof: \nWe use induction on x to \ show that Union[ Half[x], Half[x+1] ] has the intersection property as \ claimed. The base case is obvious, so consider some number x > 2.. \nCase 1: \ ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ = \ 2\ z\)]], StyleBox[". \nIn this case, ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({\ \[LeftFloor]x/ 2\[RightFloor], \ \[LeftCeiling]x/ 2\[RightCeiling], \[LeftFloor]\((x + 1)\)/ 2\[RightFloor], \[LeftCeiling]\((x + 1)\)/ 2\[RightCeiling]\ }\ \ = \ {z, \ z, \ z, \ z + 1\ }\)\)\)]], StyleBox[". \nCase 2: ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ = \ 2\ z\ + \ 1\)]], StyleBox[". \nThen ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({\ \[LeftFloor]x/ 2\[RightFloor], \ \[LeftCeiling]x/ 2\[RightCeiling], \[LeftFloor]\((x + 1)\)/ 2\[RightFloor], \[LeftCeiling]\((x + 1)\)/ 2\[RightCeiling]\ }\ \ = \ {z, \ z + 1, \ z + 1, \ z\ + \ 1\ }\)\)\)]], StyleBox[". \nIn either case, we are done by IH. From this, the claim in \ the lemma follows since Half[x] is a subset of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`Half[x]\ \[Union] \ Half[x + 1]\)]], ".", StyleBox["\n\[EmptySquare]", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[StyleBox["Note the trick in the induction proof: we prove a \ slightly stronger statement than what we really need, but this greases the \ wheels in the inductive step. Also note that the conjecture follows \ immediately from the lemma. ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["An Application: Fast Fibonacci Numbers", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Fast Fibonacci Algorithm", "c:24"}], Cell[TextData[{ "Here is a way to compute the Fibonacci numbers faster than with the plain \ recursion we already know. The trick is to move from a slow ", Cell[BoxData[ \(TraditionalForm\`n\ \[DoubleLongRightArrow]\ n - 1\)]], " recursion to the fast n \[DoubleLongRightArrow] n/2 type from the \ previous section. Since there are at most ", Cell[BoxData[ \(TraditionalForm\`2\ \(log\_2\) n\)]], " calls, we should expect much better performance than from the standard \ method. We will have more to say about the comparative speed of these \ programs when we talk about running time analysis. \n\nYou can see from \ executing the input cell below, though, that this code really flies. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[ffib]\), "\n", \(\(ffib[0] = 0;\)\), "\n", \(\(ffib[1] = 1;\)\), "\n", \(\(ffib[ n_] := \((\ ffib[n] = \[IndentingNewLine]With[{m = n/2}, \n\t\t\ ffib[m]\^2 + 2\ ffib[m]\ ffib[m - 1]])\) /; EvenQ[n];\)\), "\n", \(\(ffib[n_] := \(ffib[n] = With[{m = \((n - 1)\)/2}, ffib[m + 1]\^2 + ffib[m]\^2]\);\)\)}], "Input", AspectRatioFixed->True], Cell["$RecursionLimit=10000;", "Input"], Cell[BoxData[ \(ffib /@ Range[100]\)], "Input", AspectRatioFixed->True], Cell["ffib[1000] // Timing", "Input"], Cell[TextData[{ StyleBox["Note how quickly ", FontFamily->"Times"], StyleBox["ffib", "MR", FontFamily->"Times"], StyleBox[" executes. \n\n", FontFamily->"Times"], StyleBox["Lemma", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`ffib[n]\)]], StyleBox[" is the ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox["th Fibonacci number. \nProof: As always, write ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`F\_n\)]], StyleBox[" for the n-th Fibonacci number. We will show by strong induction \ on ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" that:\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`F\_\(2 n\) = F\_n\%\(\(\ \)\(2\)\) + \ 2\ \(F\_n\) F\_\(n - 1\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`F\_\(2 n + 1\) = F\_\(n + 1\)\%\(\(\ \)\(2\)\) + \ \ F\_n\%\(\(\ \)\(2\)\)\)]], StyleBox["\nNote that this suffices: an easy induction then shows that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`ffib[n]\ = \ F\_n\)]], StyleBox[". We may safely assume that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n \[GreaterEqual] \ 2\)]], ". ", StyleBox["Then\n", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`F\_\(2 n\) = \ \(F\_\(2 n - 1\) + F\_\(2 n - 2\) = \ \(F\_n\%2 + F\_\(n - 1\)\%\(\(\ \)\(2\)\) + F\_\(n - 1\)\%\(\(\ \)\(2\)\)\ + \ 2\ \(F\_\(n - 1\)\) F\_\(n - 2\)\ = \(F\_n\%2 + 2 \(\( F\_\(n - 1\)\)(F\_\(n - 1\)\ + F\_\(n - 2\))\)\ = F\_n\%\(\(\ \)\(2\)\) + \ 2\ \(F\_n\) F\_\(n - 1\)\)\)\)\)]], ".\nLikewise for odd positions we get", StyleBox["\n", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`F\_\(2 n + 1\) = \ \(F\_\(2 n\) + F\_\(2 n - 1\) = \ \(F\_n\%2 + 2 \( F\_n\) F\_\(n - 1\) + F\_n\%\(\(\ \)\(2\)\)\ + F\_\(n - 1\)\%\(\(\ \)\(2\)\)\ = \(\(F\_n\%\(\(\ \)\(2\)\) + \ \(F\_n\) F\_\(n - 1\)\ + F\_n\%\(\(\ \)\(2\)\(\ \)\) + \(F\_n\) F\_\(n - 1\)\ + F\_\(n - 1\)\%\(\(\ \)\(2\)\)\)\(\ \)\(=\)\)\)\)\)]], "\n", Cell[BoxData[ \(TraditionalForm\`\(\(=\)\(\ \)\(F\_n\%\(\(\ \)\(2\)\) + \(F\_n\) F\_\(n - 1\) + F\_\(n + 1\)\ F\_\(\(n\)\(-\)\(1\)\(\ \)\) = F\_\(n + 1\)\%\(\(\ \)\(2\)\) + \ \ F\_n\%\(\(\ \)\(2\)\)\)\)\)]], ".\n\[EmptySquare]" }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Groups and Fast Fibonacci", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->{"Fibonacci Group", "c:25"}], Cell[TextData[StyleBox["Here is yet another way to tackle the problem of \ computing Fibonacci numbers quickly. This time we use algebra. ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell["Squaring In a Monoid", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"1/2 Problem", "c:26"}], Cell[TextData[{ "Suppose you have to compute ", Cell[BoxData[ \(TraditionalForm\`x\^1024\)]], ". We can do this brute force using 1023 multiplications. But clearly, \ there is a better way: repeatedly square ", Cell[BoxData[ \(TraditionalForm\`x\)]], ". \n\t", Cell[BoxData[ \(TraditionalForm\`x, \ x\^\(\(\ \)\(2\)\), \ x\^\(\(\ \)\(4\)\), \ x\^16, \ x\^32, \ x\^64, \ x\^128, \ x\^256, \ x\^512, \ x\^1024\)]], "\nThis takes only 9 multiplications. In general, we can compute ", Cell[BoxData[ \(TraditionalForm\`x\^\(\(\ \)\(2\^k\)\)\)]], " in just ", Cell[BoxData[ \(TraditionalForm\`k - 1\)]], " squaring operations. Also note that we can assemble other powers from \ the powers of 2. E.g.,\n\t ", Cell[BoxData[ \(TraditionalForm\`x\^1100\ = \ x\^1024\ x\^64\ x\^8\ x\^4\)]], ". \nThis takes only ", Cell[BoxData[ \(TraditionalForm\`9 + 3\ = 12\)]], " multiplications.\nIn the general case, to compute ", Cell[BoxData[ \(TraditionalForm\`a\^\(\(\ \)\(b\)\)\)]], " use the fact that ", Cell[BoxData[ \(TraditionalForm\`a\^\(\(\ \)\(b\ + \ b\^\[Prime]\)\)\ \ = \ a\^\(\(\ \)\(b\)\)\ \[CenterDot]\ a\^\(\(\ \)\(b\^\[Prime]\)\)\)]], ".\nIn other words, decompose the exponent ", Cell[BoxData[ \(TraditionalForm\`b\)]], " into powers of 2 (yes, that's just the ordinary binary expansion of ", Cell[BoxData[ \(TraditionalForm\`b\)]], "), compute these powers quickly be repeated squaring, and then multiply \ everything together. \nActually, there is no need to explicitely compute the \ binary expansion of ", Cell[BoxData[ \(TraditionalForm\`b\)]], ". Here is a more elegant approach, based on exactly the same idea: " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ \tz = 1; \tx = a; \te = b; \twhile ( e > 0 ) \t{ \t\tif (e is odd) \t\t\tz = z \[CircleTimes] x; \t\tx = x \[CircleTimes] x; \t\te = e/2; \t}\ \>", "Program", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ This makes sense not just for multiplication of ordinary numbers, \ but also for any monoid. We have indicated the monoid operation by \ \[CircleTimes]. The 1 in the first line is the neutral element in the \ monoid. \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["The Fibonacci Monoid", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:27"], Cell[TextData[{ "Is there some monoid in which we could exploit the fast exponentiation \ algorithm from above to quickly compute Fibonacci numbers? Yes, there is, \ but it's not particularly obvious. \nThe carrier set is ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\ \[Cross]\ \ \[DoubleStruckCapitalN]\)]], " and the operation is defined by \n\t\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{ FormBox["(", "TraditionalForm"], \(a, b\), ")"}], " ", "*", " ", \((c, d)\)}], "=", " ", \((\ a\ \((c + d)\)\ + \ b\ c, \ a\ c\ + \ b\ d\ )\)}], TraditionalForm]], Background->RGBColor[1, 1, 0]], ".\nThe neutral element is ", Cell[BoxData[ \(TraditionalForm\`\((0, 1)\)\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[a, b, c, d, e, f]\), "\[IndentingNewLine]", \(CircleTimes[{a_, b_}, {c_, d_}]\ := \ {\ a\ d\ + \ b\ c\ + \ a\ c, \ a\ c\ + \ b\ d}\), "\[IndentingNewLine]", \(\(CircleTimes[{a_, b_}, {c_, d_}, xx__]\ := \ CircleTimes[{\ a\ d\ + \ b\ c\ + \ a\ c, \ a\ c\ + \ b\ d}, xx\ ];\)\)}], "Input"], Cell[BoxData[ \({a, b}\[CircleTimes]\ {c, d}\)], "Input"], Cell[BoxData[ \({1, 2}\[CircleTimes]{3, 4}\)], "Input"], Cell["We have to verify the monoid properties.", "Text"], Cell[BoxData[ \(Clear[u, v, w, x, y, z]\)], "Input"], Cell["associativity", "Text"], Cell[BoxData[{ \(\(({u, v}\[CircleTimes]{w, x})\)\[CircleTimes]{y, z}\ == \ \ \(\({u, v}\[CircleTimes]\(({w, x}\[CircleTimes]{y, z})\)\)\(\ \)\)\), "\n", \(% // \ Simplify\)}], "Input"], Cell["neutral element", "Text"], Cell[BoxData[ \({u, v}\[CircleTimes]{0, 1} \[Equal] \ {0, 1}\[CircleTimes]{u, v} \[Equal] \ {u, v}\)], "Input"], Cell["It turns out, the operation is also commutative:", "Text"], Cell[BoxData[ \({u, v}\[CircleTimes]{w, x}\ \[Equal] \ {w, x}\[CircleTimes]{u, v}\)], "Input"], Cell[TextData[StyleBox["But what does this have to do with Fibonacci numbers? \ First note that there is a special element that mimics the Fibonacci \ recurrence in the following sense:", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \({u, v}\[CircleTimes]{1, 0}\)], "Input"], Cell[TextData[StyleBox["Let's define a squaring operation, and apply it to \ the special element.", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[sq, a, b]\), "\[IndentingNewLine]", \(\(sq[{u_, v_}]\ := \ {u, v}\[CircleTimes]{u, v};\)\)}], "Input"], Cell[BoxData[ \(\(NestList[\ sq, \ {a, b}, \ 2\ ]\ // \ Expand\) // \ TableForm\)], "Input"], Cell["Too messy to see what is goin on. Try simpler values. ", "Text"], Cell[BoxData[ \(\(NestList[\ sq, \ {0, b}, \ 5\ ]\ // \ Expand\) // \ TableForm\)], "Input"], Cell[TextData[{ "This looks promising. If we set ", Cell[BoxData[ \(TraditionalForm\`a = 1\)]], ", we seem to be getting Fibonacci numbers. " }], "Text"], Cell[BoxData[ \(Flatten /@ Pairs[\ \ NestList[\ sq, \ {1, 0}, \ 5\ ], \ Fibonacci[2^Range[0, 5]]\ ] // \ TF2\)], "Input"], Cell[BoxData[ \(\({u, v}\[CircleTimes]# &\)\ /@ \ NestList[sq, {1, 0}, 5]\ // \ TableForm\)], "Input"], Cell["\<\ So now we can implement a fast Fibonacci procedure. We provide an \ option that allows us to return either the monoid element, or just the \ Fibonacci number. \ \>", "Text"], Cell[BoxData[{ \(Clear[fastFib]\), "\[IndentingNewLine]", \(\(Options[fastFib] = {Full \[Rule] False};\)\), "\[IndentingNewLine]", \(fastFib[\ n_Integer, opts___?OptionQ\ ]\ := \ \[IndentingNewLine]Module[{a, e, z}, \[IndentingNewLine]\t\tz\ = \ {0, 1}; \[IndentingNewLine]\t\ta\ = \ {1, 0}; \[IndentingNewLine]\t\te\ = \ n; \[IndentingNewLine]\t\tWhile[\ e\ > \ 0, \[IndentingNewLine]\t\t\tIf[\ OddQ[e], \ z\ = \ z\ \[CircleTimes]\ a\ ]; \[IndentingNewLine]\t\t\ta\ = \ a\ \[CircleTimes]\ a; \[IndentingNewLine]\t\t\te\ = \ Quotient[e, 2];\[IndentingNewLine]\t\t]; \[IndentingNewLine]\t\tIf[\ \ \ \(Full\ /. \ {opts}\)\ /. \ Options[fastFib], \[IndentingNewLine]\t\tz, \ First[z]\ ]\[IndentingNewLine]]\)}], "Input"], Cell["A little testing:", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(fastFib\ /@ \ Range[0, 10]\)], "Input"], Cell[BoxData[{ \(fastFib[\ 1000\ ]\), "\n", \(Fibonacci[1000]\), "\[IndentingNewLine]", \(%\ \[Equal] \ %%\)}], "Input"], Cell[BoxData[ \(And @@ Table[\ fastFib[k] \[Equal] Fibonacci[k], \ {k, 0, 100}\ ]\)], "Input"], Cell[BoxData[{ \(\(a = Fibonacci[2^16];\)\ // \ Timing\), "\[IndentingNewLine]", \(\(b = fastFib[2^16];\)\ // \ Timing\), "\[IndentingNewLine]", \(a\ \[Equal] \ b\)}], "Input"], Cell[BoxData[{ \(DigitCount[b]\), "\[IndentingNewLine]", \(Plus @@ %\)}], "Input"], Cell["Not bad for a non-system routine.", "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Is it a Group?", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:28"], Cell[TextData[{ "The operation in our monoid was\n\t\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{ FormBox["(", "TraditionalForm"], \(a, b\), ")"}], " ", "\[CircleTimes]", " ", \((c, d)\)}], "=", " ", \((a\ d\ + \ b\ c\ + \ a\ c, \ a\ c\ + \ b\ d\ )\)}], TraditionalForm]]], ".\nwith neutral element ", Cell[BoxData[ \(TraditionalForm\`\((0, 1)\)\)]], ". \nCould this be a group by any chance? We have to solve the following \ equations. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(eq\ = \ Thread[{u, v}\[CircleTimes]{w, x}\ \[Equal] \ {0, 1}]\)], "Input"], Cell[BoxData[ \(Solve[eq, \ {w, x}]\)], "Input"], Cell["Solve[ u^2 - u v -v^2 == 0, {u} ]", "Input"], Cell["% // FullSimplify", "Input"], Cell["\<\ Unfortunately, this is a rational expression, we would have \ preferred something polynomial. But, we can still define an inverse \ operation.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ RowBox[{ StyleBox[\(inv[{u_, v_}]\ := \ {u, \(-u\) - v}/\((u^2 - u\ v\ - \ v^2)\)\), FontColor->RGBColor[0, 0, 1]], ";"}]], "Input"], Cell[BoxData[{ \(inv[{u, v}]\ \[CircleTimes]\ {u, v}\ \), "\[IndentingNewLine]", \(%\ // \ Simplify\)}], "Input"], Cell[BoxData[{ \(inv[{0, 1}]\), "\[IndentingNewLine]", \(inv[{1, 0}]\)}], "Input"], Cell[BoxData[{ \(inv[{2, 3}]\), "\[IndentingNewLine]", \(inv[%]\)}], "Input"], Cell[TextData[{ "Works fine. Note that for ", Cell[BoxData[ \(TraditionalForm\`\((0, 0)\)\)]], " there is no inverse, ", Cell[BoxData[ \(TraditionalForm\`\((0, 0)\)\)]], " is a zero-element:\n\t\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{ FormBox["(", "TraditionalForm"], \(a, b\), ")"}], " ", "*", " ", \((0, 0)\)}], "=", " ", \(\((0, 0)\)\ *\((a, b)\)\ = \ \((0, 0)\)\)}], TraditionalForm]]], ".\nHow about the rest of the monoid? " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[a, b]\), "\n", \(Reduce[\ a^2\ - \ a\ b\ - \ b^2 \[Equal] 0, \ {a, b}\ ]\)}], "Input"], Cell[TextData[{ "No problem, ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], " can't both be rational, except for the case ", Cell[BoxData[ \(TraditionalForm\`a = \(b = 0\)\)]], ". \nSo, there really is a commutative group, but it is a bit more \ complicated:\n\t\t", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalQ]\ \[Cross]\ \ \[DoubleStruckCapitalQ]\ - {\((0, 0)\)}\)]], ". \nBut why should this make a difference to computing Fibonacci numbers? \ Consider the problem of computing ", Cell[BoxData[ \(TraditionalForm\`F\_1023\)]], ". We can get ", Cell[BoxData[ \(TraditionalForm\`F\_1024\)]], " with just 9 squarings, but how do we get back to the previous number? \ Since we are dealing with a group, we can multiply by the inverse of ", Cell[BoxData[ \(TraditionalForm\`\((1, 0)\)\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(inv[{1, 0}]\ \[CircleTimes]\ fastFib[2^10, Full \[Rule] True]\)], "Input"], Cell[BoxData[ \(First[%]\ \[Equal] \ Fibonacci[1023]\)], "Input"], Cell[TextData[{ "This is a bit weak, since our fast Fibonacci procedure actually computes \ ", Cell[BoxData[ \(TraditionalForm\`\((F\_n, F\_\(n - 1\))\)\)]], ", but the same idea can be used for larger gaps." }], "Text"], Cell[BoxData[{ \(sq[inv[{1, 0}]]\ \[CircleTimes]\ fastFib[2^10, Full \[Rule] True]\ // \ First\), "\[IndentingNewLine]", \(%\ \[Equal] \ Fibonacci[1022]\)}], "Input"], Cell[BoxData[{ \(sq[sq[inv[{1, 0}]]]\ \[CircleTimes]\ fastFib[2^10, Full \[Rule] True]\ // \ First\), "\[IndentingNewLine]", \(%\ \[Equal] \ Fibonacci[1020]\)}], "Input"], Cell[TextData[{ "This still requires fewer group operations than using our monoid \ algorithm.\nNote that there is a difficult problem lurking in the dark: \ assuming that all group operations are ", Cell[BoxData[ \(TraditionalForm\`O(1)\)]], ", what is the most efficient way to calculate a Fibonacci number? But we \ won't get involved at this point. \nAlso note that for the purpose of \ computing Fibonacci numbers it suffices to deal with the subgroup generated \ by ", Cell[BoxData[ \(TraditionalForm\`\((1, 0)\)\)]], ". It is easy to see that ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]\ \((1, 0)\)\ \[RightAngleBracket]\ \[SubsetEqual] \ \ \ \[DoubleStruckCapitalN]\ \[Cross]\ \[DoubleStruckCapitalN]\ \[SubsetEqual] \ \ \[DoubleStruckCapitalQ]\ \[Cross]\ \[DoubleStruckCapitalQ]\)]], ", so we are dealing only with integers. " }], "Text"], Cell["(a + b Sqrt[5]) (c + d Sqrt[5])// Expand", "Input"], Cell["Clear[a,b,c,d]", "Input"], Cell["Reduce[ {a c + 5 b d == 1, b c + a d == 0}, {c,d} ]", "Input"], Cell[BoxData[ \(InputForm\`\(1 - \@5\ a\ d - 5\ b\ d\)\/\(a + \@5\ b\)\)], "Input"], Cell["% // FullSimplify", "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Actually, it's a Field", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:29"], Cell[TextData[{ "The operation in our monoid was\n\t\t", Cell[BoxData[ FormBox[ StyleBox[ RowBox[{ RowBox[{ RowBox[{ FormBox["(", "TraditionalForm"], \(a, b\), ")"}], " ", "*", " ", \((c, d)\)}], "=", " ", \((a\ d\ + \ b\ c\ + \ a\ c, \ a\ c\ + \ b\ d\ )\)}], Background->RGBColor[1, 1, 0]], TraditionalForm]]], ".\nwith neutral element ", Cell[BoxData[ \(TraditionalForm\`\((0, 1)\)\)]], ". \nThere is another natural operation on our carrier set: component-wise \ addition.\n \t\t", Cell[BoxData[ FormBox[ StyleBox[ RowBox[{ RowBox[{ RowBox[{ FormBox["(", "TraditionalForm"], \(a, b\), ")"}], " ", "+", " ", \((c, d)\)}], "=", " ", \((a + \ c, \ b + d\ )\)}], Background->RGBColor[1, 1, 0]], TraditionalForm]]], ".\nregardless of whether we deal with ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\[Cross]\ \[DoubleStruckCapitalN]\)]], " or ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalQ]\ \[Cross]\ \ \[DoubleStruckCapitalQ]\)]], ". \nMultiplication distributes over addition:" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[a, b, u, v, w, x]\), "\[IndentingNewLine]", \({a, b}\[CircleTimes]\(({u, v} + {w, x})\)\ == \ {a, b}\[CircleTimes]{u, v}\ + \ {a, b}\[CircleTimes]{w, x}\ // \ Simplify\)}], "Input"], Cell[TextData[{ "Hence we are dealing with a field ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalF]\)]], ". Note that our field contains a copy of the rationals: 1 corresponds to \ ", Cell[BoxData[ \(TraditionalForm\`\((0, 1)\)\)]], ", so ", Cell[BoxData[ \(TraditionalForm\`n\)]], " corresponds to ", Cell[BoxData[ \(TraditionalForm\`\((0, n)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\((0, n)\)\^\(-1\)\ = \ \((0, 1/n)\)\)]], ". Thus, any rational number ", Cell[BoxData[ \(TraditionalForm\`n/m\)]], " is represented in ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalF]\)]], " by ", Cell[BoxData[ \(TraditionalForm\`\((0, n/m)\)\)]], ". \nWhat is ", Cell[BoxData[ FormBox[ RowBox[{"a", " ", "=", " ", RowBox[{\((1, 0)\), Cell[""]}]}], TraditionalForm]]], "? Note that ", Cell[BoxData[ \(TraditionalForm\`1\/a = \ \(\((1, \(-1\))\)\ = \ \(a - \ \((0, 1)\)\ = \ a - 1\_\[DoubleStruckCapitalF]\)\)\)]], ". Thus, in the field ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalF]\)]], ", ", Cell[BoxData[ \(TraditionalForm\`a\)]], " solves the equation ", Cell[BoxData[ \(TraditionalForm\`x\^\(\(\ \)\(2\)\) - x\ - \ 1\ = \ 0\)]], ". But then ", Cell[BoxData[ \(TraditionalForm\`\@5\)]], " corresponds to ", Cell[BoxData[ \(TraditionalForm\`\((2, \(-1\))\)\)]], ". \nIt is tempting to suspect that ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalF]\)]], " might be an algebraic extension of ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalQ]\)]], ", and most likely isomorphic to ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalQ](\@5)\)]], ". It is not hard to come up with the appropriate isomorphism:\n\t\t", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\[DoubleStruckCapitalQ](\@5)\)\ \ \[LongRightArrow]\ \[DoubleStruckCapitalF]\)]], ", \t", Cell[BoxData[ \(TraditionalForm\`f(x + y \@ 5)\ = \ \((2 y, \ x - y)\)\)]], ". \nWe can verify the isomorphism properties. For addition, it is clear \ that ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is a homomorphism. Here is the test for multiplication." }], "Text"], Cell[BoxData[{ \(Clear[f, a, b, c, d]\), "\[IndentingNewLine]", \(\(f[ x_]\ := \ \[IndentingNewLine]Module[\ \ {xx, yy}, \[IndentingNewLine]\t xx\ = Coefficient[x, Sqrt[5]]; \[IndentingNewLine]\t yy\ = \ x\ - \ xx\ Sqrt[5]\ // \ Expand; \[IndentingNewLine]\t{\ 2\ xx, yy - xx\ }\[IndentingNewLine]\ ];\)\)}], "Input"], Cell[BoxData[{ \(f[1\ ]\), "\[IndentingNewLine]", \(f[\((1 + Sqrt[5])\)/2]\)}], "Input"], Cell[BoxData[{ \(f[\((a + b\ Sqrt[5])\) \((c\ + \ d\ Sqrt[5])\)]\), "\n", \(f[\((a + b\ Sqrt[5])\)]\[CircleTimes]f[\((c\ + \ d\ Sqrt[5])\)]\), "\[IndentingNewLine]", \(%\ \[Equal] \ %%\ // \ Simplify\)}], "Input"], Cell[TextData[{ "Another way to describe the field ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalF]\)]], " is as a subring of the matrix ring ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalQ]\^\(2, 2\)\)]], ". The matrix representing ", Cell[BoxData[ \(TraditionalForm\`\((x, y)\)\)]], " is \n\t\t", Cell[BoxData[ FormBox[ RowBox[{"(", GridBox[{ {\(x + y\), "x"}, {"x", "y"} }], ")"}], TraditionalForm]]], "\nThus ", Cell[BoxData[ \(TraditionalForm\`\((0, 1)\)\)]], " corresponds to the identity matrix, and ", Cell[BoxData[ \(TraditionalForm\`\((1, 0)\)\)]], " is the usual Fibonacci matrix\n\t\t", Cell[BoxData[ FormBox[ RowBox[{"(", GridBox[{ {"1", "1"}, {"1", "0"} }], ")"}], TraditionalForm]]], "\nAgain, we check that we have a homomorphism with respect to \ multiplication." }], "Text"], Cell[BoxData[ \(tomat[{x_, y_}]\ := \ {{x + y, x}, {x, y}}\)], "Input"], Cell[BoxData[{ \(tomat[{0, 1}] // \ MatrixForm\), "\[IndentingNewLine]", \(tomat[{1, 0}]\ // \ MatrixForm\)}], "Input"], Cell[BoxData[ \(\(tomat[{1, 0}]\ // \ Inverse\)\ // \ MatrixForm\)], "Input"], Cell[BoxData[ \({1, 0}\[CircleTimes]{1, \(-1\)}\)], "Input"], Cell[BoxData[{ \(\(tomat[{u, v}] . tomat[{w, x}]\ // \ Expand\)\ // \ MatrixForm\), "\[IndentingNewLine]", \(\(tomat[{u, v}\[CircleTimes]{w, x}]\ // \ Expand\)\ // \ MatrixForm\), "\[IndentingNewLine]", \(%\ \[Equal] %%\)}], "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" More Recurrences", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->{"More Problems", "c:30"}], Cell[CellGroupData[{ Cell["Degree 4", "Subsection", CellTags->"c:31"], Cell["p = (1+ Sqrt[5])/2;", "Input"], Cell["\<\ t = Fibonacci[n]^4 - Fibonacci[n-2] Fibonacci[n-1] Fibonacci[n+1] \ Fibonacci[n+2] - 1\ \>", "Input"], Cell["tt = t /. Fibonacci[n_] :> (p^n - (-1)^n/p^n)/Sqrt[5]", "Input"], Cell["tt // Expand", "Input"], Cell["% // Together", "Input"], Cell["%[[5]]", "Input"], Cell["% /. (-1)^2n -> 1", "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Pell Numbers", "Subsection", CellTags->"c:32"], Cell[TextData[{ StyleBox["Suppose we modify our basic recurrence to read", FontFamily->"Times"], "\n\t", Cell[BoxData[ \(TraditionalForm\`\[Bullet]\ \ \ P\_0\ \ = \ 0, \n\[Bullet]\ \ \ P\_1\ \ = \ 1, \n\[Bullet]\ \ \ P\_\(n + 1\) = \ 2\ P\_n\ + \(\(P\_\(n - 1\)\)\(.\)\)\)]], "\nThese numbers are called Pell numbers. What properties do they have? " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[P] P[0] = 0; P[1] = 1; P[n_Integer] := P[n] = 2 P[n-1] + P[n-2];\ \>", "Input", AspectRatioFixed->True], Cell["P /@ Range[20]", "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Fibonacci Polynomials", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->{"More Problems", "c:33"}], Cell[CellGroupData[{ Cell["A Binary Version", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:34"], Cell[TextData[{ StyleBox["Here is a variant of the Fibonacci number, dressed up as \ polynomials.\n", FontFamily->"Times"], "\t", Cell[BoxData[ \(TraditionalForm\`\[Pi]\_0\ = \ 0\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\[Pi]\_1\ = \ 1\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\[Pi]\_n\ = \ \ x\ \ \[Pi]\_\(n - 1\)\ + \ \ \[Pi]\ \_\(n - 2\)\)]], "\n", StyleBox["According to this definition, the we obtain integer polynomials. \ However, it is slightly more interesting to take all these polynomials modulo \ 2, so that all coefficients are 0 or 1. Note that in this arithmetic ", FontFamily->"Times"], StyleBox["1 + 1 = 0", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[". \n", FontFamily->"Times"], "For example, \n\t", Cell[BoxData[ \(TraditionalForm\`\[Pi]\_\(\(2\)\(\ \)\)\ = \ \(x\ \[Pi]\_1 + \ \[Pi]\ \_0\ = \ \(x\ 1\ + \ 0\ = \ x\)\)\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\[Pi]\_3\ = \ \(x\ \[Pi]\_2 + \ \[Pi]\_1\ = \ \(x\ \ x\ + \ 1\ = \ x\^2 + \ 1\)\)\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`\[Pi]\_4\ = \ \(x\ \[Pi]\_3 + \ \[Pi]\_2\ = \ \(x\ \ \((x\^2 + 1)\)\ + \ x\ = \ \(x\^3 + x + \ x\ = x\^3\)\)\)\)]], "\nWrite a function to do this. First, the plain integer version." }], "Text"], Cell[BoxData[{ \(Clear[pi]\), "\n", \(pi[0] = 0; \), "\n", \(pi[1] = 1; \), "\n", \(pi[n_] := \(pi[n] = x\ pi[n - 1] + pi[n - 2]\); \)}], "Input"], Cell["Table[ pi[i], {i,0,10} ] // Expand // TableForm", "Input"], Cell["Now everything modulo 2. ", "Text"], Cell[BoxData[{ \(mod2[pp_] := PolynomialMod[pp, 2]; \), "\n", \(Clear[pi]\), "\n", \(pi[0] = 0; \), "\n", \(pi[1] = 1; \), "\n", \(pi[n_] := \(pi[n] = mod2[Expand[x\ pi[n - 1] + pi[n - 2]]]\); \)}], "Input"], Cell["Table[ pi[i], {i,0,20} ] // TableForm", "Input"], Cell[TextData[{ StyleBox["\nClaim:", FontWeight->"Bold"], " For all ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ m\ < \ n\)]], ": ", Cell[BoxData[ \(TraditionalForm\`\[Pi]\_n\ = \ \ \[Pi]\_\(m + 1\)\ \[Pi]\_\(n - m\)\ \ + \ \[Pi]\_m\ \[Pi]\_\(n - m - 1\)\)]], "\nHere is a little test. " }], "Text"], Cell[BoxData[{ \(n = 10; m = 5; \), "\n", \(pi[n]\), "\n", \(pi[m + 1]\ pi[n - m] + pi[m]\ pi[n - m - 1]\), "\n", \(mod2[%] \[Equal] mod2[%%]\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Closed Form", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:35"], Cell[TextData[StyleBox["For the \[Pi] polynomials there is a closed form \ description of the coefficients, but it involves binomial coeffients: ", FontFamily->"Times"]], "Text"], Cell["pi[30]", "Input"], Cell["CoefficientList[ pi[30], x ]", "Input"], Cell["To get a nice picture, we have to pad the lists.", "Text"], Cell[BoxData[{ \(pic = Table[PadRight[CoefficientList[pi[i], x], 50], {i, 50}]; \), "\n", \(PlotMatrix[pic]; \)}], "Input"], Cell["\<\ Somewhat surprising. This looks much like the binomial \ coefficients, modulo 2, but the arrangement of the grid is slightly \ different.\ \>", "Text"], Cell[BoxData[{ \(\(bc = Table[Mod[Binomial[i, j], 2], {i, 0, 32}, {j, 0, 32}];\)\), "\n", \(\(PlotMatrix[bc];\)\)}], "Input"], Cell["\<\ At any rate, one might hope to find some reasonable description in \ terms of binomial coefficients. Some minor fumbling is necessary to make the \ transformation from one grid to the other. \ \>", "Text"], Cell[TextData[{ StyleBox["Claim", FontWeight->"Bold"], ": ", Cell[BoxData[ FormBox[ RowBox[{\(\(\[Pi]\_\(\(\ \)\(n\)\)\)(x)\), " ", "=", " ", RowBox[{\(\[Sum]\_\(i = 0\)\%\(\(\ \)\(m\)\)\), " ", RowBox[{ RowBox[{"(", "\[NegativeThinSpace]", GridBox[{ {\(n - i - 1\)}, {"i"} }], "\[NegativeThinSpace]", ")"}], " ", \(x\^\(\(\ \)\(n\ - i - 1\)\)\)}]}]}], TraditionalForm]]], " where ", Cell[BoxData[ \(TraditionalForm\`m\ = \ \[LeftFloor]\((n - 1)\)/2\[RightFloor]\)]], "." }], "Text"], Cell[BoxData[{ \(nn = 18; \), "\n", \(pi[nn]\), "\n", \(\[Sum]\+\(j = 0\)\%\(Floor[\(nn - 1\)\/2]\)Binomial[nn - j - 1, j]\ x\^\(nn - 2\ j - 1\)\), "\n", \(mod2[%] === \ pi[nn]\)}], "Input"], Cell["Can you prove the claim?", "Text"] }, Closed]] }, Closed]] }, Closed]] }, FrontEndVersion->"5.0 for X", ScreenRectangle->{{0, 1280}, {0, 1024}}, ScreenStyleEnvironment->"Working", WindowSize->{1167, 998}, WindowMargins->{{0, Automatic}, {Automatic, 0}}, PrintingStartingPageNumber->191, IndexCreationOptions->{"Format"->"Hyperlinks"}, Magnification->2, StyleDefinitions -> "Demo.nb" ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{ "c:1"->{ Cell[1800, 53, 90, 2, 118, "Title", CellTags->"c:1"]}, "c:2"->{ Cell[1915, 59, 68, 1, 159, "Section", CellTags->"c:2"]}, "Definition Fibonacci"->{ Cell[2008, 64, 134, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Definition Fibonacci", "c:3"}]}, "c:3"->{ Cell[2008, 64, 134, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Definition Fibonacci", "c:3"}]}, "Recursive Computation"->{ Cell[3966, 114, 157, 3, 73, "Subsection", Evaluatable->False, CellTags->{"Recursive Computation", "c:4"}]}, "c:4"->{ Cell[3966, 114, 157, 3, 73, "Subsection", Evaluatable->False, CellTags->{"Recursive Computation", "c:4"}]}, "Dynamic Programming"->{ Cell[8894, 268, 134, 3, 85, "Subsection", Evaluatable->False, CellTags->{"Dynamic Programming", "c:5"}]}, "c:5"->{ Cell[8894, 268, 134, 3, 85, "Subsection", Evaluatable->False, CellTags->{"Dynamic Programming", "c:5"}]}, "Iterative Computation"->{ Cell[10028, 307, 138, 3, 69, "Subsection", Evaluatable->False, CellTags->{"Iterative Computation", "c:6"}]}, "c:6"->{ Cell[10028, 307, 138, 3, 69, "Subsection", Evaluatable->False, CellTags->{"Iterative Computation", "c:6"}]}, "c:7"->{ Cell[11373, 352, 117, 3, 93, "Section", Evaluatable->False, CellTags->"c:7"]}, "Binet Formula"->{ Cell[11515, 359, 131, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Binet Formula", "c:8"}]}, "c:8"->{ Cell[11515, 359, 131, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Binet Formula", "c:8"}]}, "c:9"->{ Cell[17161, 557, 137, 5, 91, "Subsubsection", CellTags->"c:9"]}, "Golden Ratio"->{ Cell[18307, 606, 125, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Golden Ratio", "c:10"}]}, "c:10"->{ Cell[18307, 606, 125, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Golden Ratio", "c:10"}]}, "Identities"->{ Cell[20559, 687, 131, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Identities", "c:11"}]}, "c:11"->{ Cell[20559, 687, 131, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Identities", "c:11"}]}, "c:12"->{ Cell[21010, 701, 49, 1, 91, "Subsubsection", CellTags->"c:12"]}, "c:13"->{ Cell[23453, 795, 73, 1, 91, "Subsubsection", CellTags->"c:13"]}, "c:14"->{ Cell[24381, 832, 61, 1, 91, "Subsubsection", CellTags->"c:14"]}, "c:15"->{ Cell[25921, 885, 58, 1, 73, "Subsubsection", CellTags->"c:15"]}, "c:16"->{ Cell[26906, 926, 51, 1, 73, "Subsubsection", CellTags->"c:16"]}, "c:17"->{ Cell[30493, 1040, 59, 1, 73, "Subsubsection", CellTags->"c:17"]}, "Extended Recurrence"->{ Cell[31932, 1088, 136, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Extended Recurrence", "c:18"}]}, "c:18"->{ Cell[31932, 1088, 136, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Extended Recurrence", "c:18"}]}, "Matrix Computation"->{ Cell[33373, 1133, 146, 3, 73, "Subsection", Evaluatable->False, CellTags->{"Matrix Computation", "c:19"}]}, "c:19"->{ Cell[33373, 1133, 146, 3, 73, "Subsection", Evaluatable->False, CellTags->{"Matrix Computation", "c:19"}]}, "Fast Fibonacci"->{ Cell[37762, 1283, 142, 3, 93, "Section", Evaluatable->False, CellTags->{"Fast Fibonacci", "c:20"}]}, "c:20"->{ Cell[37762, 1283, 142, 3, 93, "Section", Evaluatable->False, CellTags->{"Fast Fibonacci", "c:20"}]}, "1/2 Problem"->{ Cell[39106, 1321, 142, 3, 85, "Subsection", Evaluatable->False, CellTags->{"1/2 Problem", "c:21"}], Cell[55180, 1806, 130, 3, 87, "Subsubsection", Evaluatable->False, CellTags->{"1/2 Problem", "c:26"}]}, "c:21"->{ Cell[39106, 1321, 142, 3, 85, "Subsection", Evaluatable->False, CellTags->{"1/2 Problem", "c:21"}]}, "c:22"->{ Cell[42538, 1416, 106, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:22"]}, "c:23"->{ Cell[46489, 1544, 105, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:23"]}, "Fast Fibonacci Algorithm"->{ Cell[50488, 1671, 158, 3, 69, "Subsection", Evaluatable->False, CellTags->{"Fast Fibonacci Algorithm", "c:24"}]}, "c:24"->{ Cell[50488, 1671, 158, 3, 69, "Subsection", Evaluatable->False, CellTags->{"Fast Fibonacci Algorithm", "c:24"}]}, "Fibonacci Group"->{ Cell[54797, 1793, 134, 3, 93, "Section", Evaluatable->False, CellTags->{"Fibonacci Group", "c:25"}]}, "c:25"->{ Cell[54797, 1793, 134, 3, 93, "Section", Evaluatable->False, CellTags->{"Fibonacci Group", "c:25"}]}, "c:26"->{ Cell[55180, 1806, 130, 3, 87, "Subsubsection", Evaluatable->False, CellTags->{"1/2 Problem", "c:26"}]}, "c:27"->{ Cell[57649, 1884, 113, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:27"]}, "c:28"->{ Cell[63121, 2056, 107, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:28"]}, "c:29"->{ Cell[68619, 2239, 115, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:29"]}, "More Problems"->{ Cell[75092, 2442, 123, 3, 93, "Section", Evaluatable->False, CellTags->{"More Problems", "c:30"}], Cell[76381, 2501, 130, 3, 87, "Subsection", Evaluatable->False, CellTags->{"More Problems", "c:33"}]}, "c:30"->{ Cell[75092, 2442, 123, 3, 93, "Section", Evaluatable->False, CellTags->{"More Problems", "c:30"}]}, "c:31"->{ Cell[75240, 2449, 50, 1, 87, "Subsection", CellTags->"c:31"]}, "c:32"->{ Cell[75681, 2472, 54, 1, 87, "Subsection", CellTags->"c:32"]}, "c:33"->{ Cell[76381, 2501, 130, 3, 87, "Subsection", Evaluatable->False, CellTags->{"More Problems", "c:33"}]}, "c:34"->{ Cell[76536, 2508, 109, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:34"]}, "c:35"->{ Cell[79136, 2594, 104, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:35"]} } *) (*CellTagsIndex CellTagsIndex->{ {"c:1", 81930, 2684}, {"c:2", 82006, 2687}, {"Definition Fibonacci", 82101, 2690}, {"c:3", 82234, 2694}, {"Recursive Computation", 82385, 2698}, {"c:4", 82520, 2702}, {"Dynamic Programming", 82671, 2706}, {"c:5", 82804, 2710}, {"Iterative Computation", 82955, 2714}, {"c:6", 83091, 2718}, {"c:7", 83227, 2722}, {"Binet Formula", 83343, 2726}, {"c:8", 83471, 2730}, {"c:9", 83599, 2734}, {"Golden Ratio", 83694, 2737}, {"c:10", 83823, 2741}, {"Identities", 83958, 2745}, {"c:11", 84085, 2749}, {"c:12", 84212, 2753}, {"c:13", 84299, 2756}, {"c:14", 84386, 2759}, {"c:15", 84473, 2762}, {"c:16", 84560, 2765}, {"c:17", 84647, 2768}, {"Extended Recurrence", 84750, 2771}, {"c:18", 84887, 2775}, {"Matrix Computation", 85038, 2779}, {"c:19", 85174, 2783}, {"Fast Fibonacci", 85320, 2787}, {"c:20", 85449, 2791}, {"1/2 Problem", 85585, 2795}, {"c:21", 85833, 2802}, {"c:22", 85962, 2806}, {"c:23", 86077, 2810}, {"Fast Fibonacci Algorithm", 86212, 2814}, {"c:24", 86354, 2818}, {"Fibonacci Group", 86507, 2822}, {"c:25", 86637, 2826}, {"c:26", 86767, 2830}, {"c:27", 86899, 2834}, {"c:28", 87014, 2838}, {"c:29", 87129, 2842}, {"More Problems", 87253, 2846}, {"c:30", 87499, 2853}, {"c:31", 87627, 2857}, {"c:32", 87712, 2860}, {"c:33", 87797, 2863}, {"c:34", 87928, 2867}, {"c:35", 88043, 2871} } *) (*NotebookFileOutline Notebook[{ Cell[1754, 51, 43, 0, 44, "RCS"], Cell[1800, 53, 90, 2, 118, "Title", CellTags->"c:1"], Cell[CellGroupData[{ Cell[1915, 59, 68, 1, 159, "Section", CellTags->"c:2"], Cell[CellGroupData[{ Cell[2008, 64, 134, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Definition Fibonacci", "c:3"}], Cell[2145, 69, 576, 11, 171, "Text"], Cell[2724, 82, 667, 9, 229, "Text"], Cell[3394, 93, 535, 16, 518, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[3966, 114, 157, 3, 73, "Subsection", Evaluatable->False, CellTags->{"Recursive Computation", "c:4"}], Cell[4126, 119, 1145, 24, 525, "Text"], Cell[5274, 145, 331, 9, 137, "Text"], Cell[5608, 156, 186, 5, 150, "Input"], Cell[5797, 163, 85, 2, 59, "Input"], Cell[5885, 167, 348, 7, 105, "Text", Evaluatable->False], Cell[6236, 176, 79, 1, 58, "Input"], Cell[6318, 179, 162, 5, 59, "Input"], Cell[6483, 186, 195, 6, 60, "Text", Evaluatable->False], Cell[6681, 194, 47, 0, 58, "Input"], Cell[6731, 196, 314, 6, 182, "Input"], Cell[7048, 204, 127, 3, 59, "Input"], Cell[7178, 209, 219, 5, 121, "Input"], Cell[7400, 216, 559, 11, 238, "Text", Evaluatable->False], Cell[7962, 229, 188, 5, 175, "Input"], Cell[8153, 236, 86, 2, 85, "Input"], Cell[8242, 240, 201, 5, 82, "Text", Evaluatable->False], Cell[8446, 247, 20, 0, 83, "Input"], Cell[8469, 249, 228, 6, 82, "Text", Evaluatable->False], Cell[8700, 257, 81, 2, 85, "Input"], Cell[8784, 261, 73, 2, 85, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[8894, 268, 134, 3, 85, "Subsection", Evaluatable->False, CellTags->{"Dynamic Programming", "c:5"}], Cell[9031, 273, 514, 10, 130, "Text"], Cell[9548, 285, 221, 6, 213, "Input"], Cell[9772, 293, 33, 0, 58, "Input"], Cell[9808, 295, 146, 5, 54, "Text"], Cell[9957, 302, 34, 0, 58, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[10028, 307, 138, 3, 69, "Subsection", Evaluatable->False, CellTags->{"Iterative Computation", "c:6"}], Cell[10169, 312, 344, 11, 86, "Text", Evaluatable->False], Cell[10516, 325, 190, 4, 121, "Input"], Cell[10709, 331, 52, 1, 59, "Input"], Cell[10764, 334, 50, 1, 59, "Input"], Cell[10817, 337, 507, 9, 267, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[11373, 352, 117, 3, 93, "Section", Evaluatable->False, CellTags->"c:7"], Cell[CellGroupData[{ Cell[11515, 359, 131, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Binet Formula", "c:8"}], Cell[11649, 364, 678, 20, 187, "Text", Evaluatable->False], Cell[12330, 386, 134, 3, 59, "Input"], Cell[12467, 391, 925, 25, 286, "Text", Evaluatable->False], Cell[13395, 418, 79, 2, 58, "Input"], Cell[13477, 422, 44, 0, 58, "Input"], Cell[13524, 424, 424, 11, 79, "Text"], Cell[13951, 437, 91, 3, 85, "Input"], Cell[14045, 442, 226, 6, 83, "Text"], Cell[14274, 450, 84, 3, 58, "Input"], Cell[14361, 455, 399, 9, 162, "Text"], Cell[14763, 466, 70, 2, 58, "Input"], Cell[14836, 470, 61, 0, 54, "Text"], Cell[14900, 472, 72, 2, 58, "Input"], Cell[14975, 476, 298, 7, 178, "Text"], Cell[15276, 485, 69, 2, 58, "Input"], Cell[15348, 489, 67, 0, 54, "Text"], Cell[15418, 491, 95, 3, 58, "Input"], Cell[15516, 496, 64, 0, 54, "Text"], Cell[15583, 498, 103, 3, 58, "Input"], Cell[15689, 503, 84, 1, 59, "Input"], Cell[15776, 506, 63, 1, 59, "Input"], Cell[15842, 509, 231, 6, 79, "Text"], Cell[16076, 517, 107, 3, 58, "Input"], Cell[16186, 522, 597, 19, 355, "Text"], Cell[16786, 543, 350, 10, 137, "Text"], Cell[CellGroupData[{ Cell[17161, 557, 137, 5, 91, "Subsubsection", CellTags->"c:9"], Cell[17301, 564, 205, 5, 54, "Text"], Cell[17509, 571, 65, 4, 111, "Input"], Cell[17577, 577, 511, 16, 99, "Text"], Cell[18091, 595, 66, 1, 59, "Input"], Cell[18160, 598, 62, 0, 58, "Input"], Cell[18225, 600, 33, 0, 54, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[18307, 606, 125, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Golden Ratio", "c:10"}], Cell[18435, 611, 728, 19, 138, "Text", Evaluatable->False], Cell[19166, 632, 117, 3, 133, "Input"], Cell[19286, 637, 278, 9, 73, "Text", Evaluatable->False], Cell[19567, 648, 65, 0, 58, "Input"], Cell[19635, 650, 73, 0, 54, "Text"], Cell[19711, 652, 30, 0, 58, "Input"], Cell[19744, 654, 232, 5, 95, "Text"], Cell[19979, 661, 293, 10, 218, "Input"], Cell[20275, 673, 165, 5, 54, "Text", Evaluatable->False], Cell[20443, 680, 79, 2, 59, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[20559, 687, 131, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Identities", "c:11"}], Cell[20693, 692, 292, 5, 79, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[21010, 701, 49, 1, 91, "Subsubsection", CellTags->"c:12"], Cell[21062, 704, 162, 4, 54, "Text", Evaluatable->False], Cell[21227, 710, 102, 2, 59, "Input"], Cell[21332, 714, 81, 2, 59, "Input"], Cell[21416, 718, 150, 3, 90, "Input"], Cell[21569, 723, 325, 11, 221, "Text"], Cell[21897, 736, 151, 3, 54, "Text", Evaluatable->False], Cell[22051, 741, 110, 2, 59, "Input"], Cell[22164, 745, 81, 2, 59, "Input"], Cell[22248, 749, 335, 11, 221, "Text"], Cell[22586, 762, 185, 4, 54, "Text", Evaluatable->False], Cell[22774, 768, 132, 3, 59, "Input"], Cell[22909, 773, 81, 2, 59, "Input"], Cell[22993, 777, 423, 13, 234, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[23453, 795, 73, 1, 91, "Subsubsection", CellTags->"c:13"], Cell[23529, 798, 543, 17, 222, "Text", Evaluatable->False], Cell[24075, 817, 140, 3, 70, "Input"], Cell[24218, 822, 126, 5, 137, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[24381, 832, 61, 1, 91, "Subsubsection", CellTags->"c:14"], Cell[24445, 835, 229, 4, 53, "Text", Evaluatable->False], Cell[24677, 841, 109, 2, 59, "Input"], Cell[24789, 845, 438, 12, 86, "Text", Evaluatable->False], Cell[25230, 859, 129, 3, 59, "Input"], Cell[25362, 864, 158, 3, 53, "Text", Evaluatable->False], Cell[25523, 869, 361, 11, 250, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[25921, 885, 58, 1, 73, "Subsubsection", CellTags->"c:15"], Cell[25982, 888, 406, 8, 310, "Text"], Cell[26391, 898, 91, 5, 138, "Input"], Cell[26485, 905, 68, 3, 85, "Input"], Cell[26556, 910, 313, 11, 250, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[26906, 926, 51, 1, 73, "Subsubsection", CellTags->"c:16"], Cell[26960, 929, 894, 26, 283, "Text", Evaluatable->False], Cell[27857, 957, 148, 4, 126, "Input"], Cell[28008, 963, 2167, 62, 563, "Text", Evaluatable->False], Cell[30178, 1027, 278, 8, 86, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[30493, 1040, 59, 1, 73, "Subsubsection", CellTags->"c:17"], Cell[30555, 1043, 629, 18, 341, "Text", Evaluatable->False], Cell[31187, 1063, 103, 2, 85, "Input"], Cell[31293, 1067, 25, 0, 58, "Input"], Cell[31321, 1069, 474, 10, 185, "Text", Evaluatable->False], Cell[31798, 1081, 85, 1, 85, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[31932, 1088, 136, 3, 87, "Subsection", Evaluatable->False, CellTags->{"Extended Recurrence", "c:18"}], Cell[32071, 1093, 1265, 35, 727, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[33373, 1133, 146, 3, 73, "Subsection", Evaluatable->False, CellTags->{"Matrix Computation", "c:19"}], Cell[33522, 1138, 1973, 51, 643, "Text", Evaluatable->False], Cell[35498, 1191, 55, 3, 85, "Input"], Cell[35556, 1196, 39, 0, 58, "Input"], Cell[35598, 1198, 263, 6, 121, "Text"], Cell[35864, 1206, 64, 0, 58, "Input"], Cell[35931, 1208, 638, 20, 109, "Text"], Cell[36572, 1230, 51, 3, 85, "Input"], Cell[36626, 1235, 114, 5, 54, "Text"], Cell[36743, 1242, 115, 2, 90, "Input"], Cell[36861, 1246, 234, 5, 79, "Text"], Cell[37098, 1253, 92, 3, 85, "Input"], Cell[37193, 1258, 168, 5, 54, "Text"], Cell[37364, 1265, 78, 3, 85, "Input"], Cell[37445, 1270, 268, 7, 70, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[37762, 1283, 142, 3, 93, "Section", Evaluatable->False, CellTags->{"Fast Fibonacci", "c:20"}], Cell[37907, 1288, 1174, 29, 351, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[39106, 1321, 142, 3, 85, "Subsection", Evaluatable->False, CellTags->{"1/2 Problem", "c:21"}], Cell[39251, 1326, 3262, 86, 711, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[42538, 1416, 106, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:22"], Cell[42647, 1421, 185, 5, 54, "Text", Evaluatable->False], Cell[42835, 1428, 331, 8, 223, "Input"], Cell[43169, 1438, 96, 3, 90, "Input"], Cell[43268, 1443, 90, 2, 59, "Input"], Cell[43361, 1447, 102, 2, 59, "Input"], Cell[43466, 1451, 790, 24, 206, "Text", Evaluatable->False], Cell[44259, 1477, 212, 4, 121, "Input"], Cell[44474, 1483, 507, 13, 162, "Text", Evaluatable->False], Cell[44984, 1498, 509, 11, 243, "Input"], Cell[45496, 1511, 956, 28, 219, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[46489, 1544, 105, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:23"], Cell[46597, 1549, 176, 5, 54, "Text", Evaluatable->False], Cell[46776, 1556, 148, 5, 151, "Input"], Cell[46927, 1563, 148, 5, 54, "Text", Evaluatable->False], Cell[47078, 1570, 148, 5, 151, "Input"], Cell[47229, 1577, 490, 12, 109, "Text", Evaluatable->False], Cell[47722, 1591, 145, 4, 85, "Input"], Cell[47870, 1597, 2232, 60, 543, "Text", Evaluatable->False], Cell[50105, 1659, 334, 6, 79, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[50488, 1671, 158, 3, 69, "Subsection", Evaluatable->False, CellTags->{"Fast Fibonacci Algorithm", "c:24"}], Cell[50649, 1676, 774, 15, 237, "Text", Evaluatable->False], Cell[51426, 1693, 451, 11, 272, "Input"], Cell[51880, 1706, 39, 0, 83, "Input"], Cell[51922, 1708, 77, 2, 85, "Input"], Cell[52002, 1712, 37, 0, 83, "Input"], Cell[52042, 1714, 2706, 73, 565, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[54797, 1793, 134, 3, 93, "Section", Evaluatable->False, CellTags->{"Fibonacci Group", "c:25"}], Cell[54934, 1798, 221, 4, 54, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[55180, 1806, 130, 3, 87, "Subsubsection", Evaluatable->False, CellTags->{"1/2 Problem", "c:26"}], Cell[55313, 1811, 1834, 46, 449, "Text", Evaluatable->False], Cell[57150, 1859, 217, 13, 315, "Program", Evaluatable->False], Cell[57370, 1874, 242, 5, 79, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[57649, 1884, 113, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:27"], Cell[57765, 1889, 889, 25, 203, "Text", Evaluatable->False], Cell[58657, 1916, 361, 6, 151, "Input"], Cell[59021, 1924, 61, 1, 59, "Input"], Cell[59085, 1927, 59, 1, 59, "Input"], Cell[59147, 1930, 56, 0, 54, "Text"], Cell[59206, 1932, 56, 1, 59, "Input"], Cell[59265, 1935, 29, 0, 54, "Text"], Cell[59297, 1937, 221, 4, 90, "Input"], Cell[59521, 1943, 31, 0, 54, "Text"], Cell[59555, 1945, 126, 2, 59, "Input"], Cell[59684, 1949, 64, 0, 54, "Text"], Cell[59751, 1951, 110, 2, 59, "Input"], Cell[59864, 1955, 269, 5, 79, "Text", Evaluatable->False], Cell[60136, 1962, 59, 1, 59, "Input"], Cell[60198, 1965, 180, 4, 54, "Text", Evaluatable->False], Cell[60381, 1971, 135, 2, 90, "Input"], Cell[60519, 1975, 104, 2, 59, "Input"], Cell[60626, 1979, 70, 0, 54, "Text"], Cell[60699, 1981, 104, 2, 59, "Input"], Cell[60806, 1985, 165, 5, 54, "Text"], Cell[60974, 1992, 145, 3, 90, "Input"], Cell[61122, 1997, 115, 2, 59, "Input"], Cell[61240, 2001, 184, 4, 79, "Text"], Cell[61427, 2007, 874, 15, 489, "Input"], Cell[62304, 2024, 81, 2, 54, "Text", Evaluatable->False], Cell[62388, 2028, 60, 1, 59, "Input"], Cell[62451, 2031, 135, 3, 121, "Input"], Cell[62589, 2036, 105, 2, 59, "Input"], Cell[62697, 2040, 193, 3, 121, "Input"], Cell[62893, 2045, 91, 2, 90, "Input"], Cell[62987, 2049, 97, 2, 54, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[63121, 2056, 107, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:28"], Cell[63231, 2061, 628, 19, 178, "Text", Evaluatable->False], Cell[63862, 2082, 103, 2, 59, "Input"], Cell[63968, 2086, 52, 1, 59, "Input"], Cell[64023, 2089, 50, 0, 58, "Input"], Cell[64076, 2091, 34, 0, 58, "Input"], Cell[64113, 2093, 215, 6, 79, "Text", Evaluatable->False], Cell[64331, 2101, 181, 4, 59, "Input"], Cell[64515, 2107, 123, 2, 90, "Input"], Cell[64641, 2111, 91, 2, 90, "Input"], Cell[64735, 2115, 86, 2, 90, "Input"], Cell[64824, 2119, 631, 21, 137, "Text", Evaluatable->False], Cell[65458, 2142, 120, 2, 90, "Input"], Cell[65581, 2146, 987, 29, 229, "Text", Evaluatable->False], Cell[66571, 2177, 101, 2, 59, "Input"], Cell[66675, 2181, 70, 1, 59, "Input"], Cell[66748, 2184, 232, 6, 79, "Text"], Cell[66983, 2192, 193, 4, 90, "Input"], Cell[67179, 2198, 197, 4, 90, "Input"], Cell[67379, 2204, 910, 19, 187, "Text"], Cell[68292, 2225, 57, 0, 58, "Input"], Cell[68352, 2227, 31, 0, 58, "Input"], Cell[68386, 2229, 69, 0, 58, "Input"], Cell[68458, 2231, 87, 1, 117, "Input"], Cell[68548, 2234, 34, 0, 58, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[68619, 2239, 115, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:29"], Cell[68737, 2244, 1345, 39, 302, "Text", Evaluatable->False], Cell[70085, 2285, 251, 5, 121, "Input"], Cell[70339, 2292, 2342, 71, 373, "Text"], Cell[72684, 2365, 387, 7, 243, "Input"], Cell[73074, 2374, 97, 2, 90, "Input"], Cell[73174, 2378, 244, 4, 121, "Input"], Cell[73421, 2384, 989, 32, 258, "Text"], Cell[74413, 2418, 76, 1, 59, "Input"], Cell[74492, 2421, 129, 2, 90, "Input"], Cell[74624, 2425, 83, 1, 59, "Input"], Cell[74710, 2428, 64, 1, 59, "Input"], Cell[74777, 2431, 266, 5, 121, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[75092, 2442, 123, 3, 93, "Section", Evaluatable->False, CellTags->{"More Problems", "c:30"}], Cell[CellGroupData[{ Cell[75240, 2449, 50, 1, 87, "Subsection", CellTags->"c:31"], Cell[75293, 2452, 36, 0, 58, "Input"], Cell[75332, 2454, 111, 3, 85, "Input"], Cell[75446, 2459, 70, 0, 58, "Input"], Cell[75519, 2461, 29, 0, 58, "Input"], Cell[75551, 2463, 30, 0, 58, "Input"], Cell[75584, 2465, 23, 0, 58, "Input"], Cell[75610, 2467, 34, 0, 58, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[75681, 2472, 54, 1, 87, "Subsection", CellTags->"c:32"], Cell[75738, 2475, 448, 11, 201, "Text", Evaluatable->False], Cell[76189, 2488, 121, 6, 138, "Input"], Cell[76313, 2496, 31, 0, 58, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[76381, 2501, 130, 3, 87, "Subsection", Evaluatable->False, CellTags->{"More Problems", "c:33"}], Cell[CellGroupData[{ Cell[76536, 2508, 109, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:34"], Cell[76648, 2513, 1346, 37, 451, "Text"], Cell[77997, 2552, 165, 4, 151, "Input"], Cell[78165, 2558, 65, 0, 58, "Input"], Cell[78233, 2560, 41, 0, 54, "Text"], Cell[78277, 2562, 240, 6, 182, "Input"], Cell[78520, 2570, 55, 0, 58, "Input"], Cell[78578, 2572, 344, 11, 137, "Text"], Cell[78925, 2585, 174, 4, 151, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[79136, 2594, 104, 3, 87, "Subsubsection", Evaluatable->False, CellTags->"c:35"], Cell[79243, 2599, 180, 2, 54, "Text"], Cell[79426, 2603, 23, 0, 58, "Input"], Cell[79452, 2605, 45, 0, 58, "Input"], Cell[79500, 2607, 64, 0, 54, "Text"], Cell[79567, 2609, 139, 3, 90, "Input"], Cell[79709, 2614, 161, 4, 79, "Text"], Cell[79873, 2620, 143, 3, 90, "Input"], Cell[80019, 2625, 215, 4, 79, "Text"], Cell[80237, 2631, 649, 19, 87, "Text"], Cell[80889, 2652, 220, 5, 246, "Input"], Cell[81112, 2659, 40, 0, 54, "Text"] }, Closed]] }, Closed]] }, Closed]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)