(************** 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[ 51470, 1448]*) (*NotebookOutlinePosition[ 52160, 1472]*) (* CellTagsIndexPosition[ 52116, 1468]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell["CFSum: A Program for Summing C-Finite Sequences", "Title"], Cell["\<\ Herbert Wilf Curtis Greene December 2004\ \>", "Text", FontSize->16, FontSlant->"Italic"], Cell[CellGroupData[{ Cell["Introduction", "Subsection"], Cell[TextData[{ "This is a program for evaluating sums S(n) = ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\_i\)]], " ", Cell[BoxData[ \(TraditionalForm\`F\_1\)]], "(", Cell[BoxData[ \(TraditionalForm\`a\_1\)]], "n + ", Cell[BoxData[ \(TraditionalForm\`b\_1\)]], "j + ", Cell[BoxData[ \(TraditionalForm\`c\_1\)]], ")\[CenterEllipsis]", Cell[BoxData[ \(TraditionalForm\`F\_k\)]], "(", Cell[BoxData[ \(TraditionalForm\`a\_k\)]], "n + ", Cell[BoxData[ \(TraditionalForm\`b\_k\)]], "j + ", Cell[BoxData[ \(TraditionalForm\`c\_k\)]], ") in closed form, where the functions ", Cell[BoxData[ \(TraditionalForm\`F\_j\)]], " are C-finite, i.e., each ", Cell[BoxData[ \(TraditionalForm\`F\_j\)]], " satisfies a linear recurrence of degree D(j) < \[Infinity] with constant \ coefficients.The output is a linear combination of the terms of the form ", Cell[BoxData[ \(TraditionalForm\`F\_1\)]], "(", Cell[BoxData[ \(TraditionalForm\`\((a\_1\)\)]], "+ ", Cell[BoxData[ \(TraditionalForm\`b\_1\)]], " )n +", Cell[BoxData[ \(TraditionalForm\`i\_1\)]], ")\[CenterEllipsis]", Cell[BoxData[ \(TraditionalForm\`F\_k\)]], "(", Cell[BoxData[ \(TraditionalForm\`\((a\_k\)\)]], " + ", Cell[BoxData[ \(TraditionalForm\`b\_k\)]], ")n+ i", Cell[BoxData[ \(TraditionalForm\`\_k\)]], ") ", Cell[BoxData[ \(TraditionalForm\`and\ \ \ \(\[Psi](n)\)\ F\_1\)]], "(", Cell[BoxData[ \(TraditionalForm\`a\_1\)]], "n+", Cell[BoxData[ \(TraditionalForm\`i\_1\)]], ")\[CenterEllipsis]", Cell[BoxData[ \(TraditionalForm\`F\_k\)]], "(", Cell[BoxData[ \(TraditionalForm\`a\_k\)]], "n +", Cell[BoxData[ \(TraditionalForm\`i\_k\)]], ") where \[Psi](n) is a polynomial, and, for each j, the indices ", Cell[BoxData[ \(TraditionalForm\`i\_j\)]], " range between 0 and D(j)-1." }], "Text"], Cell["\<\ The method follows that described in our paper, \"Closed Form Summation of \ C-Finite Sequences\", to appear in Trans. American Math. Society.\ \>", "Text"] }, Open ]], Cell[CellGroupData[{ Cell["How the program works", "Subsection"], Cell[TextData[{ "To compute a sum of the form S(n) = ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\_i\)]], " ", Cell[BoxData[ \(TraditionalForm\`F\_1\)]], "(", Cell[BoxData[ \(TraditionalForm\`a\_1\)]], "n + ", Cell[BoxData[ \(TraditionalForm\`b\_1\)]], "j + ", Cell[BoxData[ \(TraditionalForm\`c\_1\)]], ")\[CenterEllipsis]", Cell[BoxData[ \(TraditionalForm\`F\_k\)]], "(", Cell[BoxData[ \(TraditionalForm\`a\_k\)]], "n + ", Cell[BoxData[ \(TraditionalForm\`b\_k\)]], "j + ", Cell[BoxData[ \(TraditionalForm\`c\_k\)]], ") , the only required input is a list of the form" }], "Text"], Cell[BoxData[ \({{a[1], b[1], c[1]}, {a[2], b[2], c[2]}, ... , {a[k], b[k], c[k]}}\)], "Input"], Cell["and explicit definitions for functions", "Text"], Cell[BoxData[ \(F[n, 1], \ F[n, 2], ... , \ F[n, k]\)], "Input"], Cell[TextData[{ "which are assumed to be C-finite. The program computes the actual C-finite \ degree, the multiplicities of the roots, and also a minimal recurrence \ satisfied by each ", StyleBox["F[n,i]. ", FontWeight->"Bold"], "The exact format is " }], "Text"], Cell[BoxData[ \(CFSum[\(\(<\)\(abclist\)\(>\)\), \(\(<\)\(newnames\)\(>\)\)]\)], "Input"], Cell["\<\ It then computes a list of N distinct \"target monomials\", and solves a \ system of N linear equations involving S(1), S(2), ..., S(N) to express S(n) \ as a linear combination of those monomials. By results in our paper, any such \ linear combination agreeing with S(n) for n = 1,2, ..., N must agree for all \ values of N.\ \>", "Text"], Cell[TextData[{ "If the resulting linear combination is not uniquely determined, the \ expression will contain arbitrary constants denoted ", StyleBox["xx[1], xx[2], xx[3],", FontWeight->"Bold"], " ..., etc. " }], "Text"], Cell[TextData[{ "The parameter <", StyleBox["newnames>", FontWeight->"Bold"], " is ", "optional", ". If omitted, then the names of the functions ", StyleBox["F[n,i]", FontWeight->"Bold"], " as they appear on output will be \"", StyleBox["f[n,i]", FontWeight->"Bold"], "\". Otherwise, <", StyleBox["newnames>", FontWeight->"Bold"], " can be specified as a list of replacement rules, e.g., ", StyleBox["{F[n_,1]\[Rule]n,F[n_,2]\[Rule]Fibonacci[n]}", FontWeight->"Bold"], ", and these name substitutions will be made on output. Note that if you \ replace with the name of a user-defined function, as opposed to a built-in \ function, the output might look unpleasant, with towers of \"If\" statements, \ so this should be avoided." }], "Text"], Cell[TextData[{ StyleBox["Important", FontSlant->"Italic"], ": If you define a function directly with a recurrence relation, be sure \ to use the Mathematica \"f[n_]:=f[n]=\" construction so the program will \ remember previously computed values. This can speed the calculation \ immensely. " }], "Text"], Cell[TextData[{ "Before running the program, be sure to execute the initalization cells \ using the ", StyleBox["Kernel > Evaluation", FontWeight->"Bold"], " menu." }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Example 3.1 (Fibonacci Example)", "Subsection"], Cell[BoxData[{ \(\(F[n_, 1] := Fibonacci[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 2] := Fibonacci[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 3] := Fibonacci[n];\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}, {2, \(-1\), 0}}, {f[n_, _] \[Rule] Fib[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ \("No monomial product equals 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]10\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 10, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(1\/2\ Fib[2\ n] + 1\/2\ Fib[n]\^2\ Fib[1 + n] - 1\/2\ Fib[n]\ Fib[1 + n]\^2 + 1\/2\ Fib[1 + n]\^3 - 1\/2\ Fib[1 + 2\ n]\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Example 3.2 (Subword Avoidance, A=2)", "Subsection"], Cell[BoxData[ \(\(A = 2;\)\)], "Input"], Cell[BoxData[{ \(\(Clear[G];\)\), "\[IndentingNewLine]", \(G[n_]\ := \ \(G[n]\ = \ If[n \[Equal] 0, 1, If[n \[Equal] 1, A, If[n \[Equal] 2, A^2, A\ G[n - 1]\ - \ G[n - 3]]]] // Simplify\)\)}], "Input"], Cell[BoxData[{ \(\(F[n_, 1] := G[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 2] := G[n];\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] GG[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{3, 3}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {3, 3}, "."], Editable->False]], "Print"], Cell[BoxData[ \("There are monomial products equal to 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]11\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 11, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(2 + n + 3\ GG[n]\ GG[1 + n] + GG[1 + n]\^2 - GG[n]\ GG[2 + n] - GG[1 + n]\ GG[2 + n] - xx[11] + GG[n]\^2\ xx[11] + 2\ GG[n]\ GG[1 + n]\ xx[11] + GG[1 + n]\^2\ xx[11] - 2\ GG[n]\ GG[2 + n]\ xx[11] - 2\ GG[1 + n]\ GG[2 + n]\ xx[11] + GG[2 + n]\^2\ xx[11]\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Collect[%, xx[11]]\)], "Input"], Cell[BoxData[ \(2 + n + 3\ GG[n]\ GG[1 + n] + GG[1 + n]\^2 - GG[n]\ GG[2 + n] - GG[1 + n]\ GG[ 2 + n] + \((\(-1\) + GG[n]\^2 + 2\ GG[n]\ GG[1 + n] + GG[1 + n]\^2 - 2\ GG[n]\ GG[2 + n] - 2\ GG[1 + n]\ GG[2 + n] + GG[2 + n]\^2)\)\ xx[11]\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Example 3.2 (Subword Avoidance, General A)", "Subsection"], Cell[BoxData[ \(A =. \)], "Input"], Cell[BoxData[{ \(\(Clear[G];\)\), "\[IndentingNewLine]", \(G[n_]\ := \ \(G[n]\ = \ If[n \[Equal] 0, 1, If[n \[Equal] 1, A, If[n \[Equal] 2, A^2, A\ G[n - 1]\ - \ G[n - 3] // Expand]]]\)\)}], "Input"], Cell[BoxData[{ \(\(F[n_, 1] := G[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 2] := G[n];\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[G[n], {n, 0, 10}]\)], "Input"], Cell[BoxData[ \({1, A, A\^2, \(-1\) + A\^3, \(-2\)\ A + A\^4, \(-3\)\ A\^2 + A\^5, 1 - 4\ A\^3 + A\^6, 3\ A - 5\ A\^4 + A\^7, 6\ A\^2 - 6\ A\^5 + A\^8, \(-1\) + 10\ A\^3 - 7\ A\^6 + A\^9, \(-4\)\ A + 15\ A\^4 - 8\ A\^7 + A\^10}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] GG[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{3, 3}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {3, 3}, "."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("If "\[InvisibleSpace]\(2\ A\^3 - A\^4 \[NotEqual] 0\)\[InvisibleSpace]" then no monomial product equals 1."\), SequenceForm[ "If ", Unequal[ Plus[ Times[ 2, Power[ A, 3]], Times[ -1, Power[ A, 4]]], 0], " then no monomial product equals 1."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]10\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 10, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(1\/\(\(-2\)\ A + A\^2\) - GG[n]\^2\/\(\(-2\)\ A + A\^2\) + \(2\ A\ GG[n]\^2\)\/\(\(-2\)\ A + A\^2\ \) - \(A\^2\ GG[n]\^2\)\/\(\(-2\)\ A + A\^2\) - \(2\ GG[n]\ GG[1 + \ n]\)\/\(\(-2\)\ A + A\^2\) - GG[1 + n]\^2\/\(\(-2\)\ A + A\^2\) + \(2\ A\ GG[1 + n]\^2\)\/\(\(-2\)\ \ A + A\^2\) - \(A\^2\ GG[1 + n]\^2\)\/\(\(-2\)\ A + A\^2\) + \(2\ GG[n]\ GG[2 \ + n]\)\/\(\(-2\)\ A + A\^2\) - \(2\ GG[1 + n]\ GG[2 + n]\)\/\(\(-2\)\ A + \ A\^2\) + \(2\ A\ GG[1 + n]\ GG[2 + n]\)\/\(\(-2\)\ A + A\^2\) - GG[2 + n]\^2\/\(\(-2\)\ A + A\^2\)\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(% // Simplify\)], "Input"], Cell[BoxData[ \(\(-\(\(\(-1\) + \((\(-1\) + A)\)\^2\ GG[n]\^2 + \((\(-1\) + A)\)\^2\ \ GG[1 + n]\^2 + 2\ GG[n]\ \((GG[1 + n] - GG[2 + n])\) - 2\ \((\(-1\) + A)\)\ GG[1 + n]\ GG[2 + n] + GG[2 + n]\^2\)\/\(\((\(-2\) + A)\)\ A\)\)\)\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Example 3.3 (Fibonacci Power Sums)", "Subsection"], Cell[BoxData[{ \(\(F[n_, 1] := Fibonacci[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 2] := Fibonacci[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 3] := Fibonacci[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 4] := Fibonacci[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 5] := Fibonacci[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 6] := Fibonacci[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 7] := Fibonacci[n];\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}}, {f[n_, _] \[Rule] f[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are \ "\[InvisibleSpace]{2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2}, "."], Editable->False]], "Print"], Cell[BoxData[ \("No monomial product equals 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]3\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 3, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(\(-1\) + f[1 + n]\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] f[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ \("No monomial product equals 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]5\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 5, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(\(-f[n]\^2\) + f[n]\ f[1 + n]\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] f[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ \("No monomial product equals 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]9\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 9, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(1\/2 - \(3\ f[n]\^3\)\/2 + 3\/2\ f[n]\ f[1 + n]\^2 - 1\/2\ f[1 + n]\^3\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] f[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2, 2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2, 2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ \("There are monomial products equal to 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]18\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 18, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(\(6\ n\)\/25 - \(19\ f[n]\^4\)\/25 + 14\/25\ f[n]\^3\ f[1 + n] - 3\/25\ f[n]\^2\ f[1 + n]\^2 + 2\/25\ f[n]\ f[1 + n]\^3 - xx[18] + f[n]\^4\ xx[18] + 2\ f[n]\^3\ f[1 + n]\ xx[18] - f[n]\^2\ f[1 + n]\^2\ xx[18] - 2\ f[n]\ f[1 + n]\^3\ xx[18] + f[1 + n]\^4\ xx[18]\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Collect[%, xx[18]]\)], "Input"], Cell[BoxData[ \(\(6\ n\)\/25 - \(19\ f[n]\^4\)\/25 + 14\/25\ f[n]\^3\ f[1 + n] - 3\/25\ f[n]\^2\ f[1 + n]\^2 + 2\/25\ f[n]\ f[1 + n]\^3 + \((\(-1\) + f[n]\^4 + 2\ f[n]\^3\ f[1 + n] - f[n]\^2\ f[1 + n]\^2 - 2\ f[n]\ f[1 + n]\^3 + f[1 + n]\^4)\)\ xx[ 18]\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] f[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2, 2, 2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2, 2, 2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ \("No monomial product equals 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]33\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 33, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(\(-\(7\/22\)\) - \(15\ f[n]\^5\)\/22 + 15\/11\ f[n]\^4\ f[1 + n] + 10\/11\ f[n]\^3\ f[1 + n]\^2 - 15\/11\ f[n]\^2\ f[1 + n]\^3 - 5\/22\ f[n]\ f[1 + n]\^4 + 7\/22\ f[1 + n]\^5\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] f[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2, 2, 2, 2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2, 2, 2, 2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ \("No monomial product equals 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]65\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 65, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(\(-f[n]\^6\) + 1\/2\ f[n]\^5\ f[1 + n] + 5\/4\ f[n]\^4\ f[1 + n]\^2 - 5\/4\ f[n]\^2\ f[1 + n]\^4 + 1\/2\ f[n]\ f[1 + n]\^5\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] f[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2, 2, 2, 2, 2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2, 2, 2, 2, 2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ \("No monomial product equals 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]129\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 129, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(139\/638 - \(777\ f[n]\^7\)\/638 - 105\/319\ f[n]\^6\ f[1 + n] + 357\/319\ f[n]\^5\ f[1 + n]\^2 + 105\/58\ f[n]\^4\ f[1 + n]\^3 - 350\/319\ f[n]\^3\ f[1 + n]\^4 - 945\/638\ f[n]\^2\ f[1 + n]\^5 + 763\/638\ f[n]\ f[1 + n]\^6 - 139\/638\ f[1 + n]\^7\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Example 3.4 (Generic Power Sums)", "Subsection"], Cell[BoxData[ \(A =. ; B =. \)], "Input"], Cell[BoxData[{ \(\(Clear[H];\)\), "\[IndentingNewLine]", \(H[n_]\ := \ \(H[n]\ = \ If[n \[Equal] 0, p, If[n \[Equal] 1, q, A\ H[n - 1]\ + \ B\ H[n - 2] // Expand]]\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[H[n], {n, 0, 5}]\)], "Input"], Cell[BoxData[ \({p, q, B\ p + A\ q, A\ B\ p + A\^2\ q + B\ q, A\^2\ B\ p + B\^2\ p + A\^3\ q + 2\ A\ B\ q, A\^3\ B\ p + 2\ A\ B\^2\ p + A\^4\ q + 3\ A\^2\ B\ q + B\^2\ q}\)], "Output"] }, Open ]], Cell[BoxData[{ \(\(F[n_, 1] := H[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 2] := H[n];\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] h[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("If "\[InvisibleSpace]\(1 - A\^2 - 2\ A\^2\ B - 2\ B\^2 - A\^2\ B\^2 + B\^4 \[NotEqual] 0\)\[InvisibleSpace]" then no monomial product equals 1."\), SequenceForm[ "If ", Unequal[ Plus[ 1, Times[ -1, Power[ A, 2]], Times[ -2, Power[ A, 2], B], Times[ -2, Power[ B, 2]], Times[ -1, Power[ A, 2], Power[ B, 2]], Power[ B, 4]], 0], " then no monomial product equals 1."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]5\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 5, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(\(-\(p\^2\/\(\(-1\) + A\^2 + B + A\^2\ B + B\^2 - B\^3\)\)\) + \(A\^2\ p\^2\)\/\(\(-1\) + A\^2 + B + A\^2\ B + \ B\^2 - B\^3\) + \(B\ p\^2\)\/\(\(-1\) + A\^2 + B + A\^2\ B + B\^2 - B\^3\) + \ \(A\^2\ B\ p\^2\)\/\(\(-1\) + A\^2 + B + A\^2\ B + B\^2 - B\^3\) - \(2\ A\ B\ \ p\ q\)\/\(\(-1\) + A\^2 + B + A\^2\ B + B\^2 - B\^3\) - q\^2\/\(\(-1\) + A\^2 + B + A\^2\ B + B\^2 - B\^3\) + \(B\ \ q\^2\)\/\(\(-1\) + A\^2 + B + A\^2\ B + B\^2 - B\^3\) + h[n]\^2\/\(\(-1\) + A\^2 + B + A\^2\ B + B\^2 - B\^3\) - \(A\^2\ \ h[n]\^2\)\/\(\(-1\) + A\^2 + B + A\^2\ B + B\^2 - B\^3\) - \(B\ h[n]\^2\)\/\(\ \(-1\) + A\^2 + B + A\^2\ B + B\^2 - B\^3\) - \(A\^2\ B\ h[n]\^2\)\/\(\(-1\) \ + A\^2 + B + A\^2\ B + B\^2 - B\^3\) + \(2\ A\ B\ h[n]\ h[1 + n]\)\/\(\(-1\) \ + A\^2 + B + A\^2\ B + B\^2 - B\^3\) + h[1 + n]\^2\/\(\(-1\) + A\^2 + B + A\^2\ B + B\^2 - B\^3\) - \(B\ h[1 + \ n]\^2\)\/\(\(-1\) + A\^2 + B + A\^2\ B + B\^2 - B\^3\)\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(% // Simplify\)], "Input"], Cell[BoxData[ \(\(\(-p\^2\) + A\^2\ p\^2 + B\ p\^2 + A\^2\ B\ p\^2 - 2\ A\ B\ p\ q - \ q\^2 + B\ q\^2 - \((\(-1\) + B + A\^2\ \((1 + B)\))\)\ h[n]\^2 + 2\ A\ B\ \ h[n]\ h[1 + n] - \((\(-1\) + B)\)\ h[1 + n]\^2\)\/\(\((A\^2 - \((\(-1\) + \ B)\)\^2)\)\ \((1 + B)\)\)\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Example 9.1 (Mixed Convolution)", "Subsection"], Cell[BoxData[{ \(\(Clear[G];\)\), "\[IndentingNewLine]", \(G[n_]\ := \ \(G[n]\ = \ If[n \[Equal] 0, 1, If[n \[Equal] 1, 3, If[n \[Equal] 2, 9, 3\ G[n - 1]\ - \ G[n - 3]]]] // Simplify\)\)}], "Input"], Cell[BoxData[{ \(\(F[n_, 1]\ := \ n;\)\), "\[IndentingNewLine]", \(\(F[n_, 2] := Fibonacci[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 3] := G[n];\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}, {1, \(-1\), 0}}, {f[n_, 1] \[Rule] n, f[n_, 2] \[Rule] f[n], f[n_, 3] \[Rule] g[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2, 3}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2, 3}, "."], Editable->False]], "Print"], Cell[BoxData[ \("No monomial product equals 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]7\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 7, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(\(-3\)\ f[n] - n\ f[n] - n\ f[1 + n] - 9\ g[n] + 18\ g[1 + n] - 5\ g[2 + n]\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Example 9.2 (Independence Property)", "Subsection"], Cell[BoxData[{ \(\(Clear[F];\)\), "\[IndentingNewLine]", \(F[n_]\ := \(F[n]\ = \ If[n \[Equal] 0, p, If[n \[Equal] 1, 1, F[n - 1]\ + F[n - 2]]] // Simplify\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[F[n], {n, 0, 6}]\)], "Input"], Cell[BoxData[ \({p, 1, 1 + p, 2 + p, 3 + 2\ p, 5 + 3\ p, 8 + 5\ p}\)], "Output"] }, Open ]], Cell[BoxData[{ \(\(F[n_, 1]\ := F[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 2] := F[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 3] := F[n];\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] f[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ \("No monomial product equals 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]9\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 9, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(1\/2 - \(3\ p\)\/2 + \(3\ p\^3\)\/2 - \(3\ f[n]\^3\)\/2 + 3\/2\ f[n]\ f[1 + n]\^2 - 1\/2\ f[1 + n]\^3\)], "Output"] }, Open ]], Cell[BoxData[{ \(\(F[n_, 1]\ := F[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 2] := F[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 3] := F[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 4] := F[n];\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] f[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2, 2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2, 2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ \("There are monomial products equal to 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]18\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 18, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(\(6\ n\)\/25 - \(2\ p\)\/25 - \(12\ n\ p\)\/25 + \(3\ p\^2\)\/25 - \(6\ \ n\ p\^2\)\/25 - \(14\ p\^3\)\/25 + \(12\ n\ p\^3\)\/25 + \(19\ p\^4\)\/25 + \ \(6\ n\ p\^4\)\/25 - \(19\ f[n]\^4\)\/25 + 14\/25\ f[n]\^3\ f[1 + n] - 3\/25\ f[n]\^2\ f[1 + n]\^2 + 2\/25\ f[n]\ f[1 + n]\^3 - xx[18] + 2\ p\ xx[18] + p\^2\ xx[18] - 2\ p\^3\ xx[18] - p\^4\ xx[18] + f[n]\^4\ xx[18] + 2\ f[n]\^3\ f[1 + n]\ xx[18] - f[n]\^2\ f[1 + n]\^2\ xx[18] - 2\ f[n]\ f[1 + n]\^3\ xx[18] + f[1 + n]\^4\ xx[18]\)], "Output"] }, Open ]], Cell["To get it to agree with the expression in our paper:", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(% /. \ xx[18] \[Rule] \((19/25 - K)\);\)\), "\[IndentingNewLine]", \(Collect[%, K]\)}], "Input"], Cell[BoxData[ \(\(-\(19\/25\)\) + \(6\ n\)\/25 + \(36\ p\)\/25 - \(12\ n\ p\)\/25 + \ \(22\ p\^2\)\/25 - \(6\ n\ p\^2\)\/25 - \(52\ p\^3\)\/25 + \(12\ n\ \ p\^3\)\/25 + \(6\ n\ p\^4\)\/25 + 52\/25\ f[n]\^3\ f[1 + n] - 22\/25\ f[n]\^2\ f[1 + n]\^2 - 36\/25\ f[n]\ f[1 + n]\^3 + 19\/25\ f[1 + n]\^4 + K\ \((1 - 2\ p - p\^2 + 2\ p\^3 + p\^4 - f[n]\^4 - 2\ f[n]\^3\ f[1 + n] + f[n]\^2\ f[1 + n]\^2 + 2\ f[n]\ f[1 + n]\^3 - f[1 + n]\^4)\)\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Example 9.3 (Partial summation of series)", "Subsection"], Cell[BoxData[{ \(\(F[n_, 1]\ := x^n;\)\), "\[IndentingNewLine]", \(\(F[n_, 2] := Fibonacci[n];\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}}, {f[n_, 1] \[Rule] x^n, f[n_, 2] \[Rule] f[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{1, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {1, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("If "\[InvisibleSpace]\(1 - x - x\^2 \[NotEqual] 0\)\[InvisibleSpace]" then no monomial product equals 1."\), SequenceForm[ "If ", Unequal[ Plus[ 1, Times[ -1, x], Times[ -1, Power[ x, 2]]], 0], " then no monomial product equals 1."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]3\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 3, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(\(-\(x\/\(\(-1\) + x + x\^2\)\)\) + \(x\^n\ f[n]\)\/\(\(-1\) + x + x\^2\) - \(x\^\(1 + \ n\)\ f[n]\)\/\(\(-1\) + x + x\^2\) + \(x\^\(1 + n\)\ f[1 + n]\)\/\(\(-1\) + x \ + x\^2\)\)], "Output"] }, Open ]], Cell[BoxData[{ \(\(F[n_, 1]\ := x^n;\)\), "\[IndentingNewLine]", \(\(F[n_, 2] := Fibonacci[n];\)\), "\[IndentingNewLine]", \(\(F[n_, 3] := Fibonacci[n];\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {f[n_, 1] \[Rule] x^n, f[n_, 2] \[Rule] f[n], f[n_, 3] \[Rule] f[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{1, 2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {1, 2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("If "\[InvisibleSpace]\(1 - x - 4\ x\^2 - x\^3 + x\^4 \[NotEqual] 0\)\[InvisibleSpace]" then no monomial product equals 1."\), SequenceForm[ "If ", Unequal[ Plus[ 1, Times[ -1, x], Times[ -4, Power[ x, 2]], Times[ -1, Power[ x, 3]], Power[ x, 4]], 0], " then no monomial product equals 1."], Editable->False]], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]5\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 5, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(x\/\(1 - 2\ x - 2\ x\^2 + x\^3\) - x\^2\/\(1 - 2\ x - 2\ x\^2 + x\^3\) - \(x\^n\ f[n]\^2\)\/\(1 - 2\ x - 2\ \ x\^2 + x\^3\) + \(2\ x\^\(1 + n\)\ f[n]\^2\)\/\(1 - 2\ x - 2\ x\^2 + x\^3\) \ + \(x\^\(2 + n\)\ f[n]\^2\)\/\(1 - 2\ x - 2\ x\^2 + x\^3\) - \(2\ x\^\(2 + \ n\)\ f[n]\ f[1 + n]\)\/\(1 - 2\ x - 2\ x\^2 + x\^3\) - \(x\^\(1 + n\)\ f[1 + \ n]\^2\)\/\(1 - 2\ x - 2\ x\^2 + x\^3\) + \(x\^\(2 + n\)\ f[1 + n]\^2\)\/\(1 - \ 2\ x - 2\ x\^2 + x\^3\)\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(% // Simplify\)], "Input"], Cell[BoxData[ \(\(x\^n\ \((\(-1\) + 2\ x + x\^2)\)\ f[n]\^2 - 2\ x\^\(2 + n\)\ f[n]\ \ f[1 + n] + \((\(-1\) + x)\)\ x\ \((\(-1\) + x\^n\ f[1 + n]\^2)\)\)\/\(1 - 2\ \ x - 2\ x\^2 + x\^3\)\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Example 9.4 (Degree of the polynomial multiplier)", "Subsection"], Cell[BoxData[ \(\(F[n_, 1]\ := n^5;\)\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}}, {f[n_, 1] \[Rule] n^5}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are \ "\[InvisibleSpace]{6}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {6}, "."], Editable->False]], "Print"], Cell[BoxData[ \("There are monomial products equal to 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]13\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 13, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(\(-\(n\^2\/12\)\) + \(5\ n\^4\)\/12 - n\^5\/2 + n\^6\/6\)], "Output"] }, Open ]], Cell[BoxData[{ \(\(F[n_, 1]\ := n;\)\), "\[IndentingNewLine]", \(\(F[n_, 2]\ := n;\)\), "\[IndentingNewLine]", \(\(F[n_, 3]\ := n;\)\), "\[IndentingNewLine]", \(\(F[n_, 4]\ := n;\)\), "\[IndentingNewLine]", \(\(F[n_, 5]\ := n;\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}}, {f[n_, _] \[Rule] n}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are "\[InvisibleSpace]{2, 2, 2, 2, 2}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {2, 2, 2, 2, 2}, "."], Editable->False]], "Print"], Cell[BoxData[ \("There are monomial products equal to 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]39\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 39, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(\(-\(n\^2\/12\)\) + \(5\ n\^4\)\/12 - n\^5\/2 + n\^6\/6\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Example 9.5 (Example from the theory of partitions)", "Subsection"], Cell[BoxData[{ \(Clear[P5]\), "\[IndentingNewLine]", \(P5[n_]\ := \ \(P5[n]\ = SeriesCoefficient[ Series[Product[1/\((1 - z^i)\), {i, 1, 5}], {z, 0, 200}], n]\)\)}], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[P5[n], {n, 0, 30}]\)], "Input"], Cell[BoxData[ \({1, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 84, 101, 119, 141, 164, 192, 221, 255, 291, 333, 377, 427, 480, 540, 603, 674}\)], "Output"] }, Open ]], Cell[BoxData[ \(\(F[n_, 1]\ := P5[n];\)\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(CFSum[{{0, 1, 0}}, {f[n_, _] \[Rule] p[n]}]\)], "Input"], Cell[BoxData[ InterpretationBox[\("Degrees are \ "\[InvisibleSpace]{15}\[InvisibleSpace]"."\), SequenceForm[ "Degrees are ", {15}, "."], Editable->False]], "Print"], Cell[BoxData[ \("There are monomial products equal to 1."\)], "Print"], Cell[BoxData[ InterpretationBox[\("There are "\[InvisibleSpace]21\[InvisibleSpace]" \ target monomials."\), SequenceForm[ "There are ", 21, " target monomials."], Editable->False]], "Print"], Cell[BoxData[ \(1001\/60 + \(25381\ n\)\/3600 + \(19\ n\^2\)\/16 + \(287\ n\^3\)\/2880 \ + n\^4\/240 + n\^5\/14400 - \(119\ p[n]\)\/120 - 23\/24\ p[1 + n] - 53\/60\ p[2 + n] - 91\/120\ p[3 + n] - 71\/120\ p[4 + n] - 49\/120\ p[5 + n] - 29\/120\ p[6 + n] - 7\/60\ p[7 + n] - 1\/24\ p[8 + n] - 1\/120\ p[9 + n] - 1001\ xx[17] - 3875\/12\ n\ xx[17] - 935\/24\ n\^2\ xx[17] - 25\/12\ n\^3\ xx[17] - 1\/24\ n\^4\ xx[17] + p[n]\ xx[17] + 4\ p[1 + n]\ xx[17] + 9\ p[2 + n]\ xx[17] + 15\ p[3 + n]\ xx[17] + 20\ p[4 + n]\ xx[17] + 22\ p[5 + n]\ xx[17] + 20\ p[6 + n]\ xx[17] + 15\ p[7 + n]\ xx[17] + 9\ p[8 + n]\ xx[17] + 4\ p[9 + n]\ xx[17] + p[10 + n]\ xx[17] + 2639\ xx[18] + 10613\/12\ n\ xx[18] + 883\/8\ n\^2\ xx[18] + 73\/12\ n\^3\ xx[18] + 1\/8\ n\^4\ xx[18] - 4\ p[n]\ xx[18] - 15\ p[1 + n]\ xx[18] - 32\ p[2 + n]\ xx[18] - 51\ p[3 + n]\ xx[18] - 65\ p[4 + n]\ xx[18] - 68\ p[5 + n]\ xx[18] - 58\ p[6 + n]\ xx[18] - 40\ p[7 + n]\ xx[18] - 21\ p[8 + n]\ xx[18] - 7\ p[9 + n]\ xx[18] + p[11 + n]\ xx[18] - 3367\ xx[19] - 2273\/2\ n\ xx[19] - 430\/3\ n\^2\ xx[19] - 8\ n\^3\ xx[19] - 1\/6\ n\^4\ xx[19] + 7\ p[n]\ xx[19] + 24\ p[1 + n]\ xx[19] + 48\ p[2 + n]\ xx[19] + 73\ p[3 + n]\ xx[19] + 89\ p[4 + n]\ xx[19] + 89\ p[5 + n]\ xx[19] + 72\ p[6 + n]\ xx[19] + 47\ p[7 + n]\ xx[19] + 23\ p[8 + n]\ xx[19] + 7\ p[9 + n]\ xx[19] + p[12 + n]\ xx[19] + 2352\ xx[20] + 9751\/12\ n\ xx[20] + 835\/8\ n\^2\ xx[20] + 71\/12\ n\^3\ xx[20] + 1\/8\ n\^4\ xx[20] - 7\ p[n]\ xx[20] - 21\ p[1 + n]\ xx[20] - 39\ p[2 + n]\ xx[20] - 57\ p[3 + n]\ xx[20] - 67\ p[4 + n]\ xx[20] - 65\ p[5 + n]\ xx[20] - 51\ p[6 + n]\ xx[20] - 33\ p[7 + n]\ xx[20] - 16\ p[8 + n]\ xx[20] - 5\ p[9 + n]\ xx[20] + p[13 + n]\ xx[20] - 1730\ xx[21] - 575\ n\ xx[21] - 863\/12\ n\^2\ xx[21] - 4\ n\^3\ xx[21] - 1\/12\ n\^4\ xx[21] + 5\ p[n]\ xx[21] + 13\ p[1 + n]\ xx[21] + 24\ p[2 + n]\ xx[21] + 36\ p[3 + n]\ xx[21] + 43\ p[4 + n]\ xx[21] + 43\ p[5 + n]\ xx[21] + 35\ p[6 + n]\ xx[21] + 24\ p[7 + n]\ xx[21] + 12\ p[8 + n]\ xx[21] + 4\ p[9 + n]\ xx[21] + p[14 + n]\ xx[21]\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Collect[%, xx[17]]\)], "Input"], Cell[BoxData[ \(1001\/60 + \(25381\ n\)\/3600 + \(19\ n\^2\)\/16 + \(287\ n\^3\)\/2880 \ + n\^4\/240 + n\^5\/14400 - \(119\ p[n]\)\/120 - 23\/24\ p[1 + n] - 53\/60\ p[2 + n] - 91\/120\ p[3 + n] - 71\/120\ p[4 + n] - 49\/120\ p[5 + n] - 29\/120\ p[6 + n] - 7\/60\ p[7 + n] - 1\/24\ p[8 + n] - 1\/120\ p[ 9 + n] + \((\(-1001\) - \(3875\ n\)\/12 - \(935\ n\^2\)\/24 - \(25\ \ n\^3\)\/12 - n\^4\/24 + p[n] + 4\ p[1 + n] + 9\ p[2 + n] + 15\ p[3 + n] + 20\ p[4 + n] + 22\ p[5 + n] + 20\ p[6 + n] + 15\ p[7 + n] + 9\ p[8 + n] + 4\ p[9 + n] + p[10 + n])\)\ xx[17] + 2639\ xx[18] + 10613\/12\ n\ xx[18] + 883\/8\ n\^2\ xx[18] + 73\/12\ n\^3\ xx[18] + 1\/8\ n\^4\ xx[18] - 4\ p[n]\ xx[18] - 15\ p[1 + n]\ xx[18] - 32\ p[2 + n]\ xx[18] - 51\ p[3 + n]\ xx[18] - 65\ p[4 + n]\ xx[18] - 68\ p[5 + n]\ xx[18] - 58\ p[6 + n]\ xx[18] - 40\ p[7 + n]\ xx[18] - 21\ p[8 + n]\ xx[18] - 7\ p[9 + n]\ xx[18] + p[11 + n]\ xx[18] - 3367\ xx[19] - 2273\/2\ n\ xx[19] - 430\/3\ n\^2\ xx[19] - 8\ n\^3\ xx[19] - 1\/6\ n\^4\ xx[19] + 7\ p[n]\ xx[19] + 24\ p[1 + n]\ xx[19] + 48\ p[2 + n]\ xx[19] + 73\ p[3 + n]\ xx[19] + 89\ p[4 + n]\ xx[19] + 89\ p[5 + n]\ xx[19] + 72\ p[6 + n]\ xx[19] + 47\ p[7 + n]\ xx[19] + 23\ p[8 + n]\ xx[19] + 7\ p[9 + n]\ xx[19] + p[12 + n]\ xx[19] + 2352\ xx[20] + 9751\/12\ n\ xx[20] + 835\/8\ n\^2\ xx[20] + 71\/12\ n\^3\ xx[20] + 1\/8\ n\^4\ xx[20] - 7\ p[n]\ xx[20] - 21\ p[1 + n]\ xx[20] - 39\ p[2 + n]\ xx[20] - 57\ p[3 + n]\ xx[20] - 67\ p[4 + n]\ xx[20] - 65\ p[5 + n]\ xx[20] - 51\ p[6 + n]\ xx[20] - 33\ p[7 + n]\ xx[20] - 16\ p[8 + n]\ xx[20] - 5\ p[9 + n]\ xx[20] + p[13 + n]\ xx[20] - 1730\ xx[21] - 575\ n\ xx[21] - 863\/12\ n\^2\ xx[21] - 4\ n\^3\ xx[21] - 1\/12\ n\^4\ xx[21] + 5\ p[n]\ xx[21] + 13\ p[1 + n]\ xx[21] + 24\ p[2 + n]\ xx[21] + 36\ p[3 + n]\ xx[21] + 43\ p[4 + n]\ xx[21] + 43\ p[5 + n]\ xx[21] + 35\ p[6 + n]\ xx[21] + 24\ p[7 + n]\ xx[21] + 12\ p[8 + n]\ xx[21] + 4\ p[9 + n]\ xx[21] + p[14 + n]\ xx[21]\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(\(-1001\) - \(3875\ n\)\/12 - \(935\ n\^2\)\/24 - \(25\ n\^3\)\/12 - n\^4\/24 // Factor\)], "Input"], Cell[BoxData[ \(\(-\(1\/24\)\)\ \((11 + n)\)\ \((12 + n)\)\ \((13 + n)\)\ \((14 + n)\)\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Technical Details (This part can safely be ignored)", "Section"], Cell[BoxData[ \(CFSum[abc_, newnames_: {}] := Module[{k, ff, dst, a, b, c, i, pl, oo, \ outr, eqs, varbs, mxm, pdg, tt, \[IndentingNewLine]\ \ \ \ \ \ \ \ \ \ \ \ \ \ kk, ind, pp, psi, sm, zz, ty, ss, nn, h, deg, x}, \[IndentingNewLine]\[IndentingNewLine] (*\ Evaluates\ a\ sum, \ from\ j = 0\ to\ n - 1, \ \(of\[IndentingNewLine] \ \ \ F[a[1] n + b[1] j + c[1], 1] F[a[2] n + b[2] j + c[2], 2]\ ... \)\ F[ a[k] n + b[k] j + c[k], k]\[IndentingNewLine]\ in\ which\ each\ F[m, j]\ is\ C - finite . \[IndentingNewLine]The\ input\ abc\ is\ the\ array\ of\ \ length\ k\ of\ the\ triples\ {a[j], b[j], c[j]} . \ \[IndentingNewLine]The\ k\ functions\ F[m, j]\ are\ specified\ externally . \ \[IndentingNewLine]Input\ \ newnames\ is\ optional . \ If\ omitted, \ then\ the\ names\ of\ the\ functions\ F[n, i]\[IndentingNewLine]\ \ \ \ as\ they\ appear\ on\ output\ will\ \ be\ "\" . \ Otherwise, \ newnames\ can\ be\[IndentingNewLine]\ \ \ \ specified\ as\ a\ list\ \ of\ replacement\ rules, \ e . g . , \ {F[n_, 1] \[Rule] n, F[n_, 2] \[Rule] Fibonacci[ n]} . \[IndentingNewLine]\ \ \ \ and\ these\ name\ \ substitutions\ will\ be\ made\ on\ output . \ Note\ that\ if\ you\ replace\[IndentingNewLine]\ \ \ \ with\ \ the\ name\ of\ a\ user - defined\ function, \ as\ opposed\ to\ a\ built - in\ function, \ the\[IndentingNewLine]\ \ \ \ \ output\ might\ look\ unpleasant, \ with\ towers\ of\ "\"\ statements, \ so\ this\ should\ be\[IndentingNewLine]\ \ \ \ \ avoided . \ \[IndentingNewLine]This\ routine\ assumes\ that\ the\ routines\ \ "\", \ "\", \ "\", \ "\", \ \[IndentingNewLine]\ \ \ \ \ \ and\ "\"\ below\ are\ activated . \ \[IndentingNewLine]\(Important : \ If\ you\ define\ a\ function\ directly\ with\ a\ recurrence\ \ relation\), \ \[IndentingNewLine]\ \ \ be\ sure\ to\ use\ the\ Mathematica\ "\ \"\ construction\ so\ the\ program\[IndentingNewLine]\ \ will\ \ remember\ previously\ computed\ values . \ This\ can\ speed\ the\ calculation\[IndentingNewLine]\ \ \ \(\(immensely\)\(.\)\)\ \[IndentingNewLine]\ \ *) \[IndentingNewLine]\ \[IndentingNewLine]k = Length[abc]; Clear[ff, f, n]; \ ff = 0; Off[Solve::svars]; \[IndentingNewLine]\[IndentingNewLine] (*\ Find\ CF - degrees\ of\ input\ sequences\ *) \[IndentingNewLine]deg = Table[0, {k}]; \[IndentingNewLine]For[i = 1, i \[LessEqual] k, \(i++\), h[n_] := F[n, i]; deg[\([i]\)] = FindDegree[h]]; \[IndentingNewLine]Print["\", deg, "\<.\>"]; \[IndentingNewLine]dst = Table[0, {k}]; mxm = Table[0, {k}]; outr := {{1}}; \[IndentingNewLine]a = Table[\(abc[\([i]\)]\)[\([1]\)], {i, 1, k}]; \[IndentingNewLine]b = Table[\(abc[\([i]\)]\)[\([2]\)], {i, 1, k}]; \[IndentingNewLine]c = Table[\(abc[\([i]\)]\)[\([3]\)], {i, 1, k}]; \[IndentingNewLine]\[IndentingNewLine] (*\ Finds\ polynomials\ associated\ with\ each\ of\ the\ F' s\ *) \[IndentingNewLine]For[i = 1, i \[LessEqual] k, \(i++\), \[IndentingNewLine]\ pl = x^\((deg[\([i]\)])\) - Sum[cc[j]\ x^j, {j, 0, deg[\([i]\)] - 1}]; \[IndentingNewLine]\ eqs = Table[ F[n + deg[\([i]\)], i] \[Equal] Sum[cc[j]\ F[n + j, i], {j, 0, deg[\([i]\)] - 1}], {n, 0, deg[\([i]\)] - 1}]; \[IndentingNewLine]\ varbs = Table[cc[k], {k, 0, deg[\([i]\)]}]; \[IndentingNewLine]\ pl = \((\(Expand[pl /. Solve[eqs, varbs]]\)[\([1]\)])\) /. Table[cc[j] -> 0, {j, 0, deg[\([i]\)] - 1}]; \[IndentingNewLine]\ (*\ Set\ up\ array\ of\ numbers\ of\ distinct\ roots\ of\ each\ \ *) \[IndentingNewLine]\ dst = ReplacePart[dst, Exponent[ PolynomialQuotient[pl, PolynomialGCD[pl, D[pl, x]], x], x], i]; \[IndentingNewLine]\ (*\ Set\ up\ array\ of\ maximum\ multiplicities\ of\ each\ polynomial\ \ *) \[IndentingNewLine]\ mxm = ReplacePart[mxm, maxmult[pl, x], i]; \[IndentingNewLine]\ \ (*\ Accumulate\ companion\ matrix\ of\ pl\ into\ NoMonom\ matrix\ \ outer\ product\ \ *) \[IndentingNewLine]\ outr = kronecker[outr, MatrixPower[companion[pl, x], b[\([i]\)]]];\[IndentingNewLine]]; \[IndentingNewLine]\ \[IndentingNewLine] (*Test\ whether\ any\ monomials\ = \ 1\ *) \[IndentingNewLine]oo = \(Dimensions[outr]\)[\([1]\)]; NoMonom = \((Det[IdentityMatrix[oo] - outr] \[NotEqual] 0)\); \[IndentingNewLine]If[NoMonom, Print["\"], Print["\"], Print["\", NoMonom, "\< then no monomial product equals 1.\>"]]; \ \[IndentingNewLine]\[IndentingNewLine] (*Compute\ max\ degree\ of\ polynomial\ \ psi*) \[IndentingNewLine]pdg = 1 + Sum[If[a[\([i]\)] \[Equal] 0, mxm[\([i]\)] - 1, 0], {i, 1, k}]; \[IndentingNewLine]\[IndentingNewLine] (*\ Assemble\ list\ of\ target\ monomials\ *) \[IndentingNewLine]tt = indices[deg]; ls = {}; \[IndentingNewLine]For[kk = 1, kk \[LessEqual] Length[tt], \(kk++\), \[IndentingNewLine]ind = tt[\([kk]\)]; \[IndentingNewLine]ls = Union[ls, \ {Product[ If[a[\([i]\)] + b[\([i]\)] \[Equal] 0, 1, f[\((a[\([i]\)] + b[\([i]\)])\)\ n + ind[\([i]\)], i]], {i, 1, k}]}]; \[IndentingNewLine]pp = Product[If[a[\([i]\)] \[NotEqual] 0, f[\((a[\([i]\)]\ n + ind[\([i]\)])\), i], 1], {i, 1, k}]; \[IndentingNewLine]ls = Union[ls, {pp}]; \[IndentingNewLine]If[Not[NoMonom], For[h = 1, h \[LessEqual] pdg, \(h++\), ls = Union[ls, {n^h\ pp}]]]]; \[IndentingNewLine]jj = Length[ls]; \ Print["\", jj, "\< target monomials.\>"]; \[IndentingNewLine]ff = Sum[xx[j]\ ls[\([j]\)], {j, 1, jj}]; \[IndentingNewLine]For[i = 1, i \[LessEqual] k, \(i++\), f[m_, i_] := F[m, i]]; \[IndentingNewLine]sm[nn_] := Sum[Product[ F[a[\([i]\)]\ nn + b[\([i]\)]\ j + c[\([i]\)], i], {i, 1, k}], {j, 0, nn - 1}]; \[IndentingNewLine] (*\ cfd = FindDegree[ sm]; \[IndentingNewLine]Print["\", cfd];\ *) \[IndentingNewLine]zz = Table[xx[j], {j, 1, jj}]; \[IndentingNewLine]ty = Table[sm[nn] \[Equal] ff /. {n \[Rule] nn}, {nn, 0, jj - 1}]; \[IndentingNewLine]ss = \(Solve[ty, zz]\)[\([1]\)]; \[IndentingNewLine]zz = \((zz /. \ {ss})\)[\([1]\)]; \[IndentingNewLine] (*\(Print["\", jj, "\< consecutive values of n, and is therefore correct for \ all n: \>"];\)*) \[IndentingNewLine]Clear[f]; \[IndentingNewLine]ff = ff /. Table[ xx[i] \[Rule] zz[\([i]\)], {i, 1, jj}]; \[IndentingNewLine]\ \ \ \ \ \ ff = ExpandAll[Simplify[ff]]; \[IndentingNewLine]ff = ff /. newnames; ff = Expand[ff]; \[IndentingNewLine]Return[ff];]\)], "Input", InitializationCell->True], Cell[BoxData[ \(indices[vec_] := Flatten[Outer[List, Apply[Sequence, Map[Range[0, # - 1] &, vec]]], Length[vec] - 1]\)], "Input", InitializationCell->True], Cell[BoxData[ \( (*\ indices[vec_] := Module[{k, ln, i, in, prev, j}, \[IndentingNewLine]k = Length[vec]; \[IndentingNewLine]ln = Product[vec[\([i]\)], {i, 1, k}]; \[IndentingNewLine]in = Table[0, {ln}]; prev = Table[0, {k}]; \[IndentingNewLine]For[i = 1, i \[LessEqual] ln, \(i++\), \[IndentingNewLine]in[\([i]\)] = prev; \[IndentingNewLine]j = k; \[IndentingNewLine]While[ prev[\([j]\)] \[Equal] vec[\([j]\)] - 1, prev[\([j]\)] = 0; \(j--\)]; \[IndentingNewLine]If[ j > 0, \(prev[\([j]\)]++\), Return[in]]]]\ \ *) \)], "Input", InitializationCell->True], Cell[BoxData[ \(maxmult[p_, x_] := Module[{pp, t, dg, j, px}, \[IndentingNewLine] (*\ Returns\ maximum\ multiplicity\ of\ the\ roots\ of\ polynomial\ p\ \ in\ the\ variable\ x\ *) \[IndentingNewLine]px = Expand[p]; \[IndentingNewLine]pp = Factor[px] /. {a_^\((m_)\) \[Rule] t[m]}; dg = Exponent[px, x]; \[IndentingNewLine]For[j = dg, j \[GreaterEqual] 0, \(j--\), If[\((pp /. {t[j] \[Rule] 0})\) \[Equal] 0, Return[j]]]; \[IndentingNewLine]Return[1]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(FindDegree[f_] := Module[{mat, i, j, cfd, maxsize}, \[IndentingNewLine] (*\ Finds\ the\ minimum\ order\ of\ the\ recurrence\ satisfied\ by\ an\ \ externally\[IndentingNewLine]defined\ function\ f . \ \(Note : \ If\ f\ contains\ symbols\ as\ well\ as\ numbers\), \ be\ sure\ to\[IndentingNewLine]include\ appropriate\ Expand\ and\ \ Simplify\ commands\ in\ its\ \(\(definition\)\(.\)\)\ \ \ *) \[IndentingNewLine]maxsize = 1; cfd = 2; \[IndentingNewLine]While[ cfd \[GreaterEqual] maxsize, \[IndentingNewLine]maxsize = maxsize + 3; \[IndentingNewLine]mat := Table[f[i + j], {i, 0, maxsize}, {j, 0, maxsize}]; \[IndentingNewLine]cfd = maxsize + 1 - Length[NullSpace[mat]]]; \[IndentingNewLine]Return[ cfd]]\)], "Input", InitializationCell->True], Cell[BoxData[ \(companion[f_, x_] := Module[{n, aa, cc, i, j}, \[IndentingNewLine] (*\ Returns\ the\ companion\ matrix\ of\ the\ polynomial\ f\ in\ x\ \ \ *) \[IndentingNewLine]n = Exponent[f, x]; \[IndentingNewLine]aa = Table[0, {n}, {n}]; \[IndentingNewLine]cc = CoefficientList[f, x]; \[IndentingNewLine]For[i = 2, i \[LessEqual] n, \(i++\), aa[\([i, i - 1]\)] = 1]; \[IndentingNewLine]For[j = 1, j \[LessEqual] n, \(j++\), aa[\([1, j]\)] = \(-cc[\([n + 1 - j]\)]\)/ cc[\([n + 1]\)]]; \[IndentingNewLine]Return[aa]]\)], "Input", InitializationCell->True], Cell[BoxData[ \( (*\ Here\ is\ a\ routine\ for\ the\ Kronecker\ product\ of\ two\ square\ \ matrices\ \[IndentingNewLine]\(kronecker[a_, b_] := Module[{m, n, c, i, i1, i2, j}, \[IndentingNewLine]m = \(Dimensions[a]\)[\([1]\)]; n = \(Dimensions[b]\)[\([1]\)]; \[IndentingNewLine]c = Table[0, {m\ n}, {m\ n}]; \[IndentingNewLine]For[i = 1, i \[LessEqual] m\ n, \(i++\), \[IndentingNewLine]i1 = Mod[i - 1, m] + 1; i2 = Ceiling[i/m]; \[IndentingNewLine]For[j = 1, j \[LessEqual] m\ n, \(j++\), \[IndentingNewLine]\(c[\([i, j]\)] = b[\([i2, Ceiling[j/m]]\)]\ a[\([i1, Mod[j - 1, m] + 1]\)];\)]]; \[IndentingNewLine]Return[ c]];\)*) \)], "Input", InitializationCell->True], Cell[BoxData[ \(kronecker[M_, N_] := Map[Flatten, Flatten[Transpose[Outer[Times, M, N], {1, 3, 2, 4}], 1]]\)], "Input", InitializationCell->True] }, Closed]] }, Open ]] }, FrontEndVersion->"5.0 for Microsoft Windows", ScreenRectangle->{{0, 1280}, {0, 937}}, AutoGeneratedPackage->None, WindowSize->{1014, 890}, WindowMargins->{{0, Automatic}, {Automatic, 0}}, Magnification->1 ] (******************************************************************* 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->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1776, 53, 64, 0, 95, "Title"], Cell[1843, 55, 103, 6, 83, "Text"], Cell[CellGroupData[{ Cell[1971, 65, 34, 0, 38, "Subsection"], Cell[2008, 67, 2001, 81, 71, "Text"], Cell[4012, 150, 167, 3, 33, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[4216, 158, 43, 0, 38, "Subsection"], Cell[4262, 160, 672, 29, 33, "Text"], Cell[4937, 191, 109, 2, 30, "Input"], Cell[5049, 195, 54, 0, 33, "Text"], Cell[5106, 197, 69, 1, 30, "Input"], Cell[5178, 200, 274, 7, 52, "Text"], Cell[5455, 209, 93, 1, 30, "Input"], Cell[5551, 212, 349, 6, 52, "Text"], Cell[5903, 220, 231, 6, 33, "Text"], Cell[6137, 228, 786, 22, 71, "Text"], Cell[6926, 252, 313, 7, 52, "Text"], Cell[7242, 261, 186, 6, 33, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[7465, 272, 53, 0, 38, "Subsection"], Cell[7521, 274, 190, 3, 70, "Input"], Cell[CellGroupData[{ Cell[7736, 281, 116, 2, 30, "Input"], Cell[7855, 285, 199, 4, 25, "Print"], Cell[8057, 291, 64, 1, 25, "Print"], Cell[8124, 294, 206, 4, 25, "Print"], Cell[8333, 300, 167, 3, 42, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[8549, 309, 58, 0, 38, "Subsection"], Cell[8610, 311, 43, 1, 30, "Input"], Cell[8656, 314, 261, 6, 50, "Input"], Cell[8920, 322, 111, 2, 50, "Input"], Cell[CellGroupData[{ Cell[9056, 328, 88, 1, 30, "Input"], Cell[9147, 331, 193, 4, 25, "Print"], Cell[9343, 337, 74, 1, 25, "Print"], Cell[9420, 340, 206, 4, 25, "Print"], Cell[9629, 346, 314, 5, 48, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[9980, 356, 51, 1, 30, "Input"], Cell[10034, 359, 296, 5, 48, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[10379, 370, 64, 0, 38, "Subsection"], Cell[10446, 372, 38, 1, 30, "Input"], Cell[10487, 375, 259, 6, 50, "Input"], Cell[10749, 383, 111, 2, 50, "Input"], Cell[CellGroupData[{ Cell[10885, 389, 56, 1, 30, "Input"], Cell[10944, 392, 268, 4, 29, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[11249, 401, 88, 1, 30, "Input"], Cell[11340, 404, 193, 4, 25, "Print"], Cell[11536, 410, 408, 10, 25, "Print"], Cell[11947, 422, 206, 4, 25, "Print"], Cell[12156, 428, 578, 9, 85, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[12771, 442, 46, 1, 30, "Input"], Cell[12820, 445, 273, 4, 47, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[13142, 455, 56, 0, 38, "Subsection"], Cell[13201, 457, 442, 7, 150, "Input"], Cell[CellGroupData[{ Cell[13668, 468, 76, 1, 30, "Input"], Cell[13747, 471, 178, 4, 25, "Print"], Cell[13928, 477, 64, 1, 25, "Print"], Cell[13995, 480, 204, 4, 25, "Print"], Cell[14202, 486, 51, 1, 29, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[14290, 492, 87, 1, 30, "Input"], Cell[14380, 495, 193, 4, 25, "Print"], Cell[14576, 501, 64, 1, 25, "Print"], Cell[14643, 504, 204, 4, 25, "Print"], Cell[14850, 510, 63, 1, 29, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[14950, 516, 109, 2, 30, "Input"], Cell[15062, 520, 199, 4, 25, "Print"], Cell[15264, 526, 64, 1, 25, "Print"], Cell[15331, 529, 204, 4, 25, "Print"], Cell[15538, 535, 111, 2, 45, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[15686, 542, 120, 2, 30, "Input"], Cell[15809, 546, 205, 4, 25, "Print"], Cell[16017, 552, 74, 1, 25, "Print"], Cell[16094, 555, 206, 4, 25, "Print"], Cell[16303, 561, 323, 5, 65, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[16663, 571, 51, 1, 30, "Input"], Cell[16717, 574, 307, 5, 65, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[17061, 584, 131, 2, 30, "Input"], Cell[17195, 588, 211, 4, 25, "Print"], Cell[17409, 594, 64, 1, 25, "Print"], Cell[17476, 597, 206, 4, 25, "Print"], Cell[17685, 603, 222, 3, 45, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[17944, 611, 142, 2, 30, "Input"], Cell[18089, 615, 217, 4, 25, "Print"], Cell[18309, 621, 64, 1, 25, "Print"], Cell[18376, 624, 206, 4, 25, "Print"], Cell[18585, 630, 163, 2, 42, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[18785, 637, 153, 2, 30, "Input"], Cell[18941, 641, 223, 4, 25, "Print"], Cell[19167, 647, 64, 1, 25, "Print"], Cell[19234, 650, 208, 4, 25, "Print"], Cell[19445, 656, 302, 4, 79, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[19796, 666, 54, 0, 38, "Subsection"], Cell[19853, 668, 45, 1, 30, "Input"], Cell[19901, 671, 224, 5, 50, "Input"], Cell[CellGroupData[{ Cell[20150, 680, 55, 1, 30, "Input"], Cell[20208, 683, 211, 4, 29, "Output"] }, Open ]], Cell[20434, 690, 111, 2, 50, "Input"], Cell[CellGroupData[{ Cell[20570, 696, 87, 1, 30, "Input"], Cell[20660, 699, 193, 4, 25, "Print"], Cell[20856, 705, 629, 17, 25, "Print"], Cell[21488, 724, 204, 4, 25, "Print"], Cell[21695, 730, 986, 14, 124, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[22718, 749, 46, 1, 30, "Input"], Cell[22767, 752, 282, 4, 47, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[23098, 762, 53, 0, 38, "Subsection"], Cell[23154, 764, 259, 6, 50, "Input"], Cell[23416, 772, 175, 3, 70, "Input"], Cell[CellGroupData[{ Cell[23616, 779, 155, 2, 30, "Input"], Cell[23774, 783, 199, 4, 25, "Print"], Cell[23976, 789, 64, 1, 25, "Print"], Cell[24043, 792, 204, 4, 25, "Print"], Cell[24250, 798, 116, 2, 29, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[24415, 806, 57, 0, 38, "Subsection"], Cell[24475, 808, 203, 4, 50, "Input"], Cell[CellGroupData[{ Cell[24703, 816, 55, 1, 30, "Input"], Cell[24761, 819, 84, 1, 29, "Output"] }, Open ]], Cell[24860, 823, 168, 3, 70, "Input"], Cell[CellGroupData[{ Cell[25053, 830, 109, 2, 30, "Input"], Cell[25165, 834, 199, 4, 25, "Print"], Cell[25367, 840, 64, 1, 25, "Print"], Cell[25434, 843, 204, 4, 25, "Print"], Cell[25641, 849, 142, 2, 45, "Output"] }, Open ]], Cell[25798, 854, 223, 4, 90, "Input"], Cell[CellGroupData[{ Cell[26046, 862, 120, 2, 30, "Input"], Cell[26169, 866, 205, 4, 25, "Print"], Cell[26377, 872, 74, 1, 25, "Print"], Cell[26454, 875, 206, 4, 25, "Print"], Cell[26663, 881, 551, 8, 99, "Output"] }, Open ]], Cell[27229, 892, 68, 0, 33, "Text"], Cell[CellGroupData[{ Cell[27322, 896, 124, 2, 50, "Input"], Cell[27449, 900, 498, 8, 79, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[27996, 914, 63, 0, 38, "Subsection"], Cell[28062, 916, 120, 2, 50, "Input"], Cell[CellGroupData[{ Cell[28207, 922, 118, 2, 30, "Input"], Cell[28328, 926, 193, 4, 25, "Print"], Cell[28524, 932, 384, 9, 25, "Print"], Cell[28911, 943, 204, 4, 25, "Print"], Cell[29118, 949, 226, 4, 45, "Output"] }, Open ]], Cell[29359, 956, 183, 3, 70, "Input"], Cell[CellGroupData[{ Cell[29567, 963, 152, 2, 30, "Input"], Cell[29722, 967, 199, 4, 25, "Print"], Cell[29924, 973, 495, 13, 25, "Print"], Cell[30422, 988, 204, 4, 25, "Print"], Cell[30629, 994, 488, 7, 85, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[31154, 1006, 46, 1, 30, "Input"], Cell[31203, 1009, 204, 3, 46, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[31456, 1018, 71, 0, 38, "Subsection"], Cell[31530, 1020, 55, 1, 30, "Input"], Cell[CellGroupData[{ Cell[31610, 1025, 75, 1, 30, "Input"], Cell[31688, 1028, 178, 4, 25, "Print"], Cell[31869, 1034, 74, 1, 25, "Print"], Cell[31946, 1037, 206, 4, 25, "Print"], Cell[32155, 1043, 89, 1, 45, "Output"] }, Open ]], Cell[32259, 1047, 271, 5, 110, "Input"], Cell[CellGroupData[{ Cell[32555, 1056, 128, 2, 30, "Input"], Cell[32686, 1060, 211, 4, 25, "Print"], Cell[32900, 1066, 74, 1, 25, "Print"], Cell[32977, 1069, 206, 4, 25, "Print"], Cell[33186, 1075, 89, 1, 45, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[33324, 1082, 73, 0, 38, "Subsection"], Cell[33400, 1084, 215, 5, 50, "Input"], Cell[CellGroupData[{ Cell[33640, 1093, 57, 1, 30, "Input"], Cell[33700, 1096, 181, 3, 48, "Output"] }, Open ]], Cell[33896, 1102, 57, 1, 30, "Input"], Cell[CellGroupData[{ Cell[33978, 1107, 76, 1, 30, "Input"], Cell[34057, 1110, 180, 4, 25, "Print"], Cell[34240, 1116, 74, 1, 25, "Print"], Cell[34317, 1119, 206, 4, 25, "Print"], Cell[34526, 1125, 2259, 32, 413, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[36822, 1162, 51, 1, 30, "Input"], Cell[36876, 1165, 2170, 32, 418, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[39083, 1202, 129, 2, 45, "Input"], Cell[39215, 1206, 115, 2, 42, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[39379, 1214, 70, 0, 73, "Section"], Cell[39452, 1216, 7865, 138, 1630, "Input", InitializationCell->True], Cell[47320, 1356, 177, 4, 30, "Input", InitializationCell->True], Cell[47500, 1362, 691, 12, 190, "Input", InitializationCell->True], Cell[48194, 1376, 579, 11, 130, "Input", InitializationCell->True], Cell[48776, 1389, 896, 16, 210, "Input", InitializationCell->True], Cell[49675, 1407, 661, 12, 170, "Input", InitializationCell->True], Cell[50339, 1421, 933, 17, 190, "Input", InitializationCell->True], Cell[51275, 1440, 167, 4, 30, "Input", InitializationCell->True] }, Closed]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)