Ask Your Question
0

How to find a short form of recursive defined sequences?

asked 2019-11-20 17:33:55 +0100

maan gravatar image

updated 2019-11-21 13:39:03 +0100

Hi, I'm new to sagemath.
Is there any way to so calculate/solve/find a short version of a recursive defined sequence?

E.g. I have a sequence like: (Fibonacci)

def f(n):                            
        if n == 0:  
                return 0  
        if n == 1:  
                return 1
        if n == 2:
                return 1
        else:
                return f(n-1)+f(n-2)

How can I compute a short form of $f_n$?


In this example case $f_n$ would be:
$f_n=\frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^n - \frac{1}{\sqrt{5}} (\frac{1-\sqrt{5}}{2})^n$


Edit: Thanks to Emmanuel I found how to solve those equations in pdf:

from sympy import Function,rsolve  
from sympy.abc import n  
u = Function('u')  
f = u(n-1)+u(n-2)-u(n)  
rsolve(f, u(n), {u(0):0,u(1):1})  

-sqrt(5)*(1/2 - sqrt(5)/2)**n/5 + sqrt(5)*(1/2 + sqrt(5)/2)**n/5
edit retag flag offensive close merge delete

Comments

Now read the book, cover to cover, and keep it under your pillow...

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2019-11-21 14:01:10 +0100 )edit

1 Answer

Sort by » oldest newest most voted
1

answered 2019-11-20 20:00:16 +0100

Emmanuel Charpentier gravatar image

This is possible with Sagemath: Maxima and Sympy have tools to work on recurrences, whose interfaces in Sage are, to say the least, not proeminently presented in Sagemath's documentation. See § 10.2 of this excellent (free) book, and Maxima's and Sympy's documentations...

edit flag offensive delete link more

Comments

ty, very informative pdf

maan gravatar imagemaan ( 2019-11-21 13:39:35 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2019-11-20 17:33:55 +0100

Seen: 668 times

Last updated: Nov 21 '19