(*********************************************************************** Mathematica-Compatible Notebook This notebook can be used on any computer system with Mathematica 3.0, MathReader 3.0, or any compatible application. The data for the notebook starts with the line of 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[ 99711, 3698]*) (*NotebookOutlinePosition[ 100592, 3728]*) (* CellTagsIndexPosition[ 100548, 3724]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell[TextData[{ "How to do ", StyleBox["Monthly", FontSlant->"Italic"], " problems with your computer: 27 worked-out examples" }], "Subtitle"], Cell["M. Petkovsek", "Subsubtitle"], Cell[TextData[{ "This notebook contains automatic or semi-automatic solutions of 27 ", StyleBox["American Mathematical Monthly", FontSlant->"Italic"], " problems that have appeared in the years 1982-1996. It accompanies the \ paper \n\nIstvan Nemes, Marko Petkovsek, Herbert S. Wilf, Doron Zeilberger: \ How to do ", StyleBox["Monthly", FontSlant->"Italic"], " problems with your computer, ", StyleBox["Amer. Math. Monthly ", FontSlant->"Italic"], StyleBox["104", FontWeight->"Bold"], " (1997) 505--519,\n\navailable also at \ http://www.cis.upenn.edu/~wilf/NPWZ.pdf.\n\n", StyleBox["To use this notebook", FontWeight->"Bold"], " you can load four additional files into ", StyleBox["Mathematica", FontSlant->"Italic"], ", as described below. If you do that then you will be able to watch the \ algorithms actually running and producing output on your own computer. \ Alternatively, you can skip that step, and then just double-click on the \ outermost bracket of each cell in this notebook. Then you will see the exact \ dialogue of input and input that produces the solution of each problem, just \ as if you had run the algorithms yourself. So your choice is whether is you \ want actually to run each line that is to be executed in this notebook, in \ which case you will need to load the packages described below, or whether you \ are willing to look at only the input line that calls each algorithm and a \ transcript of what output the algorithm returned." }], "Text"], Cell[CellGroupData[{ Cell["Loading the packages", "Subsection"], Cell[TextData[{ "Before running the examples the following four files need to be loaded \ into ", StyleBox["Mathematica", FontSlant->"Italic"], ":\n\n1. ", StyleBox["qzeil.m", FontWeight->"Bold"], " available from \ http://www.risc.uni-linz.ac.at/research/combinat/risc/software/,\n2. ", StyleBox["zb.m", FontWeight->"Bold"], " available from \ http://www.risc.uni-linz.ac.at/research/combinat/risc/software/,\n3. ", StyleBox["gosper.m", FontWeight->"Bold"], " available from http://www.cis.upenn.edu/~wilf/progs.html,\n4. ", StyleBox["hyper.m", FontWeight->"Bold"], " available from ", "http://www.cis.upenn.edu/~wilf/progs.html", ".\n\nIf all these files are put into the same directory, to which the \ current working directory is set by using the ", StyleBox["SetDirectory", FontWeight->"Bold"], " command, then the files are loaded simply as follows:" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(<< qzeil.m\)], "Input", PageWidth->Infinity], Cell[BoxData[ \("Axel Riese's q-Zeilberger implementation version 1.8 loaded"\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(<< zb.m\)], "Input", PageWidth->Infinity], Cell[BoxData[ \(SUM::"shdw" \( : \ \) "Symbol \!\(\"SUM\"\) appears in multiple contexts \!\({\"fastZeil`\", \ \"qZeil`\"}\); definitions in context \!\(\"fastZeil`\"\) may shadow or be \ shadowed by other definitions."\)], "Message"], Cell[BoxData[ \("Fast Zeilberger by Peter Paule and Markus Schorn. (V 2.4test)"\)], "Print"], Cell[BoxData[ InterpretationBox[\("Systembreaker = "\[InvisibleSpace]ENullspace\), SequenceForm[ "Systembreaker = ", ENullspace], Editable->False]], "Print"] }, Closed]], Cell[TextData[{ "Remark: This warning message explains why ", StyleBox["SUM", FontWeight->"Bold"], " from the ", StyleBox["qzeil.m", FontWeight->"Bold"], " package is called ", StyleBox["qzeil`SUM", FontWeight->"Bold"], " in the sequel (see Problem 6407). Thanks to the automatic prefixing of \ one of the two identical names by its context, the shadowing has no ill \ effects." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(<< gosper.m\)], "Input", PageWidth->Infinity], Cell[BoxData[ \("N.B.: Besides GosperSum and GosperFunction, this package also contains \ FactorialSimplify (alias FS), and WZ."\)], "Print"] }, Closed]], Cell[BoxData[ \(<< hyper.m\)], "Input", PageWidth->Infinity] }, Open ]], Cell[CellGroupData[{ Cell["6407", "Subsection", Evaluatable->False], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{ RowBox[{"Define", " ", "[", "\[NegativeThinSpace]", GridBox[{ {"n"}, {"k"} }], "\[NegativeThinSpace]", "]"}], " ", "by", " ", "means", " ", "of", " ", "the", " ", RowBox[{"relation", " ", "[", "\[NegativeThinSpace]", GridBox[{ {"n"}, {"k"} }], "\[NegativeThinSpace]", "]"}]}], "=", \(F\_\(n, k\)/F\_\(k, k\)\)}], ",", " ", \(F\_\(n, k\)\ = \ \(\((q\^n - 1)\) \((q\^\(n - 1\) - 1)\) ... \) \((q\^\(n - k + 1\) - 1)\)\), ",", " ", RowBox[{ RowBox[{"so", " ", RowBox[{"that", " ", "[", "\[NegativeThinSpace]", GridBox[{ {"n"}, {"k"} }], "\[NegativeThinSpace]", "]"}], "is", " ", "the", " ", "so"}], "-", RowBox[{ \(called\ Gaussian\ polynomial . \ Prove\ the\ identity\), "\n", FormBox[ RowBox[{ \(\[Sum]\+\(k = 1\)\%n q\^k\/\(1 - q\^k\)\), " ", "=", " ", RowBox[{\(\[Sum]\+\(k = 1\)\%n\), RowBox[{\(\(\((\(-1\))\)\^\(k - 1\)\ \)\/\(1 - q\^k\)\), RowBox[{ RowBox[{\(q\^\(1\/2\ k\ \((k + 1)\)\)\), "[", GridBox[{ {"n"}, {"k"} }], "]"}], " ", "."}]}]}]}], "TextForm"]}]}]}], TextForm]], "Text", FontSlant->"Italic"], Cell[CellGroupData[{ Cell[BoxData[ \(qZeil[ \((\(-1\))\)^\((k - 1)\) q^\((k \((k + 1)\)/2)\) qBinomial[n, k, q]/\((1 - q^k)\), {k, 1, n}, n, 1]\)], "Input"], Cell[BoxData[ \(qZeil`SUM[n] == \(-\(q\^n\/\(\(-1\) + q\^n\)\)\) + qZeil`SUM[\(-1\) + n]\)], "Output"] }, Closed]], Cell[TextData[{ "This recurrence is obviously satisfied by ", Cell[BoxData[ FormBox[ StyleBox[\(\[Sum]\+\(k = 1\)\%nq\^k\/\(1 - q\^k\)\), FontSlant->"Italic"], TraditionalForm]]], " . As both sums are 0 for ", StyleBox["n = ", FontSlant->"Italic"], "0, they are equal for all ", StyleBox["n", FontSlant->"Italic"], "." }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["E 3021", "Subsection", Evaluatable->False], Cell["Let", "Text", FontSlant->"Italic"], Cell[TextData[{ " \t", Cell[BoxData[ \(TraditionalForm\`p\_n\)]], "(x) = ", Cell[BoxData[ FormBox[ RowBox[{\(\[Sum]\+\(k = 0\)\%n\), RowBox[{ SuperscriptBox[ RowBox[{"(", "\[NegativeThinSpace]", GridBox[{ {"n"}, {"k"} }], "\[NegativeThinSpace]", ")"}], "2"], " ", \(\((1 + \ x)\)\^k\), " ", \(\((1 - \ x)\)\^\(n - k\)\)}]}], TraditionalForm]]], "." }], "Text", FontSlant->"Italic"], Cell[TextData[{ "Express ", Cell[BoxData[ \(TraditionalForm\`p\_n\)]], "(x) as an explicit function of ", StyleBox["1 -", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\(\ \ x\^2\)\)], FontSlant->"Italic"], "." }], "Text", FontSlant->"Italic"], Cell[TextData[{ "We provide a partial solution to this problem by expressing ", Cell[BoxData[ \(TraditionalForm\`p\_n\)]], "(x) in terms of the n-th Legendre polynomial ", " ", Cell[BoxData[ \(TraditionalForm\`P\_n\)]], "(x)." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[n, k]\^2\ \((1 + x)\)\^k\ \((1 - x)\)\^\(n - k\), {k, 0, n}, n, 1]\)], "Input", PageWidth->Infinity], Cell[BoxData[ \({}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[n, k]\^2\ \((1 + x)\)\^k\ \((1 - x)\)\^\(n - k\), {k, 0, n}, n, 2]\)], "Input", PageWidth->Infinity], Cell[BoxData[ \("If `n' is a natural number, then:"\)], "Print"], Cell[BoxData[ \({\(-4\)\ \((1 + n)\)\ x\^2\ SUM[n] + 2\ \((3 + 2\ n)\)\ SUM[1 + n] + \((\(-2\) - n)\)\ SUM[2 + n] == 0}\)], "Output"] }, Open ]], Cell[TextData[{ "This recurrence is similar to that satisfied by the ", StyleBox["n", FontSlant->"Italic"], "-th Legendre polynomial, except that the latter one does not have \ numerical factors 4 and 2, and has a factor of ", StyleBox["x", FontSlant->"Italic"], " in the middle term instead of ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox[\(x\^2\), FontSlant->"Italic"], " ", "in", " ", "the", " ", "trailing", " ", "one"}], TraditionalForm]]], ". We can remedy this by substituting", StyleBox[" ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`\((2 x)\)^n\ P\_n\)], FontSlant->"Italic"], StyleBox["(1/x)", FontSlant->"Italic"], " for", StyleBox[" ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`p\_n\)], FontSlant->"Italic"], StyleBox["(x)", FontSlant->"Italic"], ":" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(%[\([1, 1]\)] /. \ SUM[n_] -> \((2 x)\)^n\ P[n, 1/x]\)], "Input"], Cell[BoxData[ \(\(-2\^\(2 + n\)\)\ \((1 + n)\)\ x\^\(2 + n\)\ P[n, 1\/x] + 2\^\(2 + n\)\ \((3 + 2\ n)\)\ x\^\(1 + n\)\ P[1 + n, 1\/x] + 2\^\(2 + n\)\ \((\(-2\) - n)\)\ x\^\(2 + n\)\ P[2 + n, 1\/x]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% /. x -> 1/x\)], "Input"], Cell[BoxData[ \(\(-2\^\(2 + n\)\)\ \((1 + n)\)\ \((1\/x)\)\^\(2 + n\)\ P[n, x] + 2\^\(2 + n\)\ \((3 + 2\ n)\)\ \((1\/x)\)\^\(1 + n\)\ P[1 + n, x] + 2\^\(2 + n\)\ \((\(-2\) - n)\)\ \((1\/x)\)\^\(2 + n\)\ P[2 + n, x]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Factor[%]\)], "Input"], Cell[BoxData[ \(\(1\/x\^2\(( 2\^\(2 + n\)\ \((1\/x)\)\^n\ \((\(-P[n, x]\) - n\ P[n, x] + 3\ x\ P[1 + n, x] + 2\ n\ x\ P[1 + n, x] - 2\ P[2 + n, x] - n\ P[2 + n, x])\)) \)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Select[%, \ \(! FreeQ[#, P]\)&]\)], "Input"], Cell[BoxData[ \(\(-P[n, x]\) - n\ P[n, x] + 3\ x\ P[1 + n, x] + 2\ n\ x\ P[1 + n, x] - 2\ P[2 + n, x] - n\ P[2 + n, x]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Collect[\(-%\), {P[n, x], P[n + 1, x], P[n + 2, x]}]\)], "Input"], Cell[BoxData[ \(\((1 + n)\)\ P[n, x] + \((\(-3\)\ x - 2\ n\ x)\)\ P[1 + n, x] + \((2 + n)\)\ P[2 + n, x]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Factor\ /@\ % == \ 0\)], "Input"], Cell[BoxData[ \(\((1 + n)\)\ P[n, x] - \((3 + 2\ n)\)\ x\ P[1 + n, x] + \((2 + n)\)\ P[2 + n, x] == 0\)], "Output"] }, Closed]], Cell[TextData[{ "This is the well-known three-term recurrence satisfied by the ", StyleBox["n", FontSlant->"Italic"], "-th Legendre polynomial", StyleBox[" ", FontSlant->"Italic"], Cell[BoxData[ \(TraditionalForm\`P\_n\)], FontSlant->"Italic"], StyleBox["(x)", FontSlant->"Italic"], ". As the first two polynomials in the sequence agree, we have found that", StyleBox[" ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{ RowBox[{ FormBox[\(p\_n\), "TraditionalForm"], "(", "x", ")"}], " ", "=", " ", \(\((2 x)\)^n\ P\_n\)}]}], TraditionalForm]], FontSlant->"Italic"], StyleBox["(1/x)", FontSlant->"Italic"], ":" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ \((2 x)\)^n\ LegendreP[n, 1/x]\ - \ Sum[Binomial[n, k]\^2\ \((1 + x)\)\^k\ \((1 - x)\)\^\(n - k\), {k, 0, n}], {n, 0, 10}] // Simplify\)], "Input"], Cell[BoxData[ \({0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}\)], "Output"] }, Closed]] }, Open ]], Cell[CellGroupData[{ Cell["E 3022", "Subsection", Evaluatable->False], Cell[TextData[{ "Show that, for any \[Alpha] > 0 and any positive integer ", StyleBox["N", FontSlant->"Italic"], "," }], "Text", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(\[Sum]\+\(k = 1\)\%N\), RowBox[{\(\((\(-1\))\)\^\(k - 1\)\), " ", TagBox[ RowBox[{"(", GridBox[{ {"N"}, {"k"} }], ")"}], Binomial, Editable->False], \(\(\ k\)\/\(1 + \((k - 1)\)\ \[Alpha]\)\)}]}], " ", "=", " ", \(\[Product]\+\(k = 1\)\%\(N - 1 \)\(\(k + 1\)\/\(k + \[Alpha]\^\(-1\)\) . \)\)}], TextForm]], "Text", FontSlant->"Italic"], Cell[TextData[{ "This is equivalent to showing that ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox[\(\[Sum]\+\(k = 1\)\%NF \((N, k)\)\), FontSlant->"Italic"], StyleBox[" ", FontSlant->"Italic"], StyleBox["=", FontSlant->"Italic"], RowBox[{ StyleBox["1", FontSlant->"Italic"], " ", "where"}]}], TextForm]]] }], "Text"], Cell[BoxData[ FormBox[ RowBox[{\(F \((n, k)\)\), "=", RowBox[{ FractionBox[ RowBox[{\(\((\(-1\))\)\^\(k - 1\)\), " ", TagBox[\(\((\[Alpha]\^\(-1\))\)\_N\), Pochhammer]}], \(\(\((k - 1)\)!\)\ \(\((N - k)\)!\)\ \((k - 1 + \[Alpha]\^\(-1\))\)\)], "."}]}], TextForm]], "Text", FontSlant->"Italic"], Cell["\<\ The WZ method succeeds and returns the corresponding rational certificate:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(WZ[\((\(-1\))\)^\((k - 1)\) Pochhammer[1/alpha, N]/ \((\(\((k - 1)\)!\) \(\((N - k)\)!\) \((k - 1 + 1/alpha)\))\), N, k] \)], "Input"], Cell[BoxData[ \(\(\((\(-1\) + k)\)\ \((1 - alpha + alpha\ k)\)\)\/\(alpha\ \((\(-1\) + k - N)\)\ N\)\)], "Output"] }, Closed]], Cell[TextData[{ "It only remains to check that the sum equals 1 for one specific value of ", StyleBox["N:", FontSlant->"Italic"] }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Sum[ \((\(-1\))\)^\((k - 1)\) Pochhammer[1/alpha, N]/ \((\(\((k - 1)\)!\) \(\((N - k)\)!\) \((k - 1 + 1/alpha)\))\), { k, 1, N}] /. N -> 1\)], "Input"], Cell[BoxData[ \(1\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["E 3065", "Subsection", Evaluatable->False], Cell[TextData[{ StyleBox[ "Let n\[GreaterEqual]0 be any integer and let k be any integer such that k\ \[GreaterEqual]n+1. Then find a closed formula for ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ StyleBox[ RowBox[{\(\[Sum]\+\(j = 0\)\%n\), FractionBox[ RowBox[{\(\((\(-1\))\)\^j\), " ", TagBox[ RowBox[{"(", GridBox[{ {"k"}, {"j"} }], ")"}], Binomial, Editable->False], " ", TagBox[ RowBox[{"(", GridBox[{ {\(\(-j\) + k - 1\)}, {\(n - j\)} }], ")"}], Binomial, Editable->False]}], \(j + 1\)]}], FontSlant->"Italic"], TraditionalForm]]], StyleBox[".", FontSlant->"Italic"] }], "Text"], Cell["\<\ Zeilberger's algorithm finds an inhomogeneous recurrence of order one:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[\((\(-1\))\)^j\ Binomial[k, j] Binomial[k - 1 - j, n - j]/\((j + 1)\), \ {j, 0, n}, n, 1]\)], "Input",\ PageWidth->Infinity], Cell[BoxData[ \("If `n' is a natural number, then:"\)], "Print"], Cell[BoxData[ \({\((\(-2\) - n)\)\ SUM[n] + \((\(-2\) - n)\)\ SUM[1 + n] == \(-Binomial[k, 1 + n]\)}\)], "Output"] }, Closed]], Cell["\<\ To solve it, we shift it down by 1 and multiply SUM[n] by (-1)^n:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(% /. n -> n - 1\)], "Input"], Cell[BoxData[ \({\((\(-1\) - n)\)\ SUM[\(-1\) + n] + \((\(-1\) - n)\)\ SUM[n] == \(-Binomial[k, n]\)}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(%\ /. \ SUM[n_] -> \ a[n]/\((\(-1\))\)^n\)], "Input"], Cell[BoxData[ \({\((\(-1\))\)\^\(1 - n\)\ \((\(-1\) - n)\)\ a[\(-1\) + n] + \((\(-1\))\)\^\(-n\)\ \((\(-1\) - n)\)\ a[n] == \(-Binomial[k, n]\)} \)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[%, a[n]]\)], "Input"], Cell[BoxData[ \({{a[n] \[Rule] \(a[\(-1\) + n] + n\ a[\(-1\) + n] + \((\(-1\))\)\^n\ Binomial[k, n]\)\/\(1 + n\)}}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(a[n] /. %[\([1]\)]\)], "Input"], Cell[BoxData[ \(\(a[\(-1\) + n] + n\ a[\(-1\) + n] + \((\(-1\))\)\^n\ Binomial[k, n]\)\/\(1 + n\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Collect[%, a[n - 1]]\)], "Input"], Cell[BoxData[ \(\((1\/\(1 + n\) + n\/\(1 + n\))\)\ a[\(-1\) + n] + \(\((\(-1\))\)\^n\ Binomial[k, n]\)\/\(1 + n\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Together\ /@\ %\)], "Input"], Cell[BoxData[ \(a[\(-1\) + n] + \(\((\(-1\))\)\^n\ Binomial[k, n]\)\/\(1 + n\)\)], "Output"] }, Closed]], Cell["This shows that ", "Text"], Cell[BoxData[ FormBox[ RowBox[{\(a(n)\), "=", RowBox[{"C", "+", RowBox[{\(\[Sum]\+\(j = 0\)\%n\), RowBox[{ FractionBox[ RowBox[{\(\((\(-1\))\)\^j\), " ", TagBox[ RowBox[{"(", GridBox[{ {"k"}, {"j"} }], ")"}], Binomial, Editable->False]}], \(j + 1\)], "."}]}]}]}], TraditionalForm]], "Text"], Cell["Gosper's algorithm succeeds on the above sum", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(%[\([2]\)] /. n -> j\)], "Input"], Cell[BoxData[ \(\(\((\(-1\))\)\^j\ Binomial[k, j]\)\/\(1 + j\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(GosperSum[%, {j, 0, n}]\)], "Input", PageWidth->Infinity], Cell[BoxData[ \(1\/\(1 + k\) - \(\((\(-1\))\)\^n\ \((\(-k\) + n)\)\ Binomial[k, n]\)\/\(\((1 + k)\)\ \((1 + n)\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(%\ /. \ Binomial[k, n] -> Binomial[k, n + 1] \((n + 1)\)/\((k - n)\)\)], "Input"], Cell[BoxData[ \(1\/\(1 + k\) - \(\((\(-1\))\)\^n\ \((\(-k\) + n)\)\ Binomial[k, 1 + n]\)\/\(\((1 + k)\)\ \((k - n)\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Factor\ /@\ %\)], "Input"], Cell[BoxData[ \(1\/\(1 + k\) + \(\((\(-1\))\)\^n\ Binomial[k, 1 + n]\)\/\(1 + k\)\)], "Output"] }, Closed]], Cell["To obtain a[n], we multiply again by (-1)^n:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(% \((\(-1\))\)^n // Expand\)], "Input"], Cell[BoxData[ \(\((\(-1\))\)\^n\/\(1 + k\) + \(\((\(-1\))\)\^\(2\ n\)\ Binomial[k, 1 + n]\)\/\(1 + k\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% /. \((\(-1\))\)^\((2 n)\) -> 1\)], "Input"], Cell[BoxData[ \(\((\(-1\))\)\^n\/\(1 + k\) + Binomial[k, 1 + n]\/\(1 + k\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% // Factor\)], "Input"], Cell[BoxData[ \(\(\((\(-1\))\)\^n + Binomial[k, 1 + n]\)\/\(1 + k\)\)], "Output"] }, Closed]], Cell["\<\ To find C, we compare this with the original sum for a few values of n (in \ fact, one would suffice):\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[% - Sum[\(\((\(-1\))\)\^j\ Binomial[k, j]\ Binomial[k - 1 - j, n - j]\)\/\(j + 1\), {j, 0, n}], {n, 0, 10}] // Together\)], "Input"], Cell[BoxData[ \({0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}\)], "Output"] }, Closed]], Cell["Thus C = 0 and our sum is", "Text"], Cell[BoxData[ \(TextForm \`\(\(\((\(-1\))\)\^n + Binomial[k, 1 + n]\)\/\(1 + k\) . \)\)], "Text", FontSlant->"Italic"] }, Closed]], Cell[CellGroupData[{ Cell["E 3088", "Subsection", Evaluatable->False], Cell[TextData[{ StyleBox["Show that, for every positive integer n, ", FontSlant->"Italic"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(\[Sum]\+\(k = 1\)\%n\), FractionBox[ RowBox[{"k", " ", \(k!\), " ", TagBox[ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}], Binomial, Editable->False]}], \(n\^k\)]}], "=", "n"}], TraditionalForm]], FontSlant->"Italic"], StyleBox[".", FontSlant->"Italic"] }], "Text"], Cell["Gosper's algorithm does the job:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(GosperSum[\((k\ \(k!\) Binomial[n, k])\)/n^k, {k, 1, n}]\)], "Input", PageWidth->Infinity], Cell[BoxData[ \(n\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["6519", "Subsection"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(Let\ \(F(a, b, m, n)\)\), "=", FormBox[ RowBox[{\(\[Sum]\+\(k = 0\)\%m\), RowBox[{ TagBox[ RowBox[{"(", GridBox[{ {\(a - 2\ k + m + n\)}, {\(n - k\)} }], ")"}], Binomial, Editable->False], " ", TagBox[ RowBox[{"(", GridBox[{ {\(a + n\)}, {"k"} }], ")"}], Binomial, Editable->False], " ", TagBox[ RowBox[{"(", GridBox[{ {\(b + m\)}, {\(m - k\)} }], ")"}], Binomial, Editable->False]}]}], "TraditionalForm"]}], ",", " ", \(where\ m\ and\ n\ are\ nonnegative\ integers . \ Show\ that\ \(F(a, b, m, n)\) = \(F(b, a, n, m) . \)\)}], TraditionalForm]], "Text", FontSlant->"Italic"], Cell["\<\ Zeilberger's algorithm finds a recurrence of order four w.r.t. m satisfied by \ the left-hand sum:\ \>", "Text"], Cell[BoxData[ \(F[a_, b_, m_, n_] := Binomial[a + m + n - 2 k, n - k] Binomial[a + n, k] Binomial[b + m, m - k]\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[F[a, b, m, n], k, m, 1]\)], "Input", PageWidth->Infinity, FontFamily->"Courier New", FontWeight->"Bold", FontColor->GrayLevel[0], Background->GrayLevel[1]], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[F[a, b, m, n], k, m, 2]\)], "Input", PageWidth->Infinity, FontFamily->"Courier New", FontWeight->"Bold", FontColor->GrayLevel[0], Background->GrayLevel[1]], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[F[a, b, m, n], k, m, 3]\)], "Input", PageWidth->Infinity, FontFamily->"Courier New", FontWeight->"Bold", FontColor->GrayLevel[0], Background->GrayLevel[1]], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[F[a, b, m, n], k, m, 4]\)], "Input", PageWidth->Infinity, FontFamily->"Courier New", FontWeight->"Bold", FontColor->GrayLevel[0], Background->GrayLevel[1]], Cell[BoxData[ \({\(-3\)\ \((1 + b + m)\)\ \((2 + b + m)\)\ \((3 + b + m)\)\ F[k, m] + 2\ \((2 + b + m)\)\ \((3 + b + m)\)\ \((10 + a + b + 4\ m - 2\ n)\)\ F[k, 1 + m] - \((3 + b + m)\)\ \((53 + 5\ a + 5\ b - a\ b + 36\ m + 2\ a\ m + 2\ b\ m + 6\ m\^2 - 26\ n - 4\ a\ n - 4\ b\ n - 8\ m\ n)\)\ F[k, 2 + m] - \((7 + a + b + 2\ m)\)\ \((1 + 4\ a + 4\ b + a\ b + a\ m + b\ m + 8\ n + a\ n + b\ n + 2\ m\ n)\)\ F[k, 3 + m] + \((4 + m)\)\ \((4 + a + m)\)\ \((4 + a + b + m)\)\ F[k, 4 + m] == Delta[k, R\ F[k, m]]}\)], "Output"] }, Closed]], Cell["The same recurrence is also satisfied by the right-hand sum:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[F[b, a, n, m], k, m, 4]\)], "Input", PageWidth->Infinity, FontFamily->"Courier New", FontWeight->"Bold", FontColor->GrayLevel[0], Background->GrayLevel[1]], Cell[BoxData[ \({\(-3\)\ \((1 + b + m)\)\ \((2 + b + m)\)\ \((3 + b + m)\)\ F[k, m] + 2\ \((2 + b + m)\)\ \((3 + b + m)\)\ \((10 + a + b + 4\ m - 2\ n)\)\ F[k, 1 + m] - \((3 + b + m)\)\ \((53 + 5\ a + 5\ b - a\ b + 36\ m + 2\ a\ m + 2\ b\ m + 6\ m\^2 - 26\ n - 4\ a\ n - 4\ b\ n - 8\ m\ n)\)\ F[k, 2 + m] - \((7 + a + b + 2\ m)\)\ \((1 + 4\ a + 4\ b + a\ b + a\ m + b\ m + 8\ n + a\ n + b\ n + 2\ m\ n)\)\ F[k, 3 + m] + \((4 + m)\)\ \((4 + a + m)\)\ \((4 + a + b + m)\)\ F[k, 4 + m] == Delta[k, R\ F[k, m]]}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% == %%\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Closed]], Cell["\<\ Checking the equality for the first four values of m finishes the proof:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ Sum[F[a, b, m, n], {k, 0, m}] - Sum[F[b, a, n, m], {k, 0, m}]\n \ \ \ // FS, {m, 0, 3}]\)], "Input", PageWidth->Infinity, FontFamily->"Courier New", FontWeight->"Bold", FontColor->GrayLevel[0], Background->GrayLevel[1]], Cell[BoxData[ \({0, 0, 0, 0}\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["E 3190", "Subsection", Evaluatable->False], Cell["Gosper's algorithm does the job:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(GosperSum[ \(\((\(-1\))\)\^r\ \((N - 2 r)\)\ Binomial[j, r]\)\/Pochhammer[ N - r - j, j + 1], {r, 0, j}]\)], "Input", PageWidth->Infinity], Cell[BoxData[ \(0\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["E 3207", "Subsection", Evaluatable->False], Cell["Zeilberger's algorithm yields the desired recurrence:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[\((1 - k\/m)\)\ Binomial[2\ m, k]\ x\^k\ \((1 - x)\)\^\(2\ m - k\), { k, 0, m}, m, 1]\)], "Input", PageWidth->Infinity], Cell[BoxData[ \("If `m' is a natural number, then:"\)], "Print"], Cell[BoxData[ \({\(-SUM[m]\) + SUM[1 + m] == \(\((2 + m)\)\ \((1 - x)\)\^m\ \((\(-1\) + x)\)\ x\^\(1 + m\)\ Binomial[3 + 2\ m, 1 + m]\)\/\(2\ \((1 + 2\ m)\)\ \((3 + 2\ m)\)\)}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% /. m -> m - 1\)], "Input"], Cell[BoxData[ \({\(-SUM[\(-1\) + m]\) + SUM[m] == \(\((1 + m)\)\ \((1 - x)\)\^\(\(-1\) + m\)\ \((\(-1\) + x)\)\ x\^m\ Binomial[3 + 2\ \((\(-1\) + m)\), m]\)\/\(2\ \((1 + 2\ \((\(-1\) + m)\))\)\ \((3 + 2\ \((\(-1\) + m)\))\)\)} \)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(\(-%[\([1, 2]\)]\)\)], "Input"], Cell[BoxData[ \(\(-\(\(\((1 + m)\)\ \((1 - x)\)\^\(\(-1\) + m\)\ \((\(-1\) + x)\)\ x\^m\ Binomial[3 + 2\ \((\(-1\) + m)\), m]\)\/\(2\ \((1 + 2\ \((\(-1\) + m)\))\)\ \((3 + 2\ \((\(-1\) + m)\))\)\)\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% // FS\)], "Input"], Cell[BoxData[ \(\(\((1 - x)\)\^m\ x\^m\ Binomial[2\ m, m]\)\/\(2\ \((\(-1\) + 2\ m)\)\)\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["E 3258", "Subsection", Evaluatable->False], Cell["\<\ First we transform the sum into a hypergeometric one by combining every two \ consecutive terms, and divide through by the right-hand side:\ \>", "Text"], Cell[BoxData[ \(\(Clear[F]; \)\)], "Input"], Cell[BoxData[ \(F[n_, j_, j2_] := Binomial[n, j] 2^\((n - j)\) Binomial[j, j2]\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(FS[\((F[n, 2 j, j] + F[n, 2 j + 1, j])\)/Binomial[2 n + 1, n]]\)], "Input"], Cell[BoxData[ \(\(2\^\(\(-1\) - 2\ j + n\)\ \((1 + n)\)\ \((2 + n)\)\ Binomial[2\ j, j]\ Binomial[n, 2\ j]\)\/\(\((1 + j)\)\ \((1 + 2\ n)\)\ Binomial[2\ n, n]\)\)], "Output"] }, Closed]], Cell["Now the WZ method provides the proof:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(WZ[%, n, j]\)], "Input"], Cell[BoxData[ \(\(4\ j\ \((1 + j)\)\)\/\(\((\(-1\) + 2\ j - n)\)\ \((3 + 2\ n)\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Sum[%%, {j, 0, n}] /. n -> 0\)], "Input"], Cell[BoxData[ \(1\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["E 3335", "Subsection"], Cell["Hyper finds that x[n] = n+1 is a solution:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Hyper[x[n + 2] == x[n + 1] + x[n]/\((n + 1)\), x[n], Solutions -> All] \)], "Input"], Cell[BoxData[ \({\(2 + n\)\/\(1 + n\)}\)], "Output"] }, Closed]], Cell["Now we can find the general solution by reduction of order:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(x[n + 2] == x[n + 1] + x[n]/\((n + 1)\)\ /. \ x[n_] -> \((n + 1)\) y[n]\)], "Input"], Cell[BoxData[ \(\((3 + n)\)\ y[2 + n] == y[n] + \((2 + n)\)\ y[1 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(%[\([1]\)] - %[\([2]\)]\)], "Input"], Cell[BoxData[ \(\(-y[n]\) - \((2 + n)\)\ y[1 + n] + \((3 + n)\)\ y[2 + n]\)], "Output"] }, Closed]], Cell["\<\ This should be a first-order recurrence for d[n] = y[n+1] - y[n]:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(% //. y[n + k_] -> d[n + k - 1] + y[n + k - 1]\)], "Input"], Cell[BoxData[ \(\(-y[n]\) - \((2 + n)\)\ \((d[n] + y[n])\) + \((3 + n)\)\ \((d[n] + d[1 + n] + y[n])\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% // Expand\)], "Input"], Cell[BoxData[ \(d[n] + 3\ d[1 + n] + n\ d[1 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% /. n -> n - 1\)], "Input"], Cell[BoxData[ \(d[\(-1\) + n] + 3\ d[n] + \((\(-1\) + n)\)\ d[n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[% == 0, d[n]]\)], "Input"], Cell[BoxData[ \({{d[n] \[Rule] \(-\(d[\(-1\) + n]\/\(2 + n\)\)\)}}\)], "Output"] }, Closed]], Cell[TextData[{ "It follows that ", Cell[BoxData[ \(TraditionalForm\`d[n] = \(C\ \((\(-1\))\)\^n\)\/\(\((n + 2)\)!\)\)]], ", hence " }], "Text"], Cell[BoxData[ \(TraditionalForm \`\(y[n] = \(D - C\ \(\[Sum]\+\(k = 0\)\%n\((\(-1\))\)\^k\/\(\((k + 1)\)!\)\) = \ D + C\ \(\[Sum]\+\(k = 1\)\%\(n + 1\)\((\(-1\))\)\^k\/\(k!\)\)\), \)\)], "Text"], Cell["and the general solution of this recurrence is ", "Text"], Cell[BoxData[ \(TextForm \`x[n] = \ \((n + 1)\) \(\((D + C\ \(\[Sum]\+\(k = 1\)\%\(n + 1\)\((\(-1\))\)\^k\/\(k!\)\)) \) . \)\)], "Text", FontSlant->"Italic"], Cell["From the initial conditions we obtain", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ \((n + 1)\) \((D + C\ Sum[\((\(-1\))\)^k/\(k!\), {k, 1, n + 1}])\), {n, 0, 1}]\)], "Input"], Cell[BoxData[ \({\(-C\) + D, 2\ \((\(-\(C\/2\)\) + D)\)}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[Thread[% == {a, b}], {C, D}]\)], "Input"], Cell[BoxData[ \({{C \[Rule] \(-2\)\ a + b, D \[Rule] \(-a\) + b}}\)], "Output"] }, Closed]], Cell[BoxData[ \(TextForm \`x[n] = \ \((n + 1)\) \(\((a + \((b - 2 a)\)\ \(\[Sum]\+\(k = 0\)\%\(n + 1\)\((\(-1\))\)\^k\/\(k!\)\))\) . \)\)], "Text", FontSlant->"Italic"] }, Closed]], Cell[CellGroupData[{ Cell["E 3352", "Subsection", Evaluatable->False], Cell[CellGroupData[{ Cell[BoxData[ \(GosperSum[1\/\(\(n!\)\ \((n\^4 + n\^2 + 1)\)\) - 1\/\(2\ \(n!\)\), n] \)], "Input", PageWidth->Infinity], Cell[BoxData[ \(\(-\(\(n\^2\ \((1 + n + n\^2)\)\ \((\(-\(1\/\(2\ \(n!\)\)\)\) + 1\/\(\((1 + n\^2 + n\^4)\)\ \(n!\)\))\)\)\/\(\(-1\) + n\^2 + n\^4\)\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Simplify[%]\)], "Input", PageWidth->Infinity], Cell[BoxData[ \(n\^2\/\(2\ \((1 - n + n\^2)\)\ \(n!\)\)\)], "Output"] }, Closed]], Cell[TextData[ "This vanishes both at n = \[Infinity] and at n = 0, but to find the limit at \ n = \[Infinity] we need to load the standard package Calculus\\Limit.m."], "Text"], Cell[BoxData[ \(<< calculus\\limit.m\)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(Limit[%%, n -> Infinity] - %% /. n -> 0\)], "Input"], Cell[BoxData[ \(0\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["E 3376", "Subsection", Evaluatable->False], Cell["\<\ First we use Zeilberger's algorithm to find a recurrence w.r.t. i.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[i + j, j]\^2\ Binomial[4\ N - 2\ i - 2\ j, 2\ N - 2\ j], { j, 0, N}, \n\ti, 3]\)], "Input", PageWidth->Infinity], Cell[BoxData[ \("If `N' is a natural number, then:"\)], "Print"], Cell[BoxData[ \({\(-\((1 + i)\)\)\ \((1 + 2\ i - 2\ N)\)\ \((i - N)\)\ SUM[i] + \((18 + 32\ i + 22\ i\^2 + 6\ i\^3 + 11\ N - 4\ i\ N - 8\ i\^2\ N + 30\ N\^2 + 20\ i\ N\^2)\)\ SUM[1 + i] - \((2 + i)\)\ \((27 + 23\ i + 6\ i\^2 + 9\ N - 4\ i\ N + 18\ N\^2)\)\ SUM[2 + i] + 2\ \((2 + i)\)\ \((3 + i)\)\^2\ SUM[3 + i] == 0}\)], "Output"] }, Closed]], Cell["\<\ Following Peter Paule, we sum this recurrence w.r.t. i from -3 to N.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(Sum[#, {i, \(-3\), N}]&\)\ /@\ %[\([1, 1]\)]\)], "Input"], Cell[BoxData[ \(\[Sum]\+\(i = \(-3\)\)\%N\(-\((1 + i)\)\)\ \((1 + 2\ i - 2\ N)\)\ \((i - N)\)\ SUM[i] + \[Sum]\+\(i = \(-3\)\)\%N \((18 + 32\ i + 22\ i\^2 + 6\ i\^3 + 11\ N - 4\ i\ N - 8\ i\^2\ N + 30\ N\^2 + 20\ i\ N\^2)\)\ SUM[1 + i] + \[Sum]\+\(i = \(-3\)\)\%N\(-\((2 + i)\)\)\ \((27 + 23\ i + 6\ i\^2 + 9\ N - 4\ i\ N + 18\ N\^2)\)\ SUM[2 + i] + \[Sum]\+\(i = \(-3\)\)\%N 2\ \((2 + i)\)\ \((3 + i)\)\^2\ SUM[3 + i]\)], "Output"] }, Closed]], Cell["\<\ Now we shift summation indices in such a way that SUM appears with argument i \ everywhere.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(% /. Sum[p : a_\ SUM[i + k_], {i, low_, N}] :> Sum[Evaluate[Factor[p /. i -> i - k]], Evaluate[{i, low + k, N + k}]] \)], "Input"], Cell[BoxData[ \(\[Sum]\+\(i = 0\)\%\(3 + N\)2\ \((\(-1\) + i)\)\ i\^2\ SUM[i] + \[Sum]\+\(i = \(-3\)\)\%N\(-\((1 + i)\)\)\ \((1 + 2\ i - 2\ N)\)\ \((i - N)\)\ SUM[i] + \[Sum]\+\(i = \(-1\)\)\%\(2 + N\)\(-i\)\ \((5 - i + 6\ i\^2 + 17\ N - 4\ i\ N + 18\ N\^2)\)\ SUM[i] + \[Sum]\+\(i = \(-2\)\)\%\(1 + N\)\(( 2 + 6\ i + 4\ i\^2 + 6\ i\^3 + 7\ N + 12\ i\ N - 8\ i\^2\ N + 10\ N\^2 + 20\ i\ N\^2)\)\ SUM[i]\)], "Output"] }, Closed]], Cell["\<\ Next each sum is written with the limits 0 and N, plus some extra terms.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(% /. Sum[a_, {i, low_, N + k_. }] :> Sum[a, {i, low, \(-1\)}] + Sum[a, {i, 0, N}] + Sum[a, {i, N + 1, N + k}]\)], "Input"], Cell[BoxData[ \(\[Sum]\+\(i = 0\)\%N 2\ \((\(-1\) + i)\)\ i\^2\ SUM[i] + \[Sum]\+\(i = 0\)\%N\(-\((1 + i)\)\)\ \((1 + 2\ i - 2\ N)\)\ \((i - N)\)\ SUM[i] + \[Sum]\+\(i = 0\)\%N\(-i\)\ \((5 - i + 6\ i\^2 + 17\ N - 4\ i\ N + 18\ N\^2)\)\ SUM[i] + \[Sum]\+\(i = 0\)\%N \((2 + 6\ i + 4\ i\^2 + 6\ i\^3 + 7\ N + 12\ i\ N - 8\ i\^2\ N + 10\ N\^2 + 20\ i\ N\^2)\)\ SUM[i] + 2\ \((\(-5\) - 2\ N)\)\ \((\(-3\) - N)\)\ SUM[\(-3\)] + \((\(-3\) - 2\ N)\)\ \((\(-2\) - N)\)\ SUM[\(-2\)] + \((\(-42\) - 49\ N - 30\ N\^2)\)\ SUM[\(-2\)] + \((\(-6\) - 13\ N - 10\ N\^2)\)\ SUM[\(-1\)] + \((12 + 21\ N + 18\ N\^2)\)\ SUM[\(-1\)] + 2\ N\ \((1 + N)\)\^2\ SUM[1 + N] - \((1 + N)\)\ \((4 + 16\ N + 18\ N\^2 - 4\ N\ \((1 + N)\) + 6\ \((1 + N)\)\^2)\)\ SUM[1 + N] + \((2 + 7\ N + 10\ N\^2 + 6\ \((1 + N)\) + 12\ N\ \((1 + N)\) + 20\ N\^2\ \((1 + N)\) + 4\ \((1 + N)\)\^2 - 8\ N\ \((1 + N)\)\^2 + 6\ \((1 + N)\)\^3)\)\ SUM[1 + N] + 2\ \((1 + N)\)\ \((2 + N)\)\^2\ SUM[2 + N] - \((2 + N)\)\ \((3 + 16\ N + 18\ N\^2 - 4\ N\ \((2 + N)\) + 6\ \((2 + N)\)\^2)\)\ SUM[2 + N] + 2\ \((2 + N)\)\ \((3 + N)\)\^2\ SUM[3 + N]\)], "Output"] }, Closed]], Cell[TextData[{ "Sums with identical limits are combined into a single one. Here Paule's \ idea shows its power: the summand in the only remaining sum is of the form c \ SUM[i] where c is independent of i, so this sum equals c times the original \ double sum (which we shall call x). The entire expression equals zero, so we \ have a linear equation satisfied by x. It remains to solve this equation \ (which is straightforward by pencil-and-paper but requires some coaxing to \ get ", StyleBox["Mathematica", FontSlant->"Italic"], " do it)." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(% //. a_ + Sum[u_, {i, 0, N}] + Sum[v_, {i, 0, N}] :> a + Sum[Evaluate[Factor[u + v]], {i, 0, N}]\)], "Input"], Cell[BoxData[ \(\[Sum]\+\(i = 0\)\%N 2\ \((1 + 2\ N)\)\^2\ SUM[i] + 2\ \((\(-5\) - 2\ N)\)\ \((\(-3\) - N)\)\ SUM[\(-3\)] + \((\(-3\) - 2\ N)\)\ \((\(-2\) - N)\)\ SUM[\(-2\)] + \((\(-42\) - 49\ N - 30\ N\^2)\)\ SUM[\(-2\)] + \((\(-6\) - 13\ N - 10\ N\^2)\)\ SUM[\(-1\)] + \((12 + 21\ N + 18\ N\^2)\)\ SUM[\(-1\)] + 2\ N\ \((1 + N)\)\^2\ SUM[1 + N] - \((1 + N)\)\ \((4 + 16\ N + 18\ N\^2 - 4\ N\ \((1 + N)\) + 6\ \((1 + N)\)\^2)\)\ SUM[1 + N] + \((2 + 7\ N + 10\ N\^2 + 6\ \((1 + N)\) + 12\ N\ \((1 + N)\) + 20\ N\^2\ \((1 + N)\) + 4\ \((1 + N)\)\^2 - 8\ N\ \((1 + N)\)\^2 + 6\ \((1 + N)\)\^3)\)\ SUM[1 + N] + 2\ \((1 + N)\)\ \((2 + N)\)\^2\ SUM[2 + N] - \((2 + N)\)\ \((3 + 16\ N + 18\ N\^2 - 4\ N\ \((2 + N)\) + 6\ \((2 + N)\)\^2)\)\ SUM[2 + N] + 2\ \((2 + N)\)\ \((3 + N)\)\^2\ SUM[3 + N]\)], "Output"] }, Closed]], Cell["The extra terms are combined w.r.t. the argument of SUM.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(% //. a_ + b_\ SUM[x_] + c_\ SUM[x_] :> a + Factor[b + c] SUM[x]\)], "Input"], Cell[BoxData[ \(\[Sum]\+\(i = 0\)\%N 2\ \((1 + 2\ N)\)\^2\ SUM[i] + 2\ \((\(-5\) - 2\ N)\)\ \((\(-3\) - N)\)\ SUM[\(-3\)] - 2\ \((18 + 21\ N + 14\ N\^2)\)\ SUM[\(-2\)] + 2\ \((3 + 4\ N + 4\ N\^2)\)\ SUM[\(-1\)] + \((8 + 11\ N + 8\ N\^2)\)\ SUM[1 + N] - \((2 + N)\)\ \((23 + 26\ N + 18\ N\^2)\)\ SUM[2 + N] + 2\ \((2 + N)\)\ \((3 + N)\)\^2\ SUM[3 + N]\)], "Output"] }, Closed]], Cell[TextData[{ "These SUMs contain a fixed number of terms each, so they can be computed \ directly. However, ", StyleBox["Mathematica", FontSlant->"Italic"], " has the unfortunate habit of simplifying certain binomial coefficients to \ zero, e.g.:" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Binomial[j - 7, j]\)], "Input"], Cell[BoxData[ \(0\)], "Output"] }, Closed]], Cell["\<\ which gives wrong results when j<7. This is what happens here if we use the \ built-in Binomial function to evaluate these SUMs. Therefore we use an inert \ head called binom which we replace by the binomial coefficient (defined by \ the Pochhammer symbol to avoid the unwanted effects of Binomial) only after \ solving the equation for x.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(%% /. SUM[i_?Negative] :> Sum[binom[i + j, j]^2 binom[4 N - 2 i - 2 j, 2 N - 2 j], {j, 0, \(-i\) - 1}]\)], "Input"], Cell[BoxData[ \(2\ \((3 + 4\ N + 4\ N\^2)\)\ binom[\(-1\), 0]\^2\ binom[2 + 4\ N, 2\ N] - 2\ \((18 + 21\ N + 14\ N\^2)\)\ \((binom[\(-1\), 1]\^2\ binom[2 + 4\ N, \(-2\) + 2\ N] + binom[\(-2\), 0]\^2\ binom[4 + 4\ N, 2\ N])\) + 2\ \((\(-5\) - 2\ N)\)\ \((\(-3\) - N)\)\ \((binom[\(-1\), 2]\^2\ binom[2 + 4\ N, \(-4\) + 2\ N] + binom[\(-2\), 1]\^2\ binom[4 + 4\ N, \(-2\) + 2\ N] + binom[\(-3\), 0]\^2\ binom[6 + 4\ N, 2\ N])\) + \[Sum]\+\(i = 0\)\%N 2\ \((1 + 2\ N)\)\^2\ SUM[i] + \((8 + 11\ N + 8\ N\^2)\)\ SUM[1 + N] - \((2 + N)\)\ \((23 + 26\ N + 18\ N\^2)\)\ SUM[2 + N] + 2\ \((2 + N)\)\ \((3 + N)\)\^2\ SUM[3 + N]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% /. SUM[N + i_?Positive] :> Sum[binom[N + i + j, j]^2 binom[2 N - 2 i - 2 j, 2 N - 2 j], { j, N - i + 1, N}]\)], "Input"], Cell[BoxData[ \(\((8 + 11\ N + 8\ N\^2)\)\ binom[\(-2\), 0]\ binom[1 + 2\ N, N]\^2 + 2\ \((2 + N)\)\ \((3 + N)\)\^2\ \((binom[\(-6\), 0]\ binom[3 + 2\ N, N]\^2 + binom[1 + 2\ N, \(-2\) + N]\^2\ binom[\(-6\) - 2\ \((\(-2\) + N)\) + 2\ N, \(-2\)\ \((\(-2\) + N)\) + 2\ N] + binom[2 + 2\ N, \(-1\) + N]\^2\ binom[\(-6\) - 2\ \((\(-1\) + N)\) + 2\ N, \(-2\)\ \((\(-1\) + N)\) + 2\ N])\) - \((2 + N)\)\ \((23 + 26\ N + 18\ N\^2)\)\ \((binom[\(-4\), 0]\ binom[2 + 2\ N, N]\^2 + binom[1 + 2\ N, \(-1\) + N]\^2\ binom[\(-4\) - 2\ \((\(-1\) + N)\) + 2\ N, \(-2\)\ \((\(-1\) + N)\) + 2\ N])\) + 2\ \((3 + 4\ N + 4\ N\^2)\)\ binom[\(-1\), 0]\^2\ binom[2 + 4\ N, 2\ N] - 2\ \((18 + 21\ N + 14\ N\^2)\)\ \((binom[\(-1\), 1]\^2\ binom[2 + 4\ N, \(-2\) + 2\ N] + binom[\(-2\), 0]\^2\ binom[4 + 4\ N, 2\ N])\) + 2\ \((\(-5\) - 2\ N)\)\ \((\(-3\) - N)\)\ \((binom[\(-1\), 2]\^2\ binom[2 + 4\ N, \(-4\) + 2\ N] + binom[\(-2\), 1]\^2\ binom[4 + 4\ N, \(-2\) + 2\ N] + binom[\(-3\), 0]\^2\ binom[6 + 4\ N, 2\ N])\) + \[Sum]\+\(i = 0\)\%N 2\ \((1 + 2\ N)\)\^2\ SUM[i]\)], "Output"] }, Closed]], Cell["Now we call the unknown sum x and solve for it.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(% /. Sum[a_\ SUM[i], {i, 0, N}] /; FreeQ[a, i] -> a\ x\)], "Input"], Cell[BoxData[ \(2\ \((1 + 2\ N)\)\^2\ x + \((8 + 11\ N + 8\ N\^2)\)\ binom[\(-2\), 0]\ binom[1 + 2\ N, N]\^2 + 2\ \((2 + N)\)\ \((3 + N)\)\^2\ \((binom[\(-6\), 0]\ binom[3 + 2\ N, N]\^2 + binom[1 + 2\ N, \(-2\) + N]\^2\ binom[\(-6\) - 2\ \((\(-2\) + N)\) + 2\ N, \(-2\)\ \((\(-2\) + N)\) + 2\ N] + binom[2 + 2\ N, \(-1\) + N]\^2\ binom[\(-6\) - 2\ \((\(-1\) + N)\) + 2\ N, \(-2\)\ \((\(-1\) + N)\) + 2\ N])\) - \((2 + N)\)\ \((23 + 26\ N + 18\ N\^2)\)\ \((binom[\(-4\), 0]\ binom[2 + 2\ N, N]\^2 + binom[1 + 2\ N, \(-1\) + N]\^2\ binom[\(-4\) - 2\ \((\(-1\) + N)\) + 2\ N, \(-2\)\ \((\(-1\) + N)\) + 2\ N])\) + 2\ \((3 + 4\ N + 4\ N\^2)\)\ binom[\(-1\), 0]\^2\ binom[2 + 4\ N, 2\ N] - 2\ \((18 + 21\ N + 14\ N\^2)\)\ \((binom[\(-1\), 1]\^2\ binom[2 + 4\ N, \(-2\) + 2\ N] + binom[\(-2\), 0]\^2\ binom[4 + 4\ N, 2\ N])\) + 2\ \((\(-5\) - 2\ N)\)\ \((\(-3\) - N)\)\ \((binom[\(-1\), 2]\^2\ binom[2 + 4\ N, \(-4\) + 2\ N] + binom[\(-2\), 1]\^2\ binom[4 + 4\ N, \(-2\) + 2\ N] + binom[\(-3\), 0]\^2\ binom[6 + 4\ N, 2\ N])\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[% == 0, x]\)], "Input"], Cell[BoxData[ \({{x \[Rule] \(-\(1\/\(2\ \((1 + 2\ N)\)\^2\)\(( \((8 + 11\ N + 8\ N\^2)\)\ binom[\(-2\), 0]\ binom[1 + 2\ N, N]\^2 + 2\ \((2 + N)\)\ \((3 + N)\)\^2\ \((binom[\(-6\), 0]\ binom[3 + 2\ N, N]\^2 + binom[1 + 2\ N, \(-2\) + N]\^2\ binom[\(-6\) - 2\ \((\(-2\) + N)\) + 2\ N, \(-2\)\ \((\(-2\) + N)\) + 2\ N] + binom[2 + 2\ N, \(-1\) + N]\^2\ binom[\(-6\) - 2\ \((\(-1\) + N)\) + 2\ N, \(-2\)\ \((\(-1\) + N)\) + 2\ N])\) - \((2 + N)\)\ \((23 + 26\ N + 18\ N\^2)\)\ \((binom[\(-4\), 0]\ binom[2 + 2\ N, N]\^2 + binom[1 + 2\ N, \(-1\) + N]\^2\ binom[\(-4\) - 2\ \((\(-1\) + N)\) + 2\ N, \(-2\)\ \((\(-1\) + N)\) + 2\ N])\) + 2\ \((3 + 4\ N + 4\ N\^2)\)\ binom[\(-1\), 0]\^2\ binom[2 + 4\ N, 2\ N] - 2\ \((18 + 21\ N + 14\ N\^2)\)\ \((binom[\(-1\), 1]\^2\ binom[2 + 4\ N, \(-2\) + 2\ N] + binom[\(-2\), 0]\^2\ binom[4 + 4\ N, 2\ N])\) + 2\ \((\(-5\) - 2\ N)\)\ \((\(-3\) - N)\)\ \((binom[\(-1\), 2]\^2\ binom[2 + 4\ N, \(-4\) + 2\ N] + binom[\(-2\), 1]\^2\ binom[4 + 4\ N, \(-2\) + 2\ N] + binom[\(-3\), 0]\^2\ binom[6 + 4\ N, 2\ N])\))\)\)\)}} \)], "Output"] }, Closed]], Cell["\<\ Finally we replace binoms by the true binomials, and FactorialSimplify to get \ the desired evaluation.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\((\(x /. %[\([1]\)]\) /. binom[n_, k_] :> Pochhammer[n - k + 1, k]/\(k!\))\) // FS\)], "Input"], Cell[BoxData[ \(\((1 + 2\ N)\)\ Binomial[2\ N, N]\^2\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["E 3439", "Subsection", Evaluatable->False], Cell["The two sums can be combined into a single one", "Text"], Cell[CellGroupData[{ Cell["\<\ FS[(Binomial[M-a-1,a]Binomial[N+a, 2a+1]+ Binomial[M-a,a]Binomial[N+a,2a])]\ \>", "Input", PageWidth->Infinity], Cell[BoxData[ \(\(-\(\(( \((\(-a\) + M + a\ M - 2\ a\ N + M\ N)\)\ Binomial[\(-a\) + M, a]\ Binomial[a + N, 2\ a])\)/ \((\((1 + 2\ a)\)\ \((a - M)\))\)\)\)\)], "Output"] }, Closed]], Cell["\<\ for which Zeilberger's algorithm finds an inhomogeneous recurrence of order \ 1:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[%, {a, 0, M - 1}, N, 1]\)], "Input", PageWidth->Infinity], Cell[BoxData[ \("If `-1 + M' is a natural number, then:"\)], "Print"], Cell[BoxData[ \({\((1 + M + N)\)\ SUM[N] + \((\(-1\) - N)\)\ SUM[1 + N] == \(-\(1\/\(\(-1\) + 2\ M\)\(( \((\(-2\) + M)\)\ \((\(-1\) + M)\)\ \((\(-2\) + M - N)\)\ Binomial[1, \(-1\) + M]\ Binomial[M + N, 2\ \((\(-1\) + M)\)]) \)\)\)}\)], "Output"] }, Closed]], Cell["The right-hand side actually vanishes.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(%[\([1, 1]\)] == FS[%[\([1, 2]\)]]\)], "Input"], Cell[BoxData[ \(\((1 + M + N)\)\ SUM[N] + \((\(-1\) - N)\)\ SUM[1 + N] == 0\)], "Output"] }, Closed]], Cell["This recurrence is satisfied by the left-hand side,", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(% /. SUM[N_] -> Binomial[M + N, M]\)], "Input"], Cell[BoxData[ \(\((1 + M + N)\)\ Binomial[M + N, M] + \((\(-1\) - N)\)\ Binomial[1 + M + N, M] == 0\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(FS/@%\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Closed]], Cell["\<\ so checking the identity for a single value of N finishes the proof.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Sum[ Binomial[M - a - 1, a] Binomial[N + a, \ 2 a + 1], {a, 0, \((M - 1)\)/2}] + \ \n\ \ \ \ \ \ Sum[Binomial[M - a, a] Binomial[N + a, 2 a], {a, 0, M/2}] /. N -> 0\)], "Input"], Cell[BoxData[ \(1\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Binomial[M + N, M] /. N -> 0\)], "Input"], Cell[BoxData[ \(1\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["10206", "Subsection", Evaluatable->False], Cell["\<\ First we find a recurrence w.r.t. k satisfied by the left-hand side.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[r, k - r] Binomial[m, r], {r, 0, Infinity}, k, 1]\)], "Input"], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[r, k - r] Binomial[m, r], {r, 0, Infinity}, k, 2]\)], "Input"], Cell[BoxData[ \({\((\(-k\) + 2\ m)\)\ SUM[k] + \((\(-1\) - k + m)\)\ SUM[1 + k] + \((\(-2\) - k)\)\ SUM[2 + k] == \(-\(1\/2\)\)\ k\ \((1 + k)\)\ \((2 + k)\)\ Binomial[2, 2 + k]}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(%[\([1, 1]\)] == FS[%[\([1, 2]\)]]\)], "Input"], Cell[BoxData[ \(\((\(-k\) + 2\ m)\)\ SUM[k] + \((\(-1\) - k + m)\)\ SUM[1 + k] + \((\(-2\) - k)\)\ SUM[2 + k] == 0\)], "Output"] }, Closed]], Cell["\<\ Next we rewrite the right-hand sum by combining every two consecutive terms\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(FS[Binomial[j, k - 2 j] Binomial[m - k + 3 j, 2 j] + Binomial[j, k - 2 j - 1] Binomial[m - k + 3 j + 1, 2 j + 1]]\)], "Input"], Cell[BoxData[ \(\((\((1 + 3\ j + 3\ j\ k - k\^2 - 2\ j\ m + k\ m)\)\ Binomial[j, \(-2\)\ j + k]\ Binomial[3\ j - k + m, 2\ j])\)/ \((\((1 + 2\ j)\)\ \((1 + 3\ j - k)\))\)\)], "Output"] }, Closed]], Cell["and find the recurrence w.r.t. k satisfied by it:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[%, {j, 0, Infinity}, k, 2]\)], "Input"], Cell[BoxData[ \({\((\(-k\) + 2\ m)\)\ SUM[k] + \((\(-1\) - k + m)\)\ SUM[1 + k] + \((\(-2\) - k)\)\ SUM[2 + k] == \(-k\)\ \((1 + k)\)\ \((2 + k)\)\ Binomial[2, 2 + k]}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(%[[1, 1]] == FS[%[[1, 2]]]\)], "Input"], Cell[BoxData[ \(\((\(-k\) + 2\ m)\)\ SUM[k] + \((\(-1\) - k + m)\)\ SUM[1 + k] + \((\(-2\) - k)\)\ SUM[2 + k] == 0\)], "Output"] }, Closed]], Cell["\<\ This is the same recurrence as above, hence it suffices to check that the two \ sums agree for k = 0, 1.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[Binomial[r, k - r] Binomial[m, r], {k, 0, 1}]\)], "Input"], Cell[BoxData[ \({Binomial[m, r]\ Binomial[r, \(-r\)], Binomial[m, r]\ Binomial[r, 1 - r]}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(\(Sum[#, {r, 0, 1}]&\)\ /@\ %\)], "Input"], Cell[BoxData[ \({1, m}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ FS[Binomial[j, k - 2 j] Binomial[m - k + 3 j, 2 j] + Binomial[j, k - 2 j - 1] Binomial[m - k + 3 j + 1, 2 j + 1]], { k, 0, 1}]\)], "Input"], Cell[BoxData[ \({\(- \(\(\((\(-1\) - 3\ j + 2\ j\ m)\)\ Binomial[j, \(-2\)\ j]\ Binomial[3\ j + m, 2\ j]\)\/\(\((1 + 2\ j)\)\ \((1 + 3\ j)\)\)\)\), \(\((j + m)\)\ \((\(-6\)\ j - m + 2\ j\ m)\)\ Binomial[j, \(-2\)\ j]\ Binomial[3\ j + m, 2\ j]\)\/\(\((\(-1\) + 2\ j)\)\ \((1 + 2\ j)\)\ \((3\ j + m)\)\)}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(\(Sum[#, {j, 0, 1}]&\)\ /@\ %\)], "Input"], Cell[BoxData[ \({1, m}\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["10223", "Subsection"], Cell["\<\ We split the sum into two and find a recurrence w.r.t. n satisfied by each of \ them:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[k - 1, n - 1] p^n \((1 - p)\)^\((k - n)\), {k, n\ , 2 n - 1}, n, 1]\)], "Input"], Cell[BoxData[ \("If `-1 + n' is a natural number, then:"\)], "Print"], Cell[BoxData[ \({\(-SUM[n]\) + SUM[1 + n] == \((1 - p)\)\^n\ p\^n\ \((\(-1\) + 2\ p)\)\ Binomial[\(-1\) + 2\ n, \(-1\) + n]}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[k - 1, n - 1] \((1 - p)\)^n\ p^\((k - n)\), {k, n\ , 2 n - 1}, n, 1]\)], "Input"], Cell[BoxData[ \("If `-1 + n' is a natural number, then:"\)], "Print"], Cell[BoxData[ \({\(-SUM[n]\) + SUM[1 + n] == \(-\((1 - p)\)\^n\)\ p\^n\ \((\(-1\) + 2\ p)\)\ Binomial[\(-1\) + 2\ n, \(-1\) + n]}\)], "Output"] }, Closed]], Cell["\<\ Adding up these two recurrences we see that our sum is independent of n.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Thread[%[\([1]\)] + %%[\([1]\)], Equal]\)], "Input"], Cell[BoxData[ \(\(-2\)\ SUM[n] + 2\ SUM[1 + n] == 0\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[%, SUM[n + 1]]\)], "Input"], Cell[BoxData[ \({{SUM[1 + n] \[Rule] SUM[n]}}\)], "Output"] }, Closed]], Cell["Therefore it suffices to evaluate it at n=1.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Binomial[k - 1, n - 1] p^n \((1 - p)\)^\((k - n)\) + Binomial[k - 1, n - 1] \((1 - p)\)^n\ p^\((k - n)\) /. n -> 1\)], "Input"], Cell[BoxData[ \(\((1 - p)\)\^\(\(-1\) + k\)\ p + \((1 - p)\)\ p\^\(\(-1\) + k\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Sum[%, {k, 1, 1}]\)], "Input"], Cell[BoxData[ \(1\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["10229", "Subsection", Evaluatable->False], Cell["Gosper's algorithm does the job.", "Text"], Cell[CellGroupData[{ Cell["GosperSum[Binomial[1/2,m-j+1]Binomial[1/2,m+j],{j,1,p}]", "Input", PageWidth->Infinity], Cell[BoxData[ \(\(\((1 + m - p)\)\ p\ \((\(-1\) + 2\ m + 2\ p)\)\ Binomial[1\/2, 1 + m - p]\ Binomial[1\/2, m + p]\)\/\(m\ \((1 + 2\ m)\)\)\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["10332", "Subsection", Evaluatable->False], Cell["\<\ If we divide the identity by the left-hand side, the WZ method (w.r.t. j and \ n, say) succeed in finding a proof certificate.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(WZ[Binomial[n, j] Binomial[n - j, j + k] 2^\((n - k - 2 j)\)/Binomial[2 n, n + k], n, j]\)], "Input"], Cell[BoxData[ \(\(4\ j\ \((j + k)\)\)\/\(\((\(-1\) + 2\ j + k - n)\)\ \((1 + 2\ n)\)\)\)], "Output"] }, Closed]], Cell[TextData[{ "It remains to check the identity for a single value of n. Note that 0\ \[LessEqual]k\[LessEqual]n, so ", "n=0", " forces k=0 as well." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Binomial[n, j] Binomial[n - j, j + k] 2^\((n - k - 2 j)\) /. {n -> 0, k -> 0, j -> 0}\)], "Input"], Cell[BoxData[ \(1\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Binomial[2 n, n + k] /. {n -> 0, k -> 0}\)], "Input"], Cell[BoxData[ \(1\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["10357", "Subsection"], Cell[TextData[{ "It is easy to see that ", Cell[BoxData[ \(TraditionalForm\`a(m, n) = \[Sum]\+\(k = 0\)\%m t(m, n, k)\)]], " where" }], "Text"], Cell[BoxData[ \(t[m_, n_, k_] := \((\(-1\))\)^k\ Binomial[m, k] Binomial[n, k]\)], "Input"], Cell[TextData[{ "Using Zeilberger's algorithm we find a recurrence w.r.t. j satisfied by ", Cell[BoxData[ \(TraditionalForm\`\((\(-1\))\)\^j\ \(a(2\ j, 2\ j + 2)\)\)]], ":" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\((\(-1\))\)^j\ t[2 j, 2 j + 2, k]\)], "Input"], Cell[BoxData[ \(\((\(-1\))\)\^\(j + k\)\ Binomial[2\ j, k]\ Binomial[2 + 2\ j, k]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[%, {k, 0, Infinity}, j, 1]\)], "Input"], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[%%, {k, 0, Infinity}, j, 2]\)], "Input"], Cell[BoxData[ \({\(-16\)\ \((1 + j)\)\ \((1 + 2\ j)\)\ \((9 + 4\ j)\)\ SUM[j] + 2\ \((7 + 4\ j)\)\ \((21 + 28\ j + 8\ j\^2)\)\ SUM[1 + j] - \((3 + j)\)\ \((5 + 2\ j)\)\ \((5 + 4\ j)\)\ SUM[2 + j] == 0}\)], "Output"] }, Closed]], Cell["\<\ This recurrence is also satisfied by the j-th Catalan number:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(%[\([1, 1]\)] /. SUM[j_] -> Binomial[2 j, j]/\((j + 1)\)\)], "Input"], Cell[BoxData[ \(\(-16\)\ \((1 + 2\ j)\)\ \((9 + 4\ j)\)\ Binomial[2\ j, j] + \(2\ \((7 + 4\ j)\)\ \((21 + 28\ j + 8\ j\^2)\)\ Binomial[2\ \((1 + j)\), 1 + j]\)\/\(2 + j\) - \((5 + 2\ j)\)\ \((5 + 4\ j)\)\ Binomial[2\ \((2 + j)\), 2 + j]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% // FS\)], "Input"], Cell[BoxData[ \(0\)], "Output"] }, Closed]], Cell["\<\ As the values for j=0 and j=1 agree, the identity has been proved:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[\((\(-1\))\)^j\ a[2 j, 2 j + 2, k], {j, 0, 1}, {k, 0, 2 j}] \)], "Input"], Cell[BoxData[ \({{1}, {\(-1\), 8, \(-6\)}}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(\(Plus\ @@\ #&\)\ /@\ %\)], "Input"], Cell[BoxData[ \({1, 1}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Table[Binomial[2 j, j]/\((j + 1)\), {j, 0, 1}]\)], "Input"], Cell[BoxData[ \({1, 1}\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["10363", "Subsection", Evaluatable->False], Cell["\<\ Zeilberger's algorithm finds a first-order recurrence w.r.t. k satisfied by \ the inner sum:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[k + j, k]\ Binomial[2\ n - m - 2\ k - j - 3, 2\ \((n - m - k - 1)\)], \n \t{j, 0, m - 1}, k, 1]\)], "Input", PageWidth->Infinity], Cell[BoxData[ \("If `-1 + m' is a natural number and none of \n{-1 + k + m, -2 (2 + k + \ m - n)}\nis a negative integer, then:"\)], "Print"], Cell[BoxData[ \({\((1 + k + 2\ m - 2\ n)\)\ SUM[k] + \((\(-2\) - k - m + 2\ n)\)\ SUM[1 + k] == 0}\)], "Output"] }, Closed]], Cell["This recurrence is satisfied by u(m,n,k) defined below:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[%, SUM[k + 1]]\)], "Input"], Cell[BoxData[ \({{SUM[1 + k] \[Rule] \(\((1 + k + 2\ m - 2\ n)\)\ SUM[k]\)\/\(2 + k + m - 2\ n\)}}\)], "Output"] }, Closed]], Cell[BoxData[ \(u[m_, n_, k_] := Binomial[2 m - 2 n + k, k]/Binomial[m - 2 n + k + 1, k]\)], "Input"], Cell["Here is a check: the consecutive-term ratio is correct.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(FS[u[m, n, k + 1]/u[m, n, k]]\)], "Input"], Cell[BoxData[ \(\(1 + k + 2\ m - 2\ n\)\/\(2 + k + m - 2\ n\)\)], "Output"] }, Closed]], Cell["\<\ So the inner sum equals u(m,n,k) times a factor which is independent of k. To \ find it, we evaluate the sum at k=0 using Gosper's algorithm:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Binomial[k + j, k]\ Binomial[2\ n - m - 2\ k - j - 3, 2\ \((n - m - k - 1)\)] /. k -> 0\)], "Input"], Cell[BoxData[ \(Binomial[\(-3\) - j - m + 2\ n, 2\ \((\(-1\) - m + n)\)]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(GosperSum[%, {j, 0, m - 1}]\)], "Input"], Cell[BoxData[ \(\(-\(\(\((\(-2\) - m + 2\ n)\)\ Binomial[\(-3\) - m + 2\ n, 2\ \((\(-1\) - m + n)\)]\)\/\(1 + 2\ m - 2\ n\)\)\)\)], "Output"] }, Closed]], Cell[TextData[{ "This actually equals ", Cell[BoxData[ FormBox[ TagBox[ RowBox[{"(", GridBox[{ {\(\(-m\) + 2\ n - 2\)}, {\(m - 1\)} }], ")"}], Binomial, Editable->False], TraditionalForm]]], ":" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(FS[%/Binomial[2 n - m - 2, m - 1]]\)], "Input"], Cell[BoxData[ \(Binomial[\(-m\) + 2\ n, \(-2\)\ m + 2\ n]\/Binomial[\(-m\) + 2\ n, m] \)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% /. Binomial[n_, k_Plus] -> Binomial[n, n - k]\)], "Input"], Cell[BoxData[ \(1\)], "Output"] }, Closed]], Cell["Now Gosper's algorithm succeeds on the outer sum:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(GosperSum[Binomial[2 n - m - 2, m - 1] u[m, n, k], {k, 0, n - m - 1}] \)], "Input"], Cell[BoxData[ \(\(-\(\(\((1 + m - 2\ n)\)\ Binomial[\(-2\) - m + 2\ n, \(-1\) + m]\)\/m \)\) + \(\((m - n)\)\ Binomial[\(-1\) + m - n, \(-1\) - m + n]\ Binomial[\(-2\) - m + 2\ n, \(-1\) + m]\)\/\(m\ Binomial[\(-n\), \(-1\) - m + n]\)\)], "Output"] }, Closed]], Cell[TextData[{ "This is actually equal to ", Cell[BoxData[ FormBox[ RowBox[{ TagBox[ RowBox[{"(", GridBox[{ {\(\(-m\) + 2\ n - 1\)}, {"m"} }], ")"}], Binomial, Editable->False], "-", TagBox[ RowBox[{"(", GridBox[{ {\(n - 1\)}, {"m"} }], ")"}], Binomial, Editable->False]}], TraditionalForm]]], " as shown by the following computations:" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(%[\([1]\)]/Binomial[2 n - m - 1, m] // FS\)], "Input"], Cell[BoxData[ \(1\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(%%[\([2]\)]/Binomial[n - 1, m] // FS\)], "Input"], Cell[BoxData[ \(\(2\ n\ Binomial[m - n, \(-m\) + n]\ Binomial[\(-m\) + 2\ n, m]\)\/\(\((m - 2\ n)\)\ Binomial[\(-n\), \(-m\) + n]\ Binomial[n, m]\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(FS[%, m]\)], "Input"], Cell[BoxData[ \(\(2\ \((\(-1\) + 2\ n)\)\ Binomial[1 - n, \(-1\) + n]\)\/\(\((1 - 2\ n)\)\ Binomial[\(-n\), \(-1\) + n]\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(FS[%]\)], "Input"], Cell[BoxData[ \(\(-1\)\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["10375", "Subsection"], Cell["Algorithm Hyper finds one hypergeometric solution:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Hyper[ U[n + 2] == 2 \((2 n + 3)\)^2 U[n + 1] - 4 \((n + 1)\)^2 \((2 n + 1)\) \((2 n + 3)\) U[n], U[n], Solutions -> All]\)], "Input"], Cell[BoxData[ \({2\ \((1 + n)\)\ \((1 + 2\ n)\)}\)], "Output"] }, Closed]], Cell["This consecutive-term ratio corresponds to (2n)!.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(FS[\(\((2 \((n + 1)\))\)!\)/\(\((2 n)\)!\)]\)], "Input"], Cell[BoxData[ \(2\ \((1 + n)\)\ \((1 + 2\ n)\)\)], "Output"] }, Closed]], Cell["\<\ To find another linearly independent solution, we reduce the order by \ substituting (2n)! x(n) for U(n):\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(U[n + 2] == 2 \((2 n + 3)\)^2 U[n + 1] - 4 \((n + 1)\)^2 \((2 n + 1)\) \((2 n + 3)\) U[n] /. U[n_] -> \(\((2 n)\)!\) x[n]\)], "Input"], Cell[BoxData[ \(\(\((2\ \((2 + n)\))\)!\)\ x[2 + n] == \(-4\)\ \((1 + n)\)\^2\ \((1 + 2\ n)\)\ \((3 + 2\ n)\)\ \(\((2\ n)\)!\)\ x[n] + 2\ \((3 + 2\ n)\)\^2\ \(\((2\ \((1 + n)\))\)!\)\ x[1 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(FS[%[\([1]\)] - %[\([2]\)]]\)], "Input"], Cell[BoxData[ \(4\ \((1 + n)\)\ \((3 + 2\ n)\)\ \(\((1 + 2\ n)\)!\)\ \((x[n] + n\ x[n] - 3\ x[1 + n] - 2\ n\ x[1 + n] + 2\ x[2 + n] + n\ x[2 + n])\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Select[%, \(! FreeQ[#, x]\)&]\)], "Input"], Cell[BoxData[ \(x[n] + n\ x[n] - 3\ x[1 + n] - 2\ n\ x[1 + n] + 2\ x[2 + n] + n\ x[2 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Collect[%, {x[n], x[n + 1], x[n + 2]}]\)], "Input"], Cell[BoxData[ \(\((1 + n)\)\ x[n] + \((\(-3\) - 2\ n)\)\ x[1 + n] + \((2 + n)\)\ x[2 + n]\)], "Output"] }, Closed]], Cell["\<\ The order of the recurrence satisfied by d(n) = x(n+1) - x(n) should be one \ less:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(% //. {x[n + 2] -> d[n + 1] + x[n + 1], x[n + 1] -> d[n] + x[n]}\)], "Input"], Cell[BoxData[ \(\((1 + n)\)\ x[n] + \((\(-3\) - 2\ n)\)\ \((d[n] + x[n])\) + \((2 + n)\)\ \((d[n] + d[1 + n] + x[n])\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% // Expand\)], "Input"], Cell[BoxData[ \(\(-d[n]\) - n\ d[n] + 2\ d[1 + n] + n\ d[1 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Collect[%, {d[n], d[n + 1]}]\)], "Input"], Cell[BoxData[ \(\((\(-1\) - n)\)\ d[n] + \((2 + n)\)\ d[1 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[% == 0, d[n + 1]]\)], "Input"], Cell[BoxData[ \({{d[1 + n] \[Rule] \(\((1 + n)\)\ d[n]\)\/\(2 + n\)}}\)], "Output"] }, Closed]], Cell["This shows that d(n) is a constant multiple of 1/(n+1).", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(d[n] == 1/\((n + 1)\) /. d[n_] -> x[n + 1] - x[n]\)], "Input"], Cell[BoxData[ \(\(-x[n]\) + x[1 + n] == 1\/\(1 + n\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% /. n -> n - 1\)], "Input"], Cell[BoxData[ \(\(-x[\(-1\) + n]\) + x[n] == 1\/n\)], "Output"] }, Closed]], Cell[TextData[{ "From this, x(n) equals the n-th harmonic number, H(n), plus a constant. \ Hence the general solution is (2n)! (", Cell[BoxData[ \(TraditionalForm\`C\_1\)]], " + ", Cell[BoxData[ \(TraditionalForm\`C\_2\)]], " H(n)) where ", Cell[BoxData[ \(TraditionalForm\`C\_1\)]], " and ", Cell[BoxData[ \(TraditionalForm\`C\_2\)]], " are constants." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["10388", "Subsection", Evaluatable->False], Cell["\<\ Denote the sum in question by S(n,p). Zeilberger's algorithm finds a \ second-order recurrence w.r.t. p for the sum of even terms in S(n,p)\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[n, 2 k] Binomial[\((n - 3)\)/4 - k + p, 2 p], {k, 0, Infinity}, p, 1]\)], "Input"], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[n, 2 k] Binomial[\((n - 3)\)/4 - k + p, 2 p], {k, 0, Infinity}, p, 2]\)], "Input"], Cell[BoxData[ \({\((\(-7\) + n - 4\ p)\)\ \((\(-5\) + n - 4\ p)\)\ \((\(-3\) + n - 4\ p)\)\ \((\(-1\) + n - 4\ p)\)\ SUM[p] - 16\ \((\(-7\) + n - 4\ p)\)\ \((\(-5\) + n - 4\ p)\)\ \((\(-14\) + 5\ n - 20\ p + 4\ n\ p - 8\ p\^2)\)\ SUM[1 + p] + 512\ \((\(-4\) + n - 2\ p)\)\ \((\(-3\) + n - 2\ p)\)\ \((2 + p)\)\ \((3 + 2\ p)\)\ SUM[2 + p] == 0}\)], "Output"] }, Closed]], Cell["and the same recurrence for the sum of odd terms in S(n,p)", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[n, 2 k + 1] Binomial[\((n - 3)\)/4 - k - 1/2 + p, 2 p], { k, 0, Infinity}, p, 2]\)], "Input"], Cell[BoxData[ \({\((\(-7\) + n - 4\ p)\)\ \((\(-5\) + n - 4\ p)\)\ \((\(-3\) + n - 4\ p)\)\ \((\(-1\) + n - 4\ p)\)\ SUM[p] - 16\ \((\(-7\) + n - 4\ p)\)\ \((\(-5\) + n - 4\ p)\)\ \((\(-14\) + 5\ n - 20\ p + 4\ n\ p - 8\ p\^2)\)\ SUM[1 + p] + 512\ \((\(-4\) + n - 2\ p)\)\ \((\(-3\) + n - 2\ p)\)\ \((2 + p)\)\ \((3 + 2\ p)\)\ SUM[2 + p] == 0}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% === %%\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Closed]], Cell["\<\ so this recurrence is satisfied also by S(n,p) itself. Hyper finds two \ hypergeometric solutions of this recurrence, which we denote by a(p) and \ b(p).\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Hyper[%%[\([1]\)], SUM[p], Solutions -> All]\)], "Input"], Cell[BoxData[ \({\(- \(\(\((1 - n + 4\ p)\)\ \((3 - n + 4\ p)\)\)\/\(32\ \((1 + p)\)\ \((1 - n + 2\ p)\)\)\)\), \(-\(\(\((1 - n + 4\ p)\)\ \((3 - n + 4\ p)\)\)\/\(16\ \((1 + 2\ p)\)\ \((2 - n + 2\ p)\)\)\)\)}\)], "Output"] }, Closed]], Cell[BoxData[ \(Clear[a, b]\)], "Input"], Cell[BoxData[ \(a[p_] := Binomial[\((n - 3)\)/4, p] Binomial[\((n - 1)\)/4, p]/\((4^p\ Binomial[\((n - 1)\)/2, p])\)\)], "Input"], Cell[BoxData[ \(b[p_] := Binomial[\((n - 3)\)/4, p] Binomial[\((n - 1)\)/4, p]/ \((\((\(-4\))\)^p\ Binomial[\(-1\)/2, p] Binomial[\((n - 2)\)/2, p]) \)\)], "Input"], Cell["\<\ Here is a check that their consecutive-term ratios are right:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(FS[a[p + 1]/a[p]]\)], "Input"], Cell[BoxData[ \(\(\((\(-3\) + n - 4\ p)\)\ \((\(-1\) + n - 4\ p)\)\)\/\(32\ \((\(-1\) + n - 2\ p)\)\ \((1 + p)\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(FS[b[p + 1]/b[p]]\)], "Input"], Cell[BoxData[ \(\(-\(\(\((1 - n + 4\ p)\)\ \((3 - n + 4\ p)\)\)\/\(16\ \((1 + 2\ p)\)\ \((2 - n + 2\ p)\)\)\)\)\)], "Output"] }, Closed]], Cell[TextData[{ "So ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(S(n, p)\), "=", RowBox[{\(C1(n)\), FractionBox[ RowBox[{ RowBox[{ TagBox[ RowBox[{"(", GridBox[{ {\(\(n - 3\)\/4\)}, {"p"} }], ")"}], Binomial, Editable->False], " ", TagBox[ RowBox[{"(", GridBox[{ {\(\(n - 1\)\/4\)}, {"p"} }], ")"}], Binomial, Editable->False]}], " "}], RowBox[{\(4\^p\), " ", TagBox[ RowBox[{"(", GridBox[{ {\(\(n - 1\)\/2\)}, {"p"} }], ")"}], Binomial, Editable->False]}]]}]}], "\n"}], TraditionalForm]]], "+ C2(n)", Cell[BoxData[ FormBox[ FractionBox[ RowBox[{" ", RowBox[{ TagBox[ RowBox[{"(", GridBox[{ {\(\(n - 3\)\/4\)}, {"p"} }], ")"}], Binomial, Editable->False], " ", TagBox[ RowBox[{"(", GridBox[{ {\(\(n - 1\)\/4\)}, {"p"} }], ")"}], Binomial, Editable->False]}]}], RowBox[{\(\((\(-4\))\)\^p\), " ", TagBox[ RowBox[{"(", GridBox[{ {\(-\(1\/2\)\)}, {"p"} }], ")"}], Binomial, Editable->False], " ", TagBox[ RowBox[{"(", GridBox[{ {\(\(n - 2\)\/2\)}, {"p"} }], ")"}], Binomial, Editable->False]}]], TraditionalForm]]], ". Clearly, ", Cell[BoxData[ \(TraditionalForm\`S(n, 0) = 2\^n\)]], ". Zeilberger's algorithm finds a first-order recurrence for S(n,1)" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[n, k] Binomial[\((n - 3)\)/4 - k/2 + 1, 2], {k, 0, Infinity}, n, 1]\)], "Input"], Cell[BoxData[ \({2\ \((\(-2\) + n)\)\ SUM[n] + \((3 - n)\)\ SUM[1 + n] == 0}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[%, SUM[n + 1]]\)], "Input"], Cell[BoxData[ \({{SUM[1 + n] \[Rule] \(2\ \((\(-2\) + n)\)\ SUM[n]\)\/\(\(-3\) + n\)}} \)], "Output"] }, Closed]], Cell[TextData[{ "which shows that ", Cell[BoxData[ \(TraditionalForm\`S(n, 1) = C\ \((n - 3)\)\ 2\^n\)]], ". Comparing the values at n=0 shows that ", Cell[BoxData[ \(TraditionalForm\`C = 1\/32\)]] }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Binomial[n, k] Binomial[\((n - 3)\)/4 - k/2 + 1, 2] /. {n -> 0, k -> 0} \)], "Input"], Cell[BoxData[ \(\(-\(3\/32\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(\((n - 3)\) 2^n /. n -> 0\)], "Input"], Cell[BoxData[ \(\(-3\)\)], "Output"] }, Closed]], Cell[TextData[{ "and so ", Cell[BoxData[ \(TraditionalForm\`S(n, 1) = \ \((n - 3)\)\ 2\^n\)]], "/32. Finally," }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[{C1\ a[0] + C2\ b[0]\ == \ 2^n, C1\ a[1] + C2\ b[1]\ == \ \((n - 3)\) 2^n/32}, {C1, C2}]\)], "Input"], Cell[BoxData[ \({{C1 \[Rule] 2\^n, C2 \[Rule] 0}}\)], "Output"] }, Closed]], Cell[TextData[{ "which means that ", Cell[BoxData[ FormBox[ RowBox[{\(S(n, p)\), "=", FractionBox[ RowBox[{\(2\^n\), " ", TagBox[ RowBox[{"(", GridBox[{ {\(\(n - 3\)\/4\)}, {"p"} }], ")"}], Binomial, Editable->False], " ", TagBox[ RowBox[{"(", GridBox[{ {\(\(n - 1\)\/4\)}, {"p"} }], ")"}], Binomial, Editable->False]}], RowBox[{\(4\^p\), " ", TagBox[ RowBox[{"(", GridBox[{ {\(\(n - 1\)\/2\)}, {"p"} }], ")"}], Binomial, Editable->False]}]]}], TraditionalForm]]], "." }], "Text"], Cell[BoxData[ \(Clear[a, b]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["10396", "Subsection"], Cell[CellGroupData[{ Cell[BoxData[ \(Hyper[ b[n + 1] == \((2\ n + 1)\)\ b[n] - \((n\^2 + \[Alpha]\^2)\)\ b[n - 1], b[n], Solutions \[Rule] All, Quadratics \[Rule] True]\)], "Input"], Cell[BoxData[ \({1 + n - I\ \[Alpha], 1 + n + I\ \[Alpha]}\)], "Output"] }, Closed]], Cell[TextData[{ "This means that the general solution of this recurrence is ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"C1", " ", TagBox[\(\((1 - \[ImaginaryI]\ \[Alpha])\)\_n\), Pochhammer]}], "+", RowBox[{"C2", " ", TagBox[\(\((\[ImaginaryI]\ \[Alpha] + 1)\)\_n\), Pochhammer]}]}], TraditionalForm]]], ". From the initial conditions we find C1 and C2:" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[{ C1\ Pochhammer[1 - I\ \[Alpha], 1] + C2\ Pochhammer[1 + I\ \[Alpha], 1] == \[Alpha], C1\ Pochhammer[1 - I\ \[Alpha], 2] + C2\ Pochhammer[1 + I\ \[Alpha], 2] == 3 \[Alpha]}, {C1, C2}]\)], "Input"], Cell[BoxData[ \({{C1 \[Rule] I\/2, C2 \[Rule] \(-\(I\/2\)\)}}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(C1\ Pochhammer[1 - I\ \[Alpha], n] + C2\ Pochhammer[1 + I\ \[Alpha], n] /. %\)], "Input"], Cell[BoxData[ \({1\/2\ I\ Pochhammer[1 - I\ \[Alpha], n] - 1\/2\ I\ Pochhammer[1 + I\ \[Alpha], n]}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% // Factor\)], "Input"], Cell[BoxData[ \({1\/2\ I\ \((Pochhammer[1 - I\ \[Alpha], n] - Pochhammer[1 + I\ \[Alpha], n])\)} \)], "Output"] }, Closed]], Cell[TextData[{ "Hence ", Cell[BoxData[ \(TraditionalForm\`b\_n\)]], " = ", Cell[BoxData[ FormBox[ RowBox[{"Im", "(", TagBox[\(\((1 + \[ImaginaryI]\ \[Alpha])\)\_n\), Pochhammer], ")"}], TraditionalForm]]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["10403", "Subsection"], Cell[TextData[{ "Hyper finds one solution of the corresponding homogeneous equation, namely \ ", Cell[BoxData[ \(TraditionalForm\`\(n!\)\ 2\^n\)]], ":" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Hyper[y[n + 1] == \((2\ n + 3)\)\ y[n] - 2\ n\ y[n - 1], y[n], Solutions -> All]\)], "Input"], Cell[BoxData[ \({2\ \((1 + n)\)}\)], "Output"] }, Closed]], Cell["\<\ By the well-known reduction of order we can now find the general solution of \ the inhomogeneous equation:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(y[n + 1] == \((2\ n + 3)\)\ y[n] - 2\ n\ y[n - 1] + 8\ n /. y[n_] -> \(n!\) 2^n\ x[n]\)], "Input"], Cell[BoxData[ \(2\^\(1 + n\)\ \(\((1 + n)\)!\)\ x[1 + n] == 8\ n - 2\^n\ n\ \(\((\(-1\) + n)\)!\)\ x[\(-1\) + n] + 2\^n\ \((3 + 2\ n)\)\ \(n!\)\ x[n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(%[\([1]\)] - %[\([2]\)] // FS\)], "Input"], Cell[BoxData[ \(\(-8\)\ n + 2\^n\ \(n!\)\ x[\(-1\) + n] - 3\ 2\^n\ \(n!\)\ x[n] - 2\^\(1 + n\)\ n\ \(n!\)\ x[n] + 2\^\(1 + n\)\ \(n!\)\ x[1 + n] + 2\^\(1 + n\)\ n\ \(n!\)\ x[1 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(%/\((\(n!\) 2^n)\) // Expand\)], "Input"], Cell[BoxData[ \(\(-\(\(2\^\(3 - n\)\ n\)\/\(n!\)\)\) + x[\(-1\) + n] - 3\ x[n] - 2\ n\ x[n] + 2\ x[1 + n] + 2\ n\ x[1 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Collect[%, {x[n - 1], x[n], x[n + 1]}]\)], "Input"], Cell[BoxData[ \(\(-\(\(2\^\(3 - n\)\ n\)\/\(n!\)\)\) + x[\(-1\) + n] + \((\(-3\) - 2\ n)\)\ x[n] + \((2 + 2\ n)\)\ x[1 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% //. {x[n + 1] -> d[n] + x[n], x[n] -> d[n - 1] + x[n - 1]}\)], "Input"], Cell[BoxData[ \(\(-\(\(2\^\(3 - n\)\ n\)\/\(n!\)\)\) + x[\(-1\) + n] + \((\(-3\) - 2\ n)\)\ \((d[\(-1\) + n] + x[\(-1\) + n])\) + \((2 + 2\ n)\)\ \((d[\(-1\) + n] + d[n] + x[\(-1\) + n])\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% // Expand\)], "Input"], Cell[BoxData[ \(\(-d[\(-1\) + n]\) + 2\ d[n] + 2\ n\ d[n] - \(2\^\(3 - n\)\ n\)\/\(n!\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Collect[%, {d[n - 1], d[n]}]\)], "Input"], Cell[BoxData[ \(\(-d[\(-1\) + n]\) + \((2 + 2\ n)\)\ d[n] - \(2\^\(3 - n\)\ n\)\/\(n!\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% /. d[n_] -> u[n]/\((2^n\ \(\((n + 1)\)!\))\) // FS\)], "Input"], Cell[BoxData[ \(\(-\(\(2\^\(1 - n\)\ \((4\ n + u[\(-1\) + n] - u[n])\)\)\/\(n! \)\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Select[%, \(! FreeQ[#, u]\)&]\)], "Input"], Cell[BoxData[ \(4\ n + u[\(-1\) + n] - u[n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[% == 0, u[n]]\)], "Input"], Cell[BoxData[ \({{u[n] \[Rule] 4\ n + u[\(-1\) + n]}}\)], "Output"] }, Closed]], Cell[BoxData[ \(u[n_] := 2 n \((n + 1)\) + C\)], "Input"], Cell[BoxData[ \(d[n_] := u[n]/\((2^n\ \(\((n + 1)\)!\))\)\)], "Input"], Cell[TextData[{ "To prevent ", StyleBox["Mathematica", FontSlant->"Italic"], " from evaluating our sum in terms of the incomplete \[CapitalGamma] \ function, we use InertSum to denote the summation sign:" }], "Text"], Cell[BoxData[ \(x[n_] := InertSum[d[k - 1], {k, 1, n}] + D\)], "Input"], Cell[BoxData[ \(y[n_] := \(n!\) 2^n\ x[n]\)], "Input"], Cell["\<\ Now y[n] is the general solution of the original equation. It contains two \ arbitrary constants, C and D, which can be determined from the initial \ conditions:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[{y[0] == 1, y[1] == 3} /. InertSum -> Sum, {C, D}]\)], "Input"], Cell[BoxData[ \({{C \[Rule] 1\/2, D \[Rule] 1}}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(y[n] /. %[\([1]\)]\)], "Input"], Cell[BoxData[ \(2\^n\ \(n!\)\ \((1 + InertSum[ \(2\^\(1 - k\)\ \((1\/2 + 2\ \((\(-1\) + k)\)\ k)\)\)\/\(k!\), { k, 1, n}])\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% // Simplify\)], "Input"], Cell[BoxData[ \(2\^n\ \(n!\)\ \((1 + InertSum[\(2\^\(-k\)\ \((1 - 2\ k)\)\^2\)\/\(k!\), {k, 1, n}]) \)\)], "Output"] }, Closed]], Cell[BoxData[ \(Clear[u, d, x, y]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["10424", "Subsection"], Cell["\<\ Zeilberger's algorithm finds a recurrence of order 3 for this sum:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[2^k\ \ Binomial[n - k, \ 2 k] n/\((n - k)\), {k, 0, n - 1}, n, 1] \)], "Input"], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[2^k\ \ Binomial[n - k, \ 2 k] n/\((n - k)\), {k, 0, n - 1}, n, 2] \)], "Input"], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[2^k\ \ Binomial[n - k, \ 2 k] n/\((n - k)\), {k, 0, n - 1}, n, 3] \)], "Input"], Cell[BoxData[ \("If `-1 + n' is a natural number, then:"\)], "Print"], Cell[BoxData[ \({\(-2\)\ SUM[n] + SUM[1 + n] - 2\ SUM[2 + n] + SUM[3 + n] == \(1\/14175\(( 2\^\(\(-3\) + n\)\ \((\(-3\) + n)\)\ \((\(-2\) + n)\)\ \((\(-1\) + n)\)\ \((\(-5\) + 2\ n)\)\ \((\(-3\) + 2\ n)\)\ \((\(-1\) + 2\ n)\)\ \((18 + 63\ n + 53\ n\^2 + 10\ n\^3)\)\ Binomial[10, 6 + 2\ \((\(-1\) + n)\)])\)\)}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(%[\([1, 1]\)] == FS[%[\([1, 2]\)]]\)], "Input"], Cell[BoxData[ \(\(-2\)\ SUM[n] + SUM[1 + n] - 2\ SUM[2 + n] + SUM[3 + n] == 0\)], "Output"] }, Closed]], Cell["\<\ This recurrence is easy to solve because it has constant coefficients. Hyper \ can also handle such recurrences:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Hyper[%, SUM[n], Solutions -> All, Quadratics -> True]\)], "Input"], Cell[BoxData[ \({\(-I\), I, 2}\)], "Output"] }, Closed]], Cell["This means that the general solution is", "Text"], Cell[BoxData[ \(s[n_] := A\ 2^n + B\ I^n + C \((\(-I\))\)^n\)], "Input"], Cell["The constants A, B, C are found from the initial conditions.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ Sum[2^k\ \ Binomial[n - k, \ 2 k] n/\((n - k)\), {k, 0, n - 1}], {n, 1, 3}]\)], "Input"], Cell[BoxData[ \({1, 1, 4}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Solve[Thread[{s[1], s[2], s[3]} == %], {A, B, C}]\)], "Input"], Cell[BoxData[ \({{A \[Rule] 1\/2, B \[Rule] 1\/2, C \[Rule] 1\/2}}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(s[n] /. %[\([1]\)]\)], "Input"], Cell[BoxData[ \(\((\(-I\))\)\^n\/2 + I\^n\/2 + 2\^\(\(-1\) + n\)\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["10466", "Subsection", Evaluatable->False], Cell["\<\ a) Zeilberger's algorithm finds an inhomogeneous recurrence w.r.t. n of order \ 1 for the left-hand side:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[\((\(-4\))\)^n\ Binomial[x + 1/2, j] Binomial[n - 1 - x, 2 n - j], { j, 0, n}, n, 1]\)], "Input"], Cell[BoxData[ \("If `n' is a natural number, then:"\)], "Print"], Cell[BoxData[ \({\((1 + 2\ n)\)\ SUM[n] - 2\ \((1 + n)\)\ SUM[1 + n] == \(-\(\((\((\(-1\))\)\^n\ 2\^\(1 + 2\ n\)\ \((1 + n)\)\ \((2 + n)\)\ \((\(-1\) + 2\ n - 2\ x)\)\ \((1 + 3\ n - 2\ x)\)\ Binomial[1 + n - x, 2 + n]\ Binomial[3\/2 + x, 1 + n])\)/ \((\((n - x)\)\ \((1 + n - x)\)\ \((3 + 2\ x)\))\)\)\)}\)], "Output"] }, Closed]], Cell["\<\ We homogenize this recurrence and obtain a recurrence of order 2 which we \ call \"rec\":\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(eq1\ = \ \((%[\([1, 1]\)] == FS[%[\([1, 2]\)]])\)\)], "Input"], Cell[BoxData[ \(\((1 + 2\ n)\)\ SUM[n] - 2\ \((1 + n)\)\ SUM[1 + n] == \(1\/\(\((1 + n)\)\ \((n - x)\)\)\(( \((\(-2\))\)\^\(2\ n\)\ \((\(-1\) + 2\ n - 2\ x)\)\ \((1 + 3\ n - 2\ x)\)\ x\ Binomial[\(-1\) + x, n]\ Binomial[1\/2 + x, n])\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(eq2 = eq1 /. n -> n + 1\)], "Input"], Cell[BoxData[ \(\((1 + 2\ \((1 + n)\))\)\ SUM[1 + n] - 2\ \((2 + n)\)\ SUM[2 + n] == \(1\/\(\((2 + n)\)\ \((1 + n - x)\)\)\(( \((\(-2\))\)\^\(2\ \((1 + n)\)\)\ \((\(-1\) + 2\ \((1 + n)\) - 2\ x)\)\ \((1 + 3\ \((1 + n)\) - 2\ x)\)\ x\ Binomial[\(-1\) + x, 1 + n]\ Binomial[1\/2 + x, 1 + n])\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(eq2[\([2]\)]/eq1[\([2]\)] // FS\)], "Input"], Cell[BoxData[ \(\(2\ \((1 + 2\ n - 2\ x)\)\ \((4 + 3\ n - 2\ x)\)\ \((n - x)\)\)\/\(\((1 + n)\)\ \((2 + n)\)\ \((1 + 3\ n - 2\ x)\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(eq1[\([1]\)] % - eq2[\([1]\)] // Factor\)], "Input"], Cell[BoxData[ \(\(-\(\(( \(-8\)\ n\ SUM[n] - 38\ n\^2\ SUM[n] - 56\ n\^3\ SUM[n] - 24\ n\^4\ SUM[n] + 8\ x\ SUM[n] + 58\ n\ x\ SUM[n] + 116\ n\^2\ x\ SUM[n] + 64\ n\^3\ x\ SUM[n] - 20\ x\^2\ SUM[n] - 68\ n\ x\^2\ SUM[n] - 56\ n\^2\ x\^2\ SUM[n] + 8\ x\^3\ SUM[n] + 16\ n\ x\^3\ SUM[n] + 6\ SUM[1 + n] + 47\ n\ SUM[1 + n] + 108\ n\^2\ SUM[1 + n] + 97\ n\^3\ SUM[1 + n] + 30\ n\^4\ SUM[1 + n] - 28\ x\ SUM[1 + n] - 126\ n\ x\ SUM[1 + n] - 166\ n\^2\ x\ SUM[1 + n] - 68\ n\^3\ x\ SUM[1 + n] + 40\ x\^2\ SUM[1 + n] + 96\ n\ x\^2\ SUM[1 + n] + 56\ n\^2\ x\^2\ SUM[1 + n] - 16\ x\^3\ SUM[1 + n] - 16\ n\ x\^3\ SUM[1 + n] - 8\ SUM[2 + n] - 40\ n\ SUM[2 + n] - 58\ n\^2\ SUM[2 + n] - 32\ n\^3\ SUM[2 + n] - 6\ n\^4\ SUM[2 + n] + 16\ x\ SUM[2 + n] + 32\ n\ x\ SUM[2 + n] + 20\ n\^2\ x\ SUM[2 + n] + 4\ n\^3\ x\ SUM[2 + n])\)/ \((\((1 + n)\)\ \((2 + n)\)\ \((1 + 3\ n - 2\ x)\))\)\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Select[%, \(! FreeQ[#, SUM]\)&]\)], "Input"], Cell[BoxData[ \(\(-8\)\ n\ SUM[n] - 38\ n\^2\ SUM[n] - 56\ n\^3\ SUM[n] - 24\ n\^4\ SUM[n] + 8\ x\ SUM[n] + 58\ n\ x\ SUM[n] + 116\ n\^2\ x\ SUM[n] + 64\ n\^3\ x\ SUM[n] - 20\ x\^2\ SUM[n] - 68\ n\ x\^2\ SUM[n] - 56\ n\^2\ x\^2\ SUM[n] + 8\ x\^3\ SUM[n] + 16\ n\ x\^3\ SUM[n] + 6\ SUM[1 + n] + 47\ n\ SUM[1 + n] + 108\ n\^2\ SUM[1 + n] + 97\ n\^3\ SUM[1 + n] + 30\ n\^4\ SUM[1 + n] - 28\ x\ SUM[1 + n] - 126\ n\ x\ SUM[1 + n] - 166\ n\^2\ x\ SUM[1 + n] - 68\ n\^3\ x\ SUM[1 + n] + 40\ x\^2\ SUM[1 + n] + 96\ n\ x\^2\ SUM[1 + n] + 56\ n\^2\ x\^2\ SUM[1 + n] - 16\ x\^3\ SUM[1 + n] - 16\ n\ x\^3\ SUM[1 + n] - 8\ SUM[2 + n] - 40\ n\ SUM[2 + n] - 58\ n\^2\ SUM[2 + n] - 32\ n\^3\ SUM[2 + n] - 6\ n\^4\ SUM[2 + n] + 16\ x\ SUM[2 + n] + 32\ n\ x\ SUM[2 + n] + 20\ n\^2\ x\ SUM[2 + n] + 4\ n\^3\ x\ SUM[2 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Collect[%, SUM/@{n, n + 1, n + 2}]\)], "Input"], Cell[BoxData[ \(\((\(-8\)\ n - 38\ n\^2 - 56\ n\^3 - 24\ n\^4 + 8\ x + 58\ n\ x + 116\ n\^2\ x + 64\ n\^3\ x - 20\ x\^2 - 68\ n\ x\^2 - 56\ n\^2\ x\^2 + 8\ x\^3 + 16\ n\ x\^3)\)\ SUM[n] + \((6 + 47\ n + 108\ n\^2 + 97\ n\^3 + 30\ n\^4 - 28\ x - 126\ n\ x - 166\ n\^2\ x - 68\ n\^3\ x + 40\ x\^2 + 96\ n\ x\^2 + 56\ n\^2\ x\^2 - 16\ x\^3 - 16\ n\ x\^3)\)\ SUM[1 + n] + \((\(-8\) - 40\ n - 58\ n\^2 - 32\ n\^3 - 6\ n\^4 + 16\ x + 32\ n\ x + 20\ n\^2\ x + 4\ n\^3\ x)\)\ SUM[2 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(rec = Factor\ /@\ %\)], "Input"], Cell[BoxData[ \(\(-2\)\ \((1 + 2\ n)\)\ \((1 + 2\ n - 2\ x)\)\ \((4 + 3\ n - 2\ x)\)\ \((n - x)\)\ SUM[n] + \((1 + n)\)\ \((6 + 41\ n + 67\ n\^2 + 30\ n\^3 - 28\ x - 98\ n\ x - 68\ n\^2\ x + 40\ x\^2 + 56\ n\ x\^2 - 16\ x\^3)\)\ SUM[1 + n] - 2\ \((1 + n)\)\ \((2 + n)\)\^2\ \((1 + 3\ n - 2\ x)\)\ SUM[2 + n]\)], "Output"] }, Closed]], Cell["Now we use Zeilberger's algorithm on the right-hand side:", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[2 n, n] Binomial[x + j, 2 j] Binomial[x - j, 2 n - 2 j], {j, 0, n}, n, 1]\)], "Input"], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[2 n, n] Binomial[x + j, 2 j] Binomial[x - j, 2 n - 2 j], {j, 0, n}, n, 2]\)], "Input"], Cell[BoxData[ \("If `n' is a natural number, then:"\)], "Print"], Cell[BoxData[ \({\(-2\)\ \((1 + 2\ n)\)\ \((1 + 2\ n - 2\ x)\)\ \((4 + 3\ n - 2\ x)\)\ \((n - x)\)\ SUM[n] + \((1 + n)\)\ \((6 + 41\ n + 67\ n\^2 + 30\ n\^3 - 28\ x - 98\ n\ x - 68\ n\^2\ x + 40\ x\^2 + 56\ n\ x\^2 - 16\ x\^3)\)\ SUM[1 + n] - 2\ \((1 + n)\)\ \((2 + n)\)\^2\ \((1 + 3\ n - 2\ x)\)\ SUM[2 + n] == 0}\)], "Output"] }, Closed]], Cell["\<\ This same recurrence is also satisfied by the left-hand side:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(%[\([1, 1]\)] === rec\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Closed]], Cell["\<\ The identity follows after checking it for two consecutive values of n:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ Sum[\((\(-4\))\)^n\ Binomial[x + 1/2, j] Binomial[n - 1 - x, 2 n - j], {j, 0, n}], {n, 0, 1}] // Factor \)], "Input"], Cell[BoxData[ \({1, 2\ x\^2}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ Sum[Binomial[2 n, n] Binomial[x + j, 2 j] Binomial[x - j, 2 n - 2 j], {j, 0, n}], {n, 0, 1}] // Factor \)], "Input"], Cell[BoxData[ \({1, 2\ x\^2}\)], "Output"] }, Closed]], Cell["\<\ b) The left-hand side is the same as before. We use Zeilberger's algorithm on \ the right-hand side w.r.t. m:\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[2 n, n] Binomial[x + j, 2 j + m] Binomial[x - j, 2 n - m - 2 j], {j, \(-m\), n}, m, 1]\)], "Input"], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[2 n, n] Binomial[x + j, 2 j + m] Binomial[x - j, 2 n - m - 2 j], {j, \(-m\), n}, m, 2]\)], "Input"], Cell[BoxData[ \("If `m + n' is a natural number\nand `2 n' is no negative integer, \ then:"\)], "Print"], Cell[BoxData[ \({\((\(-1\) - m)\)\ SUM[m] + 2\ n\ SUM[1 + m] + \((1 + m - 2\ n)\)\ SUM[2 + m] == \((\((\(-2\) + m)\)\ \((\(-1\) + m)\)\ m\ \((1 + m)\)\ \((3 + 2\ m)\)\ \((\(-2\)\ n + x)\)\ \((1 - 2\ n + x)\)\ \((2 - 2\ n + x)\)\ Binomial[2\ n, n]\ Binomial[2 - m + x, 2 - m]\ Binomial[4 + m + x, 2 + m + 2\ n]) \)/\((\((\(-2\) + m - x)\)\ \((\(-1\) + m - x)\)\ \((m - x)\)\ \((1 + m - x)\)\ \((2 + m + x)\)\ \((3 + m + x)\)\ \((4 + m + x)\))\) - \((m\ \((1 + m)\)\ \((3 + 2\ m)\)\ \((m + n - x)\)\ Binomial[2\ n, n]\ Binomial[2 - n + x, \(-m\)]\ Binomial[2 + n + x, 2 + m + 2\ n])\)/ \((\((\(-2\) + n - x)\)\ \((\(-1\) + n - x)\)\ \((2 + n + x)\))\)} \)], "Output"] }, Closed]], Cell[TextData[{ "As m\[GreaterEqual]0, the right-hand side vanishes (note the factors ", Cell[BoxData[ FormBox[ RowBox[{\((m - 2)\), " ", \((m - 1)\), " ", "m", " ", TagBox[ RowBox[{"(", GridBox[{ {\(\(-m\) + x + 2\)}, {\(2 - m\)} }], ")"}], Binomial, Editable->False]}], TraditionalForm]]], " resp. ", Cell[BoxData[ FormBox[ RowBox[{"m", " ", TagBox[ RowBox[{"(", GridBox[{ {\(\(-n\) + x + 2\)}, {\(-m\)} }], ")"}], Binomial, Editable->False]}], TraditionalForm]]], "):" }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(%[\([1, 1]\)] == 0\)], "Input"], Cell[BoxData[ \(\((\(-1\) - m)\)\ SUM[m] + 2\ n\ SUM[1 + m] + \((1 + m - 2\ n)\)\ SUM[2 + m] == 0\)], "Output"] }, Closed]], Cell["\<\ When m=0 the right-hand side coincides with the one in a). When m=1 \ Zeilberger's algorithm finds our old acquaintance \"rec\" again (but \ multiplied by the factor of n):\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[2 n, n] Binomial[x + j, 2 j + 1] Binomial[x - j, 2 n - 1 - 2 j], {j, \(-1\), n}, n, 1]\)], "Input"], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[2 n, n] Binomial[x + j, 2 j + 1] Binomial[x - j, 2 n - 1 - 2 j], {j, \(-1\), n}, n, 2]\)], "Input"], Cell[BoxData[ \("If `1 + n' is a natural number\nand `2 n' is no negative integer, \ then:"\)], "Print"], Cell[BoxData[ \({\(-2\)\ n\ \((1 + 2\ n)\)\ \((1 + 2\ n - 2\ x)\)\ \((4 + 3\ n - 2\ x)\)\ \((n - x)\)\ SUM[n] + n\ \((1 + n)\)\ \((6 + 41\ n + 67\ n\^2 + 30\ n\^3 - 28\ x - 98\ n\ x - 68\ n\^2\ x + 40\ x\^2 + 56\ n\ x\^2 - 16\ x\^3)\)\ SUM[1 + n] - 2\ n\ \((1 + n)\)\ \((2 + n)\)\^2\ \((1 + 3\ n - 2\ x)\)\ SUM[2 + n] == 0}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Collect[%[\([1, 1]\)]/n // Expand, SUM/@{n, n + 1, n + 2}]\)], "Input"], Cell[BoxData[ \(\((\(-8\)\ n - 38\ n\^2 - 56\ n\^3 - 24\ n\^4 + 8\ x + 58\ n\ x + 116\ n\^2\ x + 64\ n\^3\ x - 20\ x\^2 - 68\ n\ x\^2 - 56\ n\^2\ x\^2 + 8\ x\^3 + 16\ n\ x\^3)\)\ SUM[n] + \((6 + 47\ n + 108\ n\^2 + 97\ n\^3 + 30\ n\^4 - 28\ x - 126\ n\ x - 166\ n\^2\ x - 68\ n\^3\ x + 40\ x\^2 + 96\ n\ x\^2 + 56\ n\^2\ x\^2 - 16\ x\^3 - 16\ n\ x\^3)\)\ SUM[1 + n] + \((\(-8\) - 40\ n - 58\ n\^2 - 32\ n\^3 - 6\ n\^4 + 16\ x + 32\ n\ x + 20\ n\^2\ x + 4\ n\^3\ x)\)\ SUM[2 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Factor\ /@\ %\)], "Input"], Cell[BoxData[ \(\(-2\)\ \((1 + 2\ n)\)\ \((1 + 2\ n - 2\ x)\)\ \((4 + 3\ n - 2\ x)\)\ \((n - x)\)\ SUM[n] + \((1 + n)\)\ \((6 + 41\ n + 67\ n\^2 + 30\ n\^3 - 28\ x - 98\ n\ x - 68\ n\^2\ x + 40\ x\^2 + 56\ n\ x\^2 - 16\ x\^3)\)\ SUM[1 + n] - 2\ \((1 + n)\)\ \((2 + n)\)\^2\ \((1 + 3\ n - 2\ x)\)\ SUM[2 + n]\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% === rec\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Closed]], Cell["\<\ Comparing the values at n=1 and n=2 we see that this is indeed equal to the \ right-hand side of a):\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ Sum[Binomial[2 n, n] Binomial[x + j, 2 j + 1] Binomial[x - j, 2 n - 1 - 2 j], {j, \(-1\), n}], {n, 1, 2}] // Factor\)], "Input"], Cell[BoxData[ \({2\ x\^2, \((\(-1\) + x)\)\ x\ \((\(-1\) - 2\ x + 2\ x\^2)\)}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Table[ Sum[Binomial[2 n, n] Binomial[x + j, 2 j] Binomial[x - j, 2 n - 2 j], {j, \(-1\), n}], {n, 1, 2}] // Factor\)], "Input"], Cell[BoxData[ \({2\ x\^2, \((\(-1\) + x)\)\ x\ \((\(-1\) - 2\ x + 2\ x\^2)\)}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% === %%\)], "Input"], Cell[BoxData[ \(True\)], "Output"] }, Closed]], Cell["\<\ So for m=1 and for m=2 the right-hand side in b) equals that in a). Thanks to \ the recurrence w.r.t. m that it satisfies, it is independent of m and the \ identity is proved.\ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["10473", "Subsection"], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[2 m + 1, 2 k] 3^k/\((5\ 2^m)\), \ {k, 0, m}, \ m, \ 1] \)], "Input"], Cell[BoxData[ \({}\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(Zb[Binomial[2 m + 1, 2 k] 3^k/\((5\ 2^m)\), \ {k, 0, m}, \ m, \ 2] \)], "Input"], Cell[BoxData[ \("If `m' is a natural number, then:"\)], "Print"], Cell[BoxData[ \({SUM[m] - 4\ SUM[1 + m] + SUM[2 + m] == 0}\)], "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["10494", "Subsection", Evaluatable->False], Cell["Gosper's algorithm does the job.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(GosperSum[ \((\((\(-1\))\)^k\ Binomial[4 n, 2 k])\)/Binomial[2 n, k], {k, 0, 2 n}]\)], "Input", PageWidth->Infinity], Cell[BoxData[ \(\(-\(1\/\(2\ \((\(-1\) + 2\ n)\)\)\)\) - \((\(-1\))\)\^\(2\ n\)\/\(2\ \((\(-1\) + 2\ n)\)\)\)], "Output"] }, Closed]], Cell[CellGroupData[{ Cell[BoxData[ \(% /. \((\(-1\))\)^\((2 n)\) -> 1\)], "Input"], Cell[BoxData[ \(\(-\(1\/\(\(-1\) + 2\ n\)\)\)\)], "Output"] }, Closed]] }, Closed]] }, Open ]] }, FrontEndVersion->"Microsoft Windows 3.0", ScreenRectangle->{{0, 1280}, {0, 968}}, ScreenStyleEnvironment->"Presentation", WindowToolbars->{}, WindowSize->{731, 607}, WindowMargins->{{40, Automatic}, {Automatic, 5}}, PrivateNotebookOptions->{"ColorPalette"->{RGBColor, -1}}, ShowCellLabel->True, ShowCellTags->False, RenderingOptions->{"ObjectDithering"->True, "RasterDithering"->False} ] (*********************************************************************** 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[1731, 51, 152, 5, 122, "Subtitle"], Cell[1886, 58, 35, 0, 68, "Subsubtitle"], Cell[1924, 60, 1523, 31, 420, "Text"], Cell[CellGroupData[{ Cell[3472, 95, 42, 0, 68, "Subsection"], Cell[3517, 97, 922, 26, 245, "Text"], Cell[CellGroupData[{ Cell[4464, 127, 66, 2, 38, "Input"], Cell[4533, 131, 98, 2, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[4668, 138, 63, 2, 32, "Input"], Cell[4734, 142, 245, 4, 74, "Message"], Cell[4982, 148, 99, 2, 28, "Print"], Cell[5084, 152, 173, 3, 28, "Print"] }, Closed]], Cell[5272, 158, 416, 13, 89, "Text"], Cell[CellGroupData[{ Cell[5713, 175, 67, 2, 38, "Input"], Cell[5783, 179, 145, 2, 51, "Print"] }, Closed]], Cell[5943, 184, 66, 2, 32, "Input"] }, Open ]], Cell[CellGroupData[{ Cell[6046, 191, 48, 1, 68, "Subsection", Evaluatable->False], Cell[6097, 194, 1623, 38, 162, "Text"], Cell[CellGroupData[{ Cell[7745, 236, 154, 3, 61, "Input"], Cell[7902, 241, 113, 2, 57, "Output"] }, Closed]], Cell[8030, 246, 376, 13, 54, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[8443, 264, 50, 1, 68, "Subsection", Evaluatable->False], Cell[8496, 267, 42, 1, 45, "Text"], Cell[8541, 270, 532, 18, 58, "Text"], Cell[9076, 290, 287, 12, 45, "Text"], Cell[9366, 304, 263, 9, 70, "Text"], Cell[CellGroupData[{ Cell[9654, 317, 143, 3, 40, "Input"], Cell[9800, 322, 36, 1, 38, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[9873, 328, 143, 3, 40, "Input"], Cell[10019, 333, 68, 1, 28, "Print"], Cell[10090, 336, 148, 2, 39, "Output"] }, Open ]], Cell[10253, 341, 922, 32, 95, "Text"], Cell[CellGroupData[{ Cell[11200, 377, 86, 1, 38, "Input"], Cell[11289, 380, 231, 4, 94, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[11557, 389, 46, 1, 32, "Input"], Cell[11606, 392, 249, 4, 96, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[11892, 401, 42, 1, 32, "Input"], Cell[11937, 404, 224, 5, 88, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[12198, 414, 64, 1, 32, "Input"], Cell[12265, 417, 143, 2, 61, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[12445, 424, 85, 1, 32, "Input"], Cell[12533, 427, 129, 2, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[12699, 434, 53, 1, 32, "Input"], Cell[12755, 437, 128, 2, 38, "Output"] }, Closed]], Cell[12898, 442, 779, 27, 64, "Text"], Cell[CellGroupData[{ Cell[13702, 473, 210, 4, 85, "Input"], Cell[13915, 479, 67, 1, 38, "Output"] }, Closed]] }, Open ]], Cell[CellGroupData[{ Cell[14031, 486, 50, 1, 40, "Subsection", Evaluatable->False], Cell[14084, 489, 161, 6, 45, "Text"], Cell[14248, 497, 564, 16, 73, "Text"], Cell[14815, 515, 438, 14, 44, "Text"], Cell[15256, 531, 395, 10, 64, "Text"], Cell[15654, 543, 98, 2, 44, "Text"], Cell[CellGroupData[{ Cell[15777, 549, 179, 4, 84, "Input"], Cell[15959, 555, 127, 2, 56, "Output"] }, Closed]], Cell[16101, 560, 151, 5, 45, "Text"], Cell[CellGroupData[{ Cell[16277, 569, 212, 5, 84, "Input"], Cell[16492, 576, 35, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[16576, 583, 50, 1, 40, "Subsection", Evaluatable->False], Cell[16629, 586, 951, 28, 122, "Text"], Cell[17583, 616, 94, 2, 44, "Text"], Cell[CellGroupData[{ Cell[17702, 622, 159, 4, 38, "Input"], Cell[17864, 628, 68, 1, 28, "Print"], Cell[17935, 631, 127, 2, 38, "Output"] }, Closed]], Cell[18077, 636, 91, 2, 44, "Text"], Cell[CellGroupData[{ Cell[18193, 642, 48, 1, 38, "Input"], Cell[18244, 645, 128, 2, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[18409, 652, 74, 1, 38, "Input"], Cell[18486, 655, 180, 3, 39, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[18703, 663, 47, 1, 38, "Input"], Cell[18753, 666, 158, 3, 54, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[18948, 674, 51, 1, 38, "Input"], Cell[19002, 677, 124, 2, 54, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[19163, 684, 53, 1, 38, "Input"], Cell[19219, 687, 138, 2, 54, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[19394, 694, 48, 1, 38, "Input"], Cell[19445, 697, 99, 2, 54, "Output"] }, Closed]], Cell[19559, 702, 33, 0, 44, "Text"], Cell[19595, 704, 527, 15, 96, "Text"], Cell[20125, 721, 60, 0, 44, "Text"], Cell[CellGroupData[{ Cell[20210, 725, 53, 1, 38, "Input"], Cell[20266, 728, 80, 1, 59, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[20383, 734, 79, 2, 38, "Input"], Cell[20465, 738, 150, 3, 57, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[20652, 746, 109, 2, 38, "Input"], Cell[20764, 750, 154, 3, 57, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[20955, 758, 46, 1, 38, "Input"], Cell[21004, 761, 102, 2, 54, "Output"] }, Closed]], Cell[21121, 766, 60, 0, 44, "Text"], Cell[CellGroupData[{ Cell[21206, 770, 59, 1, 38, "Input"], Cell[21268, 773, 127, 2, 56, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[21432, 780, 66, 1, 38, "Input"], Cell[21501, 783, 92, 1, 54, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[21630, 789, 44, 1, 38, "Input"], Cell[21677, 792, 85, 1, 54, "Output"] }, Closed]], Cell[21777, 796, 126, 3, 44, "Text"], Cell[CellGroupData[{ Cell[21928, 803, 197, 4, 148, "Input"], Cell[22128, 809, 67, 1, 38, "Output"] }, Closed]], Cell[22210, 813, 41, 0, 44, "Text"], Cell[22254, 815, 128, 3, 58, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[22419, 823, 50, 1, 40, "Subsection", Evaluatable->False], Cell[22472, 826, 620, 20, 69, "Text"], Cell[23095, 848, 48, 0, 44, "Text"], Cell[CellGroupData[{ Cell[23168, 852, 112, 2, 38, "Input"], Cell[23283, 856, 35, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[23367, 863, 26, 0, 40, "Subsection"], Cell[23396, 865, 1140, 32, 98, "Text"], Cell[24539, 899, 122, 3, 44, "Text"], Cell[24664, 904, 145, 3, 61, "Input"], Cell[CellGroupData[{ Cell[24834, 911, 188, 6, 54, "Input"], Cell[25025, 919, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[25098, 925, 188, 6, 54, "Input"], Cell[25289, 933, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[25362, 939, 188, 6, 54, "Input"], Cell[25553, 947, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[25626, 953, 188, 6, 54, "Input"], Cell[25817, 961, 664, 12, 176, "Output"] }, Closed]], Cell[26496, 976, 76, 0, 44, "Text"], Cell[CellGroupData[{ Cell[26597, 980, 188, 6, 54, "Input"], Cell[26788, 988, 664, 12, 176, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[27489, 1005, 40, 1, 38, "Input"], Cell[27532, 1008, 38, 1, 38, "Output"] }, Closed]], Cell[27585, 1012, 96, 2, 44, "Text"], Cell[CellGroupData[{ Cell[27706, 1018, 271, 8, 77, "Input"], Cell[27980, 1028, 46, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[28075, 1035, 50, 1, 40, "Subsection", Evaluatable->False], Cell[28128, 1038, 48, 0, 44, "Text"], Cell[CellGroupData[{ Cell[28201, 1042, 177, 4, 64, "Input"], Cell[28381, 1048, 35, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[28465, 1055, 50, 1, 40, "Subsection", Evaluatable->False], Cell[28518, 1058, 69, 0, 44, "Text"], Cell[CellGroupData[{ Cell[28612, 1062, 152, 3, 60, "Input"], Cell[28767, 1067, 68, 1, 28, "Print"], Cell[28838, 1070, 228, 4, 88, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[29103, 1079, 48, 1, 38, "Input"], Cell[29154, 1082, 286, 5, 88, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[29477, 1092, 51, 1, 38, "Input"], Cell[29531, 1095, 257, 4, 59, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[29825, 1104, 40, 1, 38, "Input"], Cell[29868, 1107, 114, 2, 57, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[30031, 1115, 50, 1, 40, "Subsection", Evaluatable->False], Cell[30084, 1118, 163, 3, 68, "Text"], Cell[30250, 1123, 47, 1, 38, "Input"], Cell[30300, 1126, 98, 2, 38, "Input"], Cell[CellGroupData[{ Cell[30423, 1132, 101, 2, 38, "Input"], Cell[30527, 1136, 196, 3, 59, "Output"] }, Closed]], Cell[30738, 1142, 53, 0, 44, "Text"], Cell[CellGroupData[{ Cell[30816, 1146, 44, 1, 38, "Input"], Cell[30863, 1149, 103, 2, 57, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[31003, 1156, 61, 1, 38, "Input"], Cell[31067, 1159, 35, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[31151, 1166, 28, 0, 40, "Subsection"], Cell[31182, 1168, 58, 0, 44, "Text"], Cell[CellGroupData[{ Cell[31265, 1172, 110, 2, 61, "Input"], Cell[31378, 1176, 56, 1, 53, "Output"] }, Closed]], Cell[31449, 1180, 75, 0, 44, "Text"], Cell[CellGroupData[{ Cell[31549, 1184, 112, 2, 38, "Input"], Cell[31664, 1188, 87, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[31788, 1194, 56, 1, 38, "Input"], Cell[31847, 1197, 91, 1, 38, "Output"] }, Closed]], Cell[31953, 1201, 89, 2, 44, "Text"], Cell[CellGroupData[{ Cell[32067, 1207, 79, 1, 38, "Input"], Cell[32149, 1210, 127, 2, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[32313, 1217, 44, 1, 38, "Input"], Cell[32360, 1220, 66, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[32463, 1226, 48, 1, 38, "Input"], Cell[32514, 1229, 82, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[32633, 1235, 52, 1, 38, "Input"], Cell[32688, 1238, 84, 1, 53, "Output"] }, Closed]], Cell[32787, 1242, 156, 5, 52, "Text"], Cell[32946, 1249, 223, 5, 85, "Text"], Cell[33172, 1256, 63, 0, 44, "Text"], Cell[33238, 1258, 195, 6, 85, "Text"], Cell[33436, 1266, 53, 0, 44, "Text"], Cell[CellGroupData[{ Cell[33514, 1270, 133, 3, 38, "Input"], Cell[33650, 1275, 74, 1, 52, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[33761, 1281, 67, 1, 38, "Input"], Cell[33831, 1284, 83, 1, 38, "Output"] }, Closed]], Cell[33929, 1288, 238, 8, 85, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[34204, 1301, 50, 1, 40, "Subsection", Evaluatable->False], Cell[CellGroupData[{ Cell[34279, 1306, 132, 3, 63, "Input"], Cell[34414, 1311, 212, 4, 71, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[34663, 1320, 67, 2, 38, "Input"], Cell[34733, 1324, 73, 1, 59, "Output"] }, Closed]], Cell[34821, 1328, 180, 3, 68, "Text"], Cell[35004, 1333, 53, 1, 38, "Input"], Cell[CellGroupData[{ Cell[35082, 1338, 72, 1, 38, "Input"], Cell[35157, 1341, 35, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[35241, 1348, 50, 1, 40, "Subsection", Evaluatable->False], Cell[35294, 1351, 90, 2, 44, "Text"], Cell[CellGroupData[{ Cell[35409, 1357, 154, 3, 63, "Input"], Cell[35566, 1362, 68, 1, 28, "Print"], Cell[35637, 1365, 404, 7, 130, "Output"] }, Closed]], Cell[36056, 1375, 92, 2, 44, "Text"], Cell[CellGroupData[{ Cell[36173, 1381, 79, 1, 38, "Input"], Cell[36255, 1384, 526, 10, 252, "Output"] }, Closed]], Cell[36796, 1397, 115, 3, 44, "Text"], Cell[CellGroupData[{ Cell[36936, 1404, 176, 4, 61, "Input"], Cell[37115, 1410, 490, 8, 191, "Output"] }, Closed]], Cell[37620, 1421, 96, 2, 44, "Text"], Cell[CellGroupData[{ Cell[37741, 1427, 169, 4, 61, "Input"], Cell[37913, 1433, 1307, 24, 401, "Output"] }, Closed]], Cell[39235, 1460, 564, 11, 141, "Text"], Cell[CellGroupData[{ Cell[39824, 1475, 146, 3, 61, "Input"], Cell[39973, 1480, 940, 17, 279, "Output"] }, Closed]], Cell[40928, 1500, 72, 0, 44, "Text"], Cell[CellGroupData[{ Cell[41025, 1504, 100, 2, 38, "Input"], Cell[41128, 1508, 410, 7, 141, "Output"] }, Closed]], Cell[41553, 1518, 272, 7, 70, "Text"], Cell[CellGroupData[{ Cell[41850, 1529, 51, 1, 38, "Input"], Cell[41904, 1532, 35, 1, 38, "Output"] }, Closed]], Cell[41954, 1536, 363, 6, 116, "Text"], Cell[CellGroupData[{ Cell[42342, 1546, 170, 4, 61, "Input"], Cell[42515, 1552, 743, 13, 237, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[43295, 1570, 176, 4, 61, "Input"], Cell[43474, 1576, 1325, 24, 348, "Output"] }, Closed]], Cell[44814, 1603, 63, 0, 44, "Text"], Cell[CellGroupData[{ Cell[44902, 1607, 87, 1, 38, "Input"], Cell[44992, 1610, 1299, 24, 292, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[46328, 1639, 49, 1, 38, "Input"], Cell[46380, 1642, 1594, 27, 383, "Output"] }, Closed]], Cell[47989, 1672, 127, 3, 44, "Text"], Cell[CellGroupData[{ Cell[48141, 1679, 130, 3, 38, "Input"], Cell[48274, 1684, 70, 1, 39, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[48393, 1691, 50, 1, 40, "Subsection", Evaluatable->False], Cell[48446, 1694, 62, 0, 44, "Text"], Cell[CellGroupData[{ Cell[48533, 1698, 130, 4, 54, "Input"], Cell[48666, 1704, 204, 4, 61, "Output"] }, Closed]], Cell[48885, 1711, 104, 3, 44, "Text"], Cell[CellGroupData[{ Cell[49014, 1718, 82, 2, 38, "Input"], Cell[49099, 1722, 73, 1, 28, "Print"], Cell[49175, 1725, 298, 5, 81, "Output"] }, Closed]], Cell[49488, 1733, 54, 0, 44, "Text"], Cell[CellGroupData[{ Cell[49567, 1737, 67, 1, 38, "Input"], Cell[49637, 1740, 93, 1, 38, "Output"] }, Closed]], Cell[49745, 1744, 67, 0, 44, "Text"], Cell[CellGroupData[{ Cell[49837, 1748, 67, 1, 38, "Input"], Cell[49907, 1751, 126, 2, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[50070, 1758, 38, 1, 38, "Input"], Cell[50111, 1761, 38, 1, 38, "Output"] }, Closed]], Cell[50164, 1765, 92, 2, 44, "Text"], Cell[CellGroupData[{ Cell[50281, 1771, 238, 5, 61, "Input"], Cell[50522, 1778, 35, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[50594, 1784, 61, 1, 38, "Input"], Cell[50658, 1787, 35, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[50742, 1794, 49, 1, 40, "Subsection", Evaluatable->False], Cell[50794, 1797, 92, 2, 44, "Text"], Cell[CellGroupData[{ Cell[50911, 1803, 97, 2, 38, "Input"], Cell[51011, 1807, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[51084, 1813, 97, 2, 38, "Input"], Cell[51184, 1817, 218, 4, 81, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[51439, 1826, 67, 1, 38, "Input"], Cell[51509, 1829, 141, 2, 38, "Output"] }, Closed]], Cell[51665, 1834, 99, 2, 44, "Text"], Cell[CellGroupData[{ Cell[51789, 1840, 164, 3, 61, "Input"], Cell[51956, 1845, 205, 3, 85, "Output"] }, Closed]], Cell[52176, 1851, 65, 0, 44, "Text"], Cell[CellGroupData[{ Cell[52266, 1855, 62, 1, 38, "Input"], Cell[52331, 1858, 205, 3, 61, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[52573, 1866, 59, 1, 38, "Input"], Cell[52635, 1869, 141, 2, 38, "Output"] }, Closed]], Cell[52791, 1874, 128, 3, 44, "Text"], Cell[CellGroupData[{ Cell[52944, 1881, 84, 1, 38, "Input"], Cell[53031, 1884, 114, 2, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[53182, 1891, 62, 1, 38, "Input"], Cell[53247, 1894, 40, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[53324, 1900, 197, 4, 84, "Input"], Cell[53524, 1906, 387, 7, 103, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[53948, 1918, 62, 1, 38, "Input"], Cell[54013, 1921, 40, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[54102, 1928, 27, 0, 40, "Subsection"], Cell[54132, 1930, 109, 3, 44, "Text"], Cell[CellGroupData[{ Cell[54266, 1937, 122, 2, 38, "Input"], Cell[54391, 1941, 73, 1, 28, "Print"], Cell[54467, 1944, 162, 3, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[54666, 1952, 123, 2, 38, "Input"], Cell[54792, 1956, 73, 1, 28, "Print"], Cell[54868, 1959, 167, 3, 38, "Output"] }, Closed]], Cell[55050, 1965, 96, 2, 44, "Text"], Cell[CellGroupData[{ Cell[55171, 1971, 72, 1, 38, "Input"], Cell[55246, 1974, 69, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[55352, 1980, 53, 1, 38, "Input"], Cell[55408, 1983, 63, 1, 38, "Output"] }, Closed]], Cell[55486, 1987, 60, 0, 44, "Text"], Cell[CellGroupData[{ Cell[55571, 1991, 159, 3, 84, "Input"], Cell[55733, 1996, 100, 2, 39, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[55870, 2003, 50, 1, 38, "Input"], Cell[55923, 2006, 35, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[56007, 2013, 49, 1, 40, "Subsection", Evaluatable->False], Cell[56059, 2016, 48, 0, 44, "Text"], Cell[CellGroupData[{ Cell[56132, 2020, 95, 1, 36, "Input"], Cell[56230, 2023, 175, 3, 66, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[56454, 2032, 49, 1, 40, "Subsection", Evaluatable->False], Cell[56506, 2035, 150, 3, 68, "Text"], Cell[CellGroupData[{ Cell[56681, 2042, 132, 2, 84, "Input"], Cell[56816, 2046, 113, 2, 57, "Output"] }, Closed]], Cell[56944, 2051, 169, 5, 44, "Text"], Cell[CellGroupData[{ Cell[57138, 2060, 128, 2, 61, "Input"], Cell[57269, 2064, 35, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[57341, 2070, 74, 1, 38, "Input"], Cell[57418, 2073, 35, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[57502, 2080, 27, 0, 40, "Subsection"], Cell[57532, 2082, 155, 5, 44, "Text"], Cell[57690, 2089, 98, 2, 38, "Input"], Cell[57791, 2093, 196, 5, 44, "Text"], Cell[CellGroupData[{ Cell[58012, 2102, 69, 1, 38, "Input"], Cell[58084, 2105, 102, 2, 39, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[58223, 2112, 62, 1, 38, "Input"], Cell[58288, 2115, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[58361, 2121, 63, 1, 38, "Input"], Cell[58427, 2124, 244, 4, 84, "Output"] }, Closed]], Cell[58686, 2131, 85, 2, 44, "Text"], Cell[CellGroupData[{ Cell[58796, 2137, 90, 1, 38, "Input"], Cell[58889, 2140, 282, 5, 109, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[59208, 2150, 40, 1, 38, "Input"], Cell[59251, 2153, 35, 1, 38, "Output"] }, Closed]], Cell[59301, 2157, 90, 2, 44, "Text"], Cell[CellGroupData[{ Cell[59416, 2163, 108, 2, 38, "Input"], Cell[59527, 2167, 60, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[59624, 2173, 56, 1, 38, "Input"], Cell[59683, 2176, 40, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[59760, 2182, 80, 1, 38, "Input"], Cell[59843, 2185, 40, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[59932, 2192, 49, 1, 40, "Subsection", Evaluatable->False], Cell[59984, 2195, 116, 3, 44, "Text"], Cell[CellGroupData[{ Cell[60125, 2202, 178, 4, 61, "Input"], Cell[60306, 2208, 145, 2, 74, "Print"], Cell[60454, 2212, 127, 2, 38, "Output"] }, Closed]], Cell[60596, 2217, 71, 0, 44, "Text"], Cell[CellGroupData[{ Cell[60692, 2221, 53, 1, 38, "Input"], Cell[60748, 2224, 130, 3, 53, "Output"] }, Closed]], Cell[60893, 2230, 115, 2, 38, "Input"], Cell[61011, 2234, 71, 0, 44, "Text"], Cell[CellGroupData[{ Cell[61107, 2238, 62, 1, 38, "Input"], Cell[61172, 2241, 79, 1, 53, "Output"] }, Closed]], Cell[61266, 2245, 165, 3, 68, "Text"], Cell[CellGroupData[{ Cell[61456, 2252, 136, 3, 38, "Input"], Cell[61595, 2257, 90, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[61722, 2263, 60, 1, 38, "Input"], Cell[61785, 2266, 171, 3, 54, "Output"] }, Closed]], Cell[61971, 2272, 304, 12, 57, "Text"], Cell[CellGroupData[{ Cell[62300, 2288, 68, 1, 38, "Input"], Cell[62371, 2291, 112, 2, 57, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[62520, 2298, 80, 1, 38, "Input"], Cell[62603, 2301, 35, 1, 38, "Output"] }, Closed]], Cell[62653, 2305, 65, 0, 44, "Text"], Cell[CellGroupData[{ Cell[62743, 2309, 110, 2, 38, "Input"], Cell[62856, 2313, 286, 4, 99, "Output"] }, Closed]], Cell[63157, 2320, 570, 20, 57, "Text"], Cell[CellGroupData[{ Cell[63752, 2344, 75, 1, 38, "Input"], Cell[63830, 2347, 35, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[63902, 2353, 69, 1, 38, "Input"], Cell[63974, 2356, 183, 3, 57, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[64194, 2364, 41, 1, 38, "Input"], Cell[64238, 2367, 157, 3, 57, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[64432, 2375, 38, 1, 38, "Input"], Cell[64473, 2378, 40, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[64562, 2385, 27, 0, 40, "Subsection"], Cell[64592, 2387, 66, 0, 44, "Text"], Cell[CellGroupData[{ Cell[64683, 2391, 191, 5, 61, "Input"], Cell[64877, 2398, 66, 1, 38, "Output"] }, Closed]], Cell[64958, 2402, 65, 0, 44, "Text"], Cell[CellGroupData[{ Cell[65048, 2406, 77, 1, 38, "Input"], Cell[65128, 2409, 64, 1, 38, "Output"] }, Closed]], Cell[65207, 2413, 129, 3, 44, "Text"], Cell[CellGroupData[{ Cell[65361, 2420, 186, 4, 61, "Input"], Cell[65550, 2426, 237, 4, 61, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[65824, 2435, 60, 1, 38, "Input"], Cell[65887, 2438, 184, 3, 61, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[66108, 2446, 62, 1, 38, "Input"], Cell[66173, 2449, 114, 2, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[66324, 2456, 71, 1, 38, "Input"], Cell[66398, 2459, 114, 2, 38, "Output"] }, Closed]], Cell[66527, 2464, 107, 3, 44, "Text"], Cell[CellGroupData[{ Cell[66659, 2471, 100, 2, 38, "Input"], Cell[66762, 2475, 143, 2, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[66942, 2482, 44, 1, 38, "Input"], Cell[66989, 2485, 81, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[67107, 2491, 61, 1, 38, "Input"], Cell[67171, 2494, 80, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[67288, 2500, 56, 1, 38, "Input"], Cell[67347, 2503, 87, 1, 53, "Output"] }, Closed]], Cell[67449, 2507, 71, 0, 44, "Text"], Cell[CellGroupData[{ Cell[67545, 2511, 82, 1, 38, "Input"], Cell[67630, 2514, 70, 1, 53, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[67737, 2520, 48, 1, 38, "Input"], Cell[67788, 2523, 67, 1, 53, "Output"] }, Closed]], Cell[67870, 2527, 407, 15, 68, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[68314, 2547, 49, 1, 40, "Subsection", Evaluatable->False], Cell[68366, 2550, 163, 3, 68, "Text"], Cell[CellGroupData[{ Cell[68554, 2557, 125, 2, 61, "Input"], Cell[68682, 2561, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[68755, 2567, 125, 2, 61, "Input"], Cell[68883, 2571, 422, 6, 107, "Output"] }, Closed]], Cell[69320, 2580, 74, 0, 44, "Text"], Cell[CellGroupData[{ Cell[69419, 2584, 135, 2, 61, "Input"], Cell[69557, 2588, 422, 6, 107, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[70016, 2599, 41, 1, 38, "Input"], Cell[70060, 2602, 38, 1, 38, "Output"] }, Closed]], Cell[70113, 2606, 177, 4, 68, "Text"], Cell[CellGroupData[{ Cell[70315, 2614, 77, 1, 38, "Input"], Cell[70395, 2617, 271, 5, 56, "Output"] }, Closed]], Cell[70681, 2625, 44, 1, 38, "Input"], Cell[70728, 2628, 152, 4, 61, "Input"], Cell[70883, 2634, 206, 5, 61, "Input"], Cell[71092, 2641, 85, 2, 44, "Text"], Cell[CellGroupData[{ Cell[71202, 2647, 50, 1, 38, "Input"], Cell[71255, 2650, 141, 2, 56, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[71433, 2657, 50, 1, 38, "Input"], Cell[71486, 2660, 142, 2, 56, "Output"] }, Closed]], Cell[71643, 2665, 2316, 71, 155, "Text"], Cell[CellGroupData[{ Cell[73984, 2740, 121, 2, 61, "Input"], Cell[74108, 2744, 97, 2, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[74242, 2751, 53, 1, 38, "Input"], Cell[74298, 2754, 111, 2, 53, "Output"] }, Closed]], Cell[74424, 2759, 229, 7, 48, "Text"], Cell[CellGroupData[{ Cell[74678, 2770, 113, 2, 38, "Input"], Cell[74794, 2774, 48, 1, 53, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[74879, 2780, 58, 1, 38, "Input"], Cell[74940, 2783, 40, 1, 38, "Output"] }, Closed]], Cell[74995, 2787, 134, 5, 44, "Text"], Cell[CellGroupData[{ Cell[75154, 2796, 138, 2, 61, "Input"], Cell[75295, 2800, 67, 1, 38, "Output"] }, Closed]], Cell[75377, 2804, 923, 30, 101, "Text"], Cell[76303, 2836, 44, 1, 38, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[76384, 2842, 27, 0, 40, "Subsection"], Cell[CellGroupData[{ Cell[76436, 2846, 177, 3, 63, "Input"], Cell[76616, 2851, 76, 1, 38, "Output"] }, Closed]], Cell[76707, 2855, 461, 12, 68, "Text"], Cell[CellGroupData[{ Cell[77193, 2871, 270, 6, 84, "Input"], Cell[77466, 2879, 79, 1, 52, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[77582, 2885, 118, 2, 38, "Input"], Cell[77703, 2889, 126, 2, 53, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[77866, 2896, 44, 1, 38, "Input"], Cell[77913, 2899, 130, 3, 53, "Output"] }, Closed]], Cell[78058, 2905, 275, 11, 44, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[78370, 2921, 27, 0, 40, "Subsection"], Cell[78400, 2923, 175, 6, 44, "Text"], Cell[CellGroupData[{ Cell[78600, 2933, 120, 2, 38, "Input"], Cell[78723, 2937, 50, 1, 38, "Output"] }, Closed]], Cell[78788, 2941, 130, 3, 68, "Text"], Cell[CellGroupData[{ Cell[78943, 2948, 125, 2, 38, "Input"], Cell[79071, 2952, 183, 3, 39, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[79291, 2960, 62, 1, 38, "Input"], Cell[79356, 2963, 212, 3, 62, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[79605, 2971, 61, 1, 38, "Input"], Cell[79669, 2974, 147, 2, 56, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[79853, 2981, 71, 1, 38, "Input"], Cell[79927, 2984, 148, 2, 56, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[80112, 2991, 93, 1, 38, "Input"], Cell[80208, 2994, 220, 3, 81, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[80465, 3002, 44, 1, 38, "Input"], Cell[80512, 3005, 112, 2, 56, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[80661, 3012, 61, 1, 38, "Input"], Cell[80725, 3015, 112, 2, 56, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[80874, 3022, 85, 1, 38, "Input"], Cell[80962, 3025, 115, 2, 56, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[81114, 3032, 62, 1, 38, "Input"], Cell[81179, 3035, 61, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[81277, 3041, 52, 1, 38, "Input"], Cell[81332, 3044, 71, 1, 38, "Output"] }, Closed]], Cell[81418, 3048, 62, 1, 38, "Input"], Cell[81483, 3051, 74, 1, 38, "Input"], Cell[81560, 3054, 226, 6, 69, "Text"], Cell[81789, 3062, 75, 1, 38, "Input"], Cell[81867, 3065, 58, 1, 38, "Input"], Cell[81928, 3068, 185, 4, 68, "Text"], Cell[CellGroupData[{ Cell[82138, 3076, 89, 1, 38, "Input"], Cell[82230, 3079, 65, 1, 53, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[82332, 3085, 51, 1, 38, "Input"], Cell[82386, 3088, 175, 4, 72, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[82598, 3097, 46, 1, 38, "Input"], Cell[82647, 3100, 135, 3, 58, "Output"] }, Closed]], Cell[82797, 3106, 50, 1, 38, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[82884, 3112, 27, 0, 41, "Subsection"], Cell[82914, 3114, 90, 2, 44, "Text"], Cell[CellGroupData[{ Cell[83029, 3120, 109, 2, 38, "Input"], Cell[83141, 3124, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[83214, 3130, 109, 2, 38, "Input"], Cell[83326, 3134, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[83399, 3140, 109, 2, 38, "Input"], Cell[83511, 3144, 73, 1, 28, "Print"], Cell[83587, 3147, 386, 6, 104, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[84010, 3158, 67, 1, 38, "Input"], Cell[84080, 3161, 98, 2, 38, "Output"] }, Closed]], Cell[84193, 3166, 136, 3, 68, "Text"], Cell[CellGroupData[{ Cell[84354, 3173, 87, 1, 38, "Input"], Cell[84444, 3176, 48, 1, 38, "Output"] }, Closed]], Cell[84507, 3180, 55, 0, 44, "Text"], Cell[84565, 3182, 76, 1, 38, "Input"], Cell[84644, 3185, 76, 0, 44, "Text"], Cell[CellGroupData[{ Cell[84745, 3189, 131, 3, 61, "Input"], Cell[84879, 3194, 43, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[84959, 3200, 82, 1, 38, "Input"], Cell[85044, 3203, 84, 1, 53, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[85165, 3209, 51, 1, 38, "Input"], Cell[85219, 3212, 82, 1, 54, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[85350, 3219, 49, 1, 41, "Subsection", Evaluatable->False], Cell[85402, 3222, 129, 3, 44, "Text"], Cell[CellGroupData[{ Cell[85556, 3229, 129, 2, 61, "Input"], Cell[85688, 3233, 68, 1, 28, "Print"], Cell[85759, 3236, 380, 6, 142, "Output"] }, Closed]], Cell[86154, 3245, 113, 3, 44, "Text"], Cell[CellGroupData[{ Cell[86292, 3252, 83, 1, 38, "Input"], Cell[86378, 3255, 292, 5, 131, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[86707, 3265, 56, 1, 38, "Input"], Cell[86766, 3268, 359, 6, 122, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[87162, 3279, 64, 1, 38, "Input"], Cell[87229, 3282, 169, 3, 56, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[87435, 3290, 72, 1, 38, "Input"], Cell[87510, 3293, 1079, 16, 269, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[88626, 3314, 64, 1, 38, "Input"], Cell[88693, 3317, 905, 13, 246, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[89635, 3335, 67, 1, 38, "Input"], Cell[89705, 3338, 575, 8, 131, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[90317, 3351, 52, 1, 38, "Input"], Cell[90372, 3354, 373, 7, 84, "Output"] }, Closed]], Cell[90760, 3364, 73, 0, 44, "Text"], Cell[CellGroupData[{ Cell[90858, 3368, 131, 2, 61, "Input"], Cell[90992, 3372, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[91065, 3378, 131, 2, 61, "Input"], Cell[91199, 3382, 68, 1, 28, "Print"], Cell[91270, 3385, 423, 8, 130, "Output"] }, Closed]], Cell[91708, 3396, 85, 2, 44, "Text"], Cell[CellGroupData[{ Cell[91818, 3402, 54, 1, 38, "Input"], Cell[91875, 3405, 38, 1, 38, "Output"] }, Closed]], Cell[91928, 3409, 95, 2, 44, "Text"], Cell[CellGroupData[{ Cell[92048, 3415, 172, 4, 84, "Input"], Cell[92223, 3421, 46, 1, 39, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[92306, 3427, 174, 4, 84, "Input"], Cell[92483, 3433, 46, 1, 39, "Output"] }, Closed]], Cell[92544, 3437, 133, 3, 68, "Text"], Cell[CellGroupData[{ Cell[92702, 3444, 144, 2, 61, "Input"], Cell[92849, 3448, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[92922, 3454, 144, 2, 61, "Input"], Cell[93069, 3458, 108, 2, 51, "Print"], Cell[93180, 3462, 851, 14, 222, "Output"] }, Closed]], Cell[94046, 3479, 723, 24, 94, "Text"], Cell[CellGroupData[{ Cell[94794, 3507, 51, 1, 38, "Input"], Cell[94848, 3510, 124, 2, 38, "Output"] }, Closed]], Cell[94987, 3515, 196, 4, 68, "Text"], Cell[CellGroupData[{ Cell[95208, 3523, 144, 2, 84, "Input"], Cell[95355, 3527, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[95428, 3533, 144, 2, 84, "Input"], Cell[95575, 3537, 108, 2, 51, "Print"], Cell[95686, 3541, 432, 8, 130, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[96155, 3554, 91, 1, 38, "Input"], Cell[96249, 3557, 575, 8, 131, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[96861, 3570, 46, 1, 38, "Input"], Cell[96910, 3573, 373, 7, 84, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[97320, 3585, 42, 1, 38, "Input"], Cell[97365, 3588, 38, 1, 38, "Output"] }, Closed]], Cell[97418, 3592, 124, 3, 44, "Text"], Cell[CellGroupData[{ Cell[97567, 3599, 187, 4, 84, "Input"], Cell[97757, 3605, 98, 2, 39, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[97892, 3612, 179, 4, 84, "Input"], Cell[98074, 3618, 98, 2, 39, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[98209, 3625, 41, 1, 38, "Input"], Cell[98253, 3628, 38, 1, 38, "Output"] }, Closed]], Cell[98306, 3632, 199, 4, 68, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[98542, 3641, 27, 0, 41, "Subsection"], Cell[CellGroupData[{ Cell[98594, 3645, 108, 2, 38, "Input"], Cell[98705, 3649, 36, 1, 38, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[98778, 3655, 108, 2, 38, "Input"], Cell[98889, 3659, 68, 1, 28, "Print"], Cell[98960, 3662, 76, 1, 38, "Output"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[99085, 3669, 49, 1, 41, "Subsection", Evaluatable->False], Cell[99137, 3672, 48, 0, 44, "Text"], Cell[CellGroupData[{ Cell[99210, 3676, 157, 4, 38, "Input"], Cell[99370, 3682, 132, 2, 59, "Output"] }, Closed]], Cell[CellGroupData[{ Cell[99539, 3689, 66, 1, 38, "Input"], Cell[99608, 3692, 63, 1, 53, "Output"] }, Closed]] }, Closed]] }, Open ]] } ] *) (*********************************************************************** End of Mathematica Notebook file. ***********************************************************************)