︠63918ce6-ce7e-408a-a9d8-2f212cc72715i︠ %md
Here are a few tips on how to get started using Sage to work with recursion. ︡5bd7934b-0580-4455-95fb-48b68e311b73︡{"html":"
Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial - No Derivative Works 3.0 United States License.
\n"}︡{"html":"Here are a few tips on how to get started using Sage to work with recursion.
\n"}︡ ︠8efe7fc2-bc87-4992-a92c-94f9511fc255i︠ %htmlSuppose you want to solve the recurrence relation
$$ a(n+2)+a(n+1)-2*a(n)=0$$
with the initial conditions
$$ a(0)=1, a(1)=3 . $$
Sage cannot currently solve this system, but maxima does. So we first load maxima's solve_rec function.
︡8ccf09b4-8530-46e9-9c37-ce6cc6192163︡{"done":true,"html":"Suppose you want to solve the recurrence relation
\n$$ a(n+2)+a(n+1)-2*a(n)=0$$
\nwith the initial conditions
\n$$ a(0)=1, a(1)=3 . $$
\nSage cannot currently solve this system, but maxima does. So we first load maxima's solve_rec function.
"} ︠90c3104f-0d75-44fc-9576-aa6c4a736950i︠ %md Sage cannot currently solve this system, but maxima does. So we first load maxima's solve_rec function. If this changes, I'd appreciate it if anyone would let me know! ︡82847b1a-6247-426e-a4ca-80f4842120ab︡{"html":"Sage cannot currently solve this system, but maxima does. So we first load maxima’s solve_rec function. If this changes, I’d appreciate it if anyone would let me know!
\n"}︡ ︠2372950c-9afe-4945-bca8-c1aa811e4266o︠ maxima('load("solve_rec")') ︡4ce16682-596f-4b80-9897-d3d1aaca6801︡{"stdout":"\"/usr/local/sage/sage-5.12/local/share/maxima/5.29.1/share/solve_rec/solve_rec.mac\"\n"}︡ ︠29c0819e-47a7-4660-9e15-0da47a7120f9i︠ %md Sage's maxima function sends the argument provided as a string to maxima and returns the maxima output. Here is a second order linear recurrence relation with constant coefficients. ︡3e82f3e4-ba7e-4ffd-b5b5-f56b39f46f25︡{"html":"Sage’s maxima function sends the argument provided as a string to maxima and returns the maxima output. Here is a second order linear recurrence relation with constant coefficients.
\n"}︡ ︠e72ac1af-cea3-4f2d-95fc-5cfb6432ca02i︠ sol=maxima('solve_rec(a[n+2]+a[n+1]-2*a[n]=0,a[n],a[0]=1,a[1]=3)') sol ︡3b327e90-f04b-404c-9379-ac39ab57af7a︡{"stdout":"a[n]=(-2)^(n+1)/3+5/3\n"}︡ ︠0cf23634-1a32-4364-a885-9d3130740ab8i︠ %htmlThis tells us that the solution is $a(n) = (1/3) (-2)^{n+1} + 5/3$, but to compute with this result we need to extract the right side and use the expression to define a function called $a$.
This tells us that the solution is $a(n) = (1/3) (-2)^{n+1} + 5/3$, but to compute with this result we need to extract the right side and use the expression to define a function called $a$.
\nNote: At one point, I got advise to use the somewhat more complicated expression
a(n)= maxima(sol.rhs()).sage()
which also works. It may be possible that certain solutions where the maxima output has a form that is incompatible with Sage and the more complicated expression is needed.
Here are the first few terms of the sequence and a plot.
︡4bd71ca8-dfb9-43f5-88ec-33a69adc5bdd︡{"html":"Note: At one point, I got advise to use the somewhat more complicated expression
\na(n)= maxima(sol.rhs()).sage()
\nwhich also works. It may be possible that certain solutions where the maxima output has a form that is incompatible with Sage and the more complicated expression is needed.
\n\nHere are the first few terms of the sequence and a plot.
"}︡ ︠ef5a4490-6c9a-4ec0-8508-3459e0f607bf︠ map(a,range(10)) ︡6a4c577c-aee3-4171-877a-c6b8e3b963a3︡{"stdout":"[1, 3, -1, 7, -9, 23, -41, 87, -169, 343]\n"}︡ ︠668bfa38-c5af-444a-ae9b-90d7eed3baf3︠ list_plot(map(lambda k:[k,a(k)],range(10))) ︡0b8c7905-dff7-48c7-aad2-8459d265c70a︡{"once":false,"file":{"show":true,"uuid":"0ebe879e-cf03-412b-8ee6-32326f71076b","filename":"/projects/f351622c-d261-4717-abee-4c0bfa210e88/.sage/temp/compute2a/7545/tmp_2i54Rd.png"}}︡ ︠0f3e8610-6793-4675-9b61-e0d3ae14c302i︠ %htmlHere is how to define a sequence recursively. For example suppose $a_{0}=4$ and for positive $n$, $$a_{n}=3 a_{n-1}$$.
\n"}︡ ︠8a164be6-6c2f-4455-99e8-d6fc44f5046f︠ var('a') ︡874c7c34-bc84-4362-b3fa-39d88967e346︡{"stdout":"a\n"}︡ ︠87011d1d-47ad-45bf-baa4-a51cdef4629c︠ def a(n): if n==0: return 4 else: return 3*a(n-1) ︡7bc4667e-2c90-4720-8e04-e1687f2abb60︡ ︠7e29930d-8ba4-435d-b005-a8732a0008f5i︠ %md What follows are some calculations and a plot of the sequence. ︡7b60611f-d517-431b-8513-e5c67d2ac170︡{"html":"What follows are some calculations and a plot of the sequence.
\n"}︡ ︠d974826d-a2cf-41df-a5c3-67c0f5456a2b︠ a(5) ︡b63a9d38-0f12-428a-af2a-54d5795f08e4︡{"stdout":"972\n"}︡ ︠ef863ade-76a0-4683-bf6e-62c66a303263︠ data=[a(n) for n in range(20)] ︡000b0369-5391-44a0-b757-b16ab9929ab6︡ ︠3c35de07-888a-4e65-9528-f50908a61c89︠ data ︡f09aa387-a653-48ca-b841-b93c9a73f114︡{"stdout":"[4, 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196, 708588, 2125764, 6377292, 19131876, 57395628, 172186884, 516560652, 1549681956, 4649045868]\n"}︡ ︠73858c59-8c4a-4731-af32-26a53c4d42ce︠ var('pts') ︡d5f10953-7ab2-4c16-ab2e-57c7d4756681︡{"stdout":"pts\n"}︡ ︠3ce25e58-88c0-4dfd-a6b1-ee2618a2260c︠ pts=[(n,a(n)/n) for n in range(10)] ︡04ca4396-7e0c-4ca2-88ba-7b2d10232f48︡ ︠dfac4874-f7dd-4acc-bb6e-6b7d176892e4︠ pts ︡a223f292-e564-44be-be1f-7128143ecd35︡{"stdout":"[(0, 4), (1, 12), (2, 36), (3, 108), (4, 324), (5, 972), (6, 2916), (7, 8748), (8, 26244), (9, 78732)]\n"}︡ ︠aa6fc5b0-ece1-48a4-b06d-c527cc4d88c4︠ list_plot(pts,plotjoined=True, color='purple') ︡1e8a4028-7a1a-429a-b0fb-b94ca599839d︡{"once":false,"file":{"show":true,"uuid":"9f01952c-353e-4ab5-acbd-0504fcc33f34","filename":"/projects/f351622c-d261-4717-abee-4c0bfa210e88/.sage/temp/compute2a/7545/tmp_4F0_zu.png"}}︡ ︠b9f355a3-1358-4578-a837-0a4b815c7a82i︠ %html