︠63918ce6-ce7e-408a-a9d8-2f212cc72715s︠ %md
Here are a few tips on how to get started using Sage to work with recursion. ︡1ff2202c-bfda-4749-beb3-2136e63a6159︡{"md":"
Here are a few tips on how to get started using Sage to work with recursion."}︡{"done":true} ︠bc9de986-af86-4cc7-a76f-11c772d9d2dbi︠ %md Consider the recurrence relation $$ a_{n+2}=-a_{n+1}+2 a_n$$ with the initial conditions $a_0=1$, $a_1=5$. ︡a857e11f-8563-42d0-b585-481ca93e0eb8︡{"md":"Consider the recurrence relation $$ a_{n+2}=-a_{n+1}+2 a_n$$ with the initial conditions $a_0=1$, $a_1=5$."}︡ ︠dc31c009-7d72-4800-afd2-e52b1db7f469i︠ %html
Suppose 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.
︡2e89f855-a24b-46c4-924c-966b41378a5a︡ ︠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-c1aa811e4266s︠ maxima('load("solve_rec")') ︡2da5dd7d-b5cd-4895-be12-c61e5d131d32︡{"stdout":"\"/projects/sage/sage-7.5/local/share/maxima/5.35.1/share/solve_rec/solve_rec.mac\""}︡{"stdout":"\n"}︡{"done":true} ︠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-5cfb6432ca02s︠ sol=maxima('solve_rec(a[n+2]+a[n+1]-2*a[n]=0,a[n],a[0]=1,a[1]=3)') sol ︡d8e23019-dd48-4744-811a-31a299146f7c︡{"stdout":"a[n]=(-2)^(n+1)/3+5/3\n"}︡{"done":true} ︠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 advice 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︡{"done":true,"html":"Note: At one point, I got advice 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-3459e0f607bfs︠ map(a,range(10)) ︡1f65ff6c-643a-4788-b279-7901160d87fa︡{"stdout":"[1, 3, -1, 7, -9, 23, -41, 87, -169, 343]"}︡{"stdout":"\n"}︡{"done":true} ︠668bfa38-c5af-444a-ae9b-90d7eed3baf3s︠ list_plot(map(lambda k:[k,a(k)],range(10))) ︡9f5ac43c-69cb-4e75-8369-3c27c46d432c︡{"file":{"filename":"/projects/f351622c-d261-4717-abee-4c0bfa210e88/.sage/temp/compute4-us/8440/tmp_CJ8Hgd.svg","show":true,"uuid":"b5e1cf2d-7226-4ade-bf9e-a6a7dee83e38"},"once":false}︡{"done":true} ︠0f3e8610-6793-4675-9b61-e0d3ae14c302i︠ %htmlWhat follows are some calculations and a plot of the sequence.
\n"}︡ ︠d974826d-a2cf-41df-a5c3-67c0f5456a2bs︠ a(5) ︡3d3493c9-9224-4f3b-866b-9cefb91426fa︡{"stdout":"972\n"}︡{"done":true} ︠ef863ade-76a0-4683-bf6e-62c66a303263s︠ data=[a(n) for n in range(20)] ︡80f958c5-c412-4221-885e-9e66562ab11b︡{"done":true} ︠3c35de07-888a-4e65-9528-f50908a61c89s︠ data ︡2fb3c4e8-6c86-4047-85c7-a41b9625f789︡{"stdout":"[4, 12, 36, 108, 324, 972, 2916, 8748, 26244, 78732, 236196, 708588, 2125764, 6377292, 19131876, 57395628, 172186884, 516560652, 1549681956, 4649045868]\n"}︡{"done":true} ︠73858c59-8c4a-4731-af32-26a53c4d42ces︠ var('pts') ︡702b299f-81de-4702-bdfb-1f803c59c5b2︡{"stdout":"pts\n"}︡{"done":true} ︠3ce25e58-88c0-4dfd-a6b1-ee2618a2260cs︠ pts=[(n,a(n)) for n in range(10)] ︡a0cdaeb7-b9ed-41a5-b78f-0fa57199f515︡{"done":true} ︠dfac4874-f7dd-4acc-bb6e-6b7d176892e4s︠ pts ︡2c8b9332-cfa3-45aa-b02d-49441eb1bdc1︡{"stdout":"[(0, 4), (1, 12), (2, 36), (3, 108), (4, 324), (5, 972), (6, 2916), (7, 8748), (8, 26244), (9, 78732)]\n"}︡{"done":true} ︠aa6fc5b0-ece1-48a4-b06d-c527cc4d88c4s︠ list_plot(pts,plotjoined=True, color='purple') ︡13bf15c9-ef4c-48fa-9011-b444487b6fcc︡{"file":{"filename":"/projects/f351622c-d261-4717-abee-4c0bfa210e88/.sage/temp/compute4-us/8440/tmp_2_J6EY.svg","show":true,"uuid":"73feb9a7-2fc0-41da-9cfa-137d99a67883"},"once":false}︡{"done":true} ︠20bcd216-9217-4e36-9b8d-f6c6b3b1fe9a︠ ︡2a669164-1726-4d5c-adb4-0c6e81add098︡ ︠c4b75ca6-26e2-4b00-8a6a-43044c3ea060i︠ %htmlFor a recursive version of the binary search algorithm, see our introduction the SageMath implementation of Binary Tree Sorting.
︡c09fce8b-813a-4399-a842-9590daf70827︡{"done":true,"html":"\n For a recursive version of the binary search algorithm, see our introduction the SageMath implementation of Binary Tree Sorting.\n
"} ︠48f6f070-2107-4841-8267-a1f3a2dc4d99si︠ %md