(* Content-type: application/mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 6.0' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 145, 7] NotebookDataLength[ 16733, 596] NotebookOptionsPosition[ 15168, 540] NotebookOutlinePosition[ 15508, 555] CellTagsIndexPosition[ 15465, 552] WindowFrame->Normal ContainsDynamic->False*) (* Beginning of Notebook Content *) Notebook[{ Cell[TextData[{ "Example : we're going to solve\n\nf[n]=10 f[n-1]-37 f[n-2]+60 f[n-3]-36 \ f[n-4] + ", Cell[BoxData[ FormBox[ SuperscriptBox["2", "n"], TraditionalForm]]], "+", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox["5", "n"], "+", "3", " "}], TraditionalForm]]], "\nsubject to\nf[0]=1, f[1]=2, f[2]=5, f[3]=7\n\nFirst, we determine the \ general forms for fp and fg:" }], "Text", CellChangeTimes->{{3.442573346419875*^9, 3.4425736016855*^9}}, FontSize->16], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Factor", "[", RowBox[{ RowBox[{"x", "^", "4"}], "-", RowBox[{"10", RowBox[{"x", "^", "3"}]}], "+", RowBox[{"37", RowBox[{"x", "^", "2"}]}], "-", RowBox[{"60", "x"}], "+", "36"}], "]"}]], "Input", CellChangeTimes->{{3.44257360634175*^9, 3.44257363115425*^9}}], Cell[BoxData[ RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{"-", "3"}], "+", "x"}], ")"}], "2"], " ", SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{"-", "2"}], "+", "x"}], ")"}], "2"]}]], "Output", CellChangeTimes->{3.442573632638625*^9, 3.442575499732375*^9}] }, Open ]], Cell["\<\ Consequently, we get the following forms for fp and fg, with a total of eight \ unknown constants (a,b,c,d; P,Q,R,S) :\ \>", "Text", CellChangeTimes->{{3.44257550809175*^9, 3.442575556544875*^9}}, FontSize->18], Cell[BoxData[ RowBox[{ RowBox[{"fg", "[", "n_", "]"}], ":=", RowBox[{ RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"a", " ", "n"}], "+", "b"}], ")"}], " ", RowBox[{"2", "^", "n"}]}], " ", "+", " ", RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"c", " ", "n"}], "+", "d"}], ")"}], " ", RowBox[{"3", "^", "n"}]}]}]}]], "Input", CellChangeTimes->{{3.442573646857375*^9, 3.4425736941855*^9}}], Cell[BoxData[ RowBox[{ RowBox[{"fp", "[", "n_", "]"}], ":=", " ", RowBox[{ RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"P", " ", RowBox[{"n", "^", "3"}]}], "+", RowBox[{"Q", " ", RowBox[{"n", "^", "2"}]}]}], ")"}], RowBox[{"2", "^", "n"}]}], "+", RowBox[{"R", " ", RowBox[{"5", "^", "n"}]}], " ", "+", " ", "S"}]}]], "Input", CellChangeTimes->{{3.442573699294875*^9, 3.44257374821675*^9}}], Cell["Next, let' s solve for P, Q, R, S:", "Text", CellChangeTimes->{{3.442574326857375*^9, 3.442574348873*^9}}, FontSize->18], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"RR", "=", RowBox[{ RowBox[{"fp", "[", "n", "]"}], "-", RowBox[{"10", " ", RowBox[{"fp", "[", RowBox[{"n", "-", "1"}], "]"}]}], "+", RowBox[{"37", " ", RowBox[{"fp", "[", RowBox[{"n", "-", "2"}], "]"}]}], "-", RowBox[{"60", " ", RowBox[{"fp", "[", RowBox[{"n", "-", "3"}], "]"}]}], "+", RowBox[{"36", " ", RowBox[{"fp", "[", RowBox[{"n", "-", "4"}], "]"}]}], "-", RowBox[{"2", "^", "n"}], "-", RowBox[{"5", "^", "n"}], "-", "3"}]}]], "Input", CellChangeTimes->{{3.4425739130605*^9, 3.442573947263625*^9}, { 3.44257502452925*^9, 3.44257503171675*^9}}], Cell[BoxData[ RowBox[{ RowBox[{"-", "3"}], "-", SuperscriptBox["2", "n"], "-", SuperscriptBox["5", "n"], "+", RowBox[{ SuperscriptBox["2", "n"], " ", RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox["n", "3"], " ", "P"}], "+", RowBox[{ SuperscriptBox["n", "2"], " ", "Q"}]}], ")"}]}], "+", RowBox[{ SuperscriptBox["5", "n"], " ", "R"}], "+", "S", "+", RowBox[{"36", " ", RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox["2", RowBox[{ RowBox[{"-", "4"}], "+", "n"}]], " ", RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{"-", "4"}], "+", "n"}], ")"}], "3"], " ", "P"}], "+", RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{"-", "4"}], "+", "n"}], ")"}], "2"], " ", "Q"}]}], ")"}]}], "+", RowBox[{ SuperscriptBox["5", RowBox[{ RowBox[{"-", "4"}], "+", "n"}]], " ", "R"}], "+", "S"}], ")"}]}], "-", RowBox[{"60", " ", RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox["2", RowBox[{ RowBox[{"-", "3"}], "+", "n"}]], " ", RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{"-", "3"}], "+", "n"}], ")"}], "3"], " ", "P"}], "+", RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{"-", "3"}], "+", "n"}], ")"}], "2"], " ", "Q"}]}], ")"}]}], "+", RowBox[{ SuperscriptBox["5", RowBox[{ RowBox[{"-", "3"}], "+", "n"}]], " ", "R"}], "+", "S"}], ")"}]}], "+", RowBox[{"37", " ", RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox["2", RowBox[{ RowBox[{"-", "2"}], "+", "n"}]], " ", RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{"-", "2"}], "+", "n"}], ")"}], "3"], " ", "P"}], "+", RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{"-", "2"}], "+", "n"}], ")"}], "2"], " ", "Q"}]}], ")"}]}], "+", RowBox[{ SuperscriptBox["5", RowBox[{ RowBox[{"-", "2"}], "+", "n"}]], " ", "R"}], "+", "S"}], ")"}]}], "-", RowBox[{"10", " ", RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox["2", RowBox[{ RowBox[{"-", "1"}], "+", "n"}]], " ", RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{"-", "1"}], "+", "n"}], ")"}], "3"], " ", "P"}], "+", RowBox[{ SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{"-", "1"}], "+", "n"}], ")"}], "2"], " ", "Q"}]}], ")"}]}], "+", RowBox[{ SuperscriptBox["5", RowBox[{ RowBox[{"-", "1"}], "+", "n"}]], " ", "R"}], "+", "S"}], ")"}]}]}]], "Output", CellChangeTimes->{ 3.442573948576125*^9, {3.4425750360605*^9, 3.44257506340425*^9}}] }, Open ]], Cell["\<\ We need to solve for 4 unknowns, so we need four different values of n to do \ that. Any four will generally work.\ \>", "Text", CellChangeTimes->{{3.442574369826125*^9, 3.4425744043105*^9}}, FontSize->18], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Simplify", "[", RowBox[{ RowBox[{"(", RowBox[{"RR", "\[Equal]", "0"}], ")"}], "/.", RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{"n", "\[Rule]", "0"}], "}"}], ",", RowBox[{"{", RowBox[{"n", "\[Rule]", "1"}], "}"}], ",", RowBox[{"{", RowBox[{"n", "\[Rule]", "2"}], "}"}], ",", RowBox[{"{", RowBox[{"n", "\[Rule]", "3"}], "}"}]}], "}"}]}], "]"}]], "Input", CellChangeTimes->{{3.442574197013625*^9, 3.442574220794875*^9}, { 3.442574292607375*^9, 3.4425742951855*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{ RowBox[{ FractionBox["Q", "2"], "+", FractionBox[ RowBox[{"36", " ", "R"}], "625"], "+", RowBox[{"4", " ", "S"}]}], "\[Equal]", RowBox[{"5", "+", FractionBox[ RowBox[{"21", " ", "P"}], "2"]}]}], ",", RowBox[{ RowBox[{"Q", "+", FractionBox[ RowBox[{"36", " ", "R"}], "125"], "+", RowBox[{"4", " ", "S"}]}], "\[Equal]", RowBox[{"2", " ", RowBox[{"(", RowBox[{"5", "+", RowBox[{"9", " ", "P"}]}], ")"}]}]}], ",", RowBox[{ RowBox[{ RowBox[{"2", " ", "Q"}], "+", FractionBox[ RowBox[{"36", " ", "R"}], "25"], "+", RowBox[{"4", " ", "S"}]}], "\[Equal]", RowBox[{"32", "+", RowBox[{"30", " ", "P"}]}]}], ",", RowBox[{ RowBox[{"170", "+", RowBox[{"60", " ", "P"}]}], "\[Equal]", RowBox[{ RowBox[{"5", " ", "Q"}], "+", RowBox[{"9", " ", "R"}], "+", RowBox[{"5", " ", "S"}]}]}]}], "}"}]], "Output", CellChangeTimes->{3.442574221607375*^9, 3.44257429615425*^9, 3.442575066873*^9}] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Solve", "[", RowBox[{"%", ",", RowBox[{"{", RowBox[{"P", ",", "Q", ",", "R", ",", "S"}], "}"}]}], "]"}]], "Input", CellChangeTimes->{{3.4425742716855*^9, 3.44257427802925*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{"{", RowBox[{ RowBox[{"P", "\[Rule]", "0"}], ",", RowBox[{"Q", "\[Rule]", "2"}], ",", RowBox[{"R", "\[Rule]", FractionBox["625", "36"]}], ",", RowBox[{"S", "\[Rule]", FractionBox["3", "4"]}]}], "}"}], "}"}]], "Output", CellChangeTimes->{3.442574299201125*^9, 3.442575068388625*^9}] }, Open ]], Cell["\<\ Now, set P, Q, R and S to the computed values and we'll continue to solve for \ a, b, c and d, using the initial conditions.\ \>", "Text", CellChangeTimes->{{3.442574434326125*^9, 3.44257447940425*^9}, { 3.442574570263625*^9, 3.442574575107375*^9}}, FontSize->18], Cell[BoxData[ RowBox[{ RowBox[{"P", "=", "0"}], ";", RowBox[{"Q", "=", "2"}], ";", RowBox[{"R", "=", FractionBox["625", "36"]}], ";", RowBox[{"S", "=", FractionBox["3", "4"]}], ";"}]], "Input", CellChangeTimes->{{3.442574483919875*^9, 3.442574516388625*^9}, { 3.442575080294875*^9, 3.4425751090605*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Solve", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{ RowBox[{ RowBox[{"fp", "[", "0", "]"}], "+", RowBox[{"fg", "[", "0", "]"}]}], "\[Equal]", "1"}], ",", RowBox[{ RowBox[{ RowBox[{"fp", "[", "1", "]"}], "+", RowBox[{"fg", "[", "1", "]"}]}], "\[Equal]", "2"}], ",", RowBox[{ RowBox[{ RowBox[{"fp", "[", "2", "]"}], "+", RowBox[{"fg", "[", "2", "]"}]}], "\[Equal]", "5"}], ",", RowBox[{ RowBox[{ RowBox[{"fp", "[", "3", "]"}], "+", RowBox[{"fg", "[", "3", "]"}]}], "\[Equal]", "7"}]}], "}"}], ",", RowBox[{"{", RowBox[{"a", ",", "b", ",", "c", ",", "d"}], "}"}]}], "]"}]], "Input", CellChangeTimes->{{3.44257453246675*^9, 3.442574611607375*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{"{", RowBox[{ RowBox[{"a", "\[Rule]", RowBox[{"-", FractionBox["559", "6"]}]}], ",", RowBox[{"b", "\[Rule]", RowBox[{"-", FractionBox["4060", "9"]}]}], ",", RowBox[{"c", "\[Rule]", RowBox[{"-", "101"}]}], ",", RowBox[{"d", "\[Rule]", "434"}]}], "}"}], "}"}]], "Output", CellChangeTimes->{3.4425746144355*^9, 3.442575111451125*^9}] }, Open ]], Cell["\<\ To find the solution in all its glory, set a, b, c and d to these values, and \ simplify fp[n] + fg[n]\ \>", "Text", CellChangeTimes->{{3.442574625294875*^9, 3.442574650748*^9}}, FontSize->18], Cell[BoxData[ RowBox[{ RowBox[{"a", "=", RowBox[{"-", FractionBox["559", "6"]}]}], ";", RowBox[{"b", "=", RowBox[{"-", FractionBox["4060", "9"]}]}], ";", RowBox[{"c", "=", RowBox[{"-", "101"}]}], ";", RowBox[{"d", "=", "434"}], ";"}]], "Input", CellChangeTimes->{{3.442574659294875*^9, 3.442574705169875*^9}, { 3.442575128294875*^9, 3.44257515034175*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"FullSimplify", "[", RowBox[{ RowBox[{"fp", "[", "n", "]"}], "+", RowBox[{"fg", "[", "n", "]"}]}], "]"}]], "Input", CellChangeTimes->{{3.4425747096855*^9, 3.442574714701125*^9}, { 3.4425752265605*^9, 3.4425752270605*^9}}], Cell[BoxData[ RowBox[{ FractionBox["3", "4"], "+", FractionBox[ SuperscriptBox["5", RowBox[{"4", "+", "n"}]], "36"], "+", RowBox[{ SuperscriptBox["3", "n"], " ", RowBox[{"(", RowBox[{"434", "-", RowBox[{"101", " ", "n"}]}], ")"}]}], "+", RowBox[{ SuperscriptBox["2", "n"], " ", RowBox[{"(", RowBox[{ RowBox[{"-", FractionBox["4060", "9"]}], "-", FractionBox[ RowBox[{"559", " ", "n"}], "6"]}], ")"}]}], "+", RowBox[{ SuperscriptBox["2", RowBox[{"1", "+", "n"}]], " ", SuperscriptBox["n", "2"]}]}]], "Output", CellChangeTimes->{3.442574715638625*^9, 3.442575155263625*^9, 3.442575228107375*^9}] }, Open ]], Cell["\<\ If you like, you can now define f[n] and verify that it satisfies all the \ equations we were trying to solve :\ \>", "Text", CellChangeTimes->{{3.442574747044875*^9, 3.442574774044875*^9}}, FontSize->18], Cell[BoxData[ RowBox[{ RowBox[{"f", "[", "n_", "]"}], ":=", RowBox[{ FractionBox["3", "4"], "+", FractionBox[ SuperscriptBox["5", RowBox[{"4", "+", "n"}]], "36"], "+", RowBox[{ SuperscriptBox["3", "n"], " ", RowBox[{"(", RowBox[{"434", "-", RowBox[{"101", " ", "n"}]}], ")"}]}], "+", RowBox[{ SuperscriptBox["2", "n"], " ", RowBox[{"(", RowBox[{ RowBox[{"-", FractionBox["4060", "9"]}], "-", FractionBox[ RowBox[{"559", " ", "n"}], "6"]}], ")"}]}], "+", RowBox[{ SuperscriptBox["2", RowBox[{"1", "+", "n"}]], " ", SuperscriptBox["n", "2"]}]}]}]], "Input", CellChangeTimes->{{3.442574731732375*^9, 3.442574740748*^9}, 3.442575175326125*^9}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"f", "[", "0", "]"}], ",", RowBox[{"f", "[", "1", "]"}], ",", RowBox[{"f", "[", "2", "]"}], ",", RowBox[{"f", "[", "3", "]"}]}], "}"}]], "Input", CellChangeTimes->{{3.442574784888625*^9, 3.4425748053105*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{"1", ",", "2", ",", "5", ",", "7"}], "}"}]], "Output", CellChangeTimes->{{3.44257478646675*^9, 3.44257480584175*^9}, 3.4425751795605*^9}] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Simplify", "[", RowBox[{ RowBox[{"f", "[", "n", "]"}], "-", RowBox[{"10", " ", RowBox[{"f", "[", RowBox[{"n", "-", "1"}], "]"}]}], "+", RowBox[{"37", " ", RowBox[{"f", "[", RowBox[{"n", "-", "2"}], "]"}]}], "-", RowBox[{"60", " ", RowBox[{"f", "[", RowBox[{"n", "-", "3"}], "]"}]}], "+", RowBox[{"36", " ", RowBox[{"f", "[", RowBox[{"n", "-", "4"}], "]"}]}], "-", RowBox[{"2", "^", "n"}], "-", RowBox[{"5", "^", "n"}], "-", "3"}], "]"}]], "Input", CellChangeTimes->{{3.44257481065425*^9, 3.44257488527925*^9}, { 3.44257495559175*^9, 3.44257495821675*^9}, {3.442575189498*^9, 3.4425751928105*^9}}], Cell[BoxData["0"], "Output", CellChangeTimes->{{3.44257484221675*^9, 3.44257488646675*^9}, 3.442574959326125*^9, 3.4425751959355*^9}] }, Open ]] }, WindowSize->{611, 750}, WindowMargins->{{0, Automatic}, {Automatic, 0}}, FrontEndVersion->"6.0 for Microsoft Windows (64-bit) (April 20, 2007)", StyleDefinitions->"Default.nb" ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[568, 21, 486, 15, 165, "Text"], Cell[CellGroupData[{ Cell[1079, 40, 311, 9, 31, "Input"], Cell[1393, 51, 302, 10, 30, "Output"] }, Open ]], Cell[1710, 64, 222, 5, 57, "Text"], Cell[1935, 71, 431, 14, 31, "Input"], Cell[2369, 87, 447, 14, 31, "Input"], Cell[2819, 103, 128, 2, 34, "Text"], Cell[CellGroupData[{ Cell[2972, 109, 650, 19, 52, "Input"], Cell[3625, 130, 3191, 116, 121, "Output"] }, Open ]], Cell[6831, 249, 218, 5, 57, "Text"], Cell[CellGroupData[{ Cell[7074, 258, 560, 16, 31, "Input"], Cell[7637, 276, 1099, 37, 79, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[8773, 318, 213, 5, 31, "Input"], Cell[8989, 325, 356, 10, 45, "Output"] }, Open ]], Cell[9360, 338, 277, 6, 57, "Text"], Cell[9640, 346, 326, 9, 45, "Input"], Cell[CellGroupData[{ Cell[9991, 359, 796, 23, 52, "Input"], Cell[10790, 384, 425, 13, 45, "Output"] }, Open ]], Cell[11230, 400, 204, 5, 57, "Text"], Cell[11437, 407, 392, 12, 45, "Input"], Cell[CellGroupData[{ Cell[11854, 423, 257, 6, 31, "Input"], Cell[12114, 431, 686, 24, 48, "Output"] }, Open ]], Cell[12815, 458, 216, 5, 57, "Text"], Cell[13034, 465, 759, 26, 48, "Input"], Cell[CellGroupData[{ Cell[13818, 495, 272, 7, 31, "Input"], Cell[14093, 504, 181, 4, 30, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[14311, 513, 700, 20, 52, "Input"], Cell[15014, 535, 138, 2, 30, "Output"] }, Open ]] } ] *) (* End of internal cache information *)