Applied Discrete Structures by Alan Doerr & Kenneth Levasseur is licensed under a Creative Commons Attribution - Noncommercial - No Derivative Works 3.0 United States License.
Here are a few tips on how to get started using Sage to work with recursion.
Consider the recurrence relation with the initial conditions , .
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!
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.
This tells us that the solution is , but to compute with this result we need to extract the right side and use the expression to define a function called .
Note: At one point, I got advice to use the somewhat more complicated expression
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.
Here is how to define a sequence recursively. For example suppose and for positive , .
For a recursive version of the binary search algorithm, see our introduction the SageMath implementation of Binary Tree Sorting.