ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 21 Nov 2019 14:01:10 +0100How to find a short form of recursive defined sequences?https://ask.sagemath.org/question/48820/how-to-find-a-short-form-of-recursive-defined-sequences/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/5Wed, 20 Nov 2019 17:33:55 +0100https://ask.sagemath.org/question/48820/how-to-find-a-short-form-of-recursive-defined-sequences/Comment by Emmanuel Charpentier for <p>Hi, I'm new to sagemath. <br>
Is there any way to so calculate/solve/find a short version of a recursive defined sequence?</p>
<p>E.g. I have a sequence like: (Fibonacci) </p>
<pre><code>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)
</code></pre>
<p>How can I compute a short form of $f_n$?</p>
<hr>
<p>In this example case $f_n$ would be: <br>
$f_n=\frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^n - \frac{1}{\sqrt{5}} (\frac{1-\sqrt{5}}{2})^n$</p>
<hr>
<p>Edit:
Thanks to Emmanuel I found how to solve those equations in pdf:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/48820/how-to-find-a-short-form-of-recursive-defined-sequences/?comment=48837#post-id-48837Now read the book, cover to cover, and keep it under your pillow...Thu, 21 Nov 2019 14:01:10 +0100https://ask.sagemath.org/question/48820/how-to-find-a-short-form-of-recursive-defined-sequences/?comment=48837#post-id-48837Answer by Emmanuel Charpentier for <p>Hi, I'm new to sagemath. <br>
Is there any way to so calculate/solve/find a short version of a recursive defined sequence?</p>
<p>E.g. I have a sequence like: (Fibonacci) </p>
<pre><code>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)
</code></pre>
<p>How can I compute a short form of $f_n$?</p>
<hr>
<p>In this example case $f_n$ would be: <br>
$f_n=\frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^n - \frac{1}{\sqrt{5}} (\frac{1-\sqrt{5}}{2})^n$</p>
<hr>
<p>Edit:
Thanks to Emmanuel I found how to solve those equations in pdf:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/48820/how-to-find-a-short-form-of-recursive-defined-sequences/?answer=48827#post-id-48827This 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](http://sagebook.gforge.inria.fr/english.html), and Maxima's and Sympy's documentations...Wed, 20 Nov 2019 20:00:16 +0100https://ask.sagemath.org/question/48820/how-to-find-a-short-form-of-recursive-defined-sequences/?answer=48827#post-id-48827Comment by maan for <p>This is possible with Sagemath: Maxima and Sympy have tools to work on <em>recurrences</em>, whose interfaces in Sage are, to say the least, not proeminently presented in Sagemath's documentation. See § 10.2 of this <a href="http://sagebook.gforge.inria.fr/english.html">excellent (free) book</a>, and Maxima's and Sympy's documentations...</p>
https://ask.sagemath.org/question/48820/how-to-find-a-short-form-of-recursive-defined-sequences/?comment=48834#post-id-48834ty, very informative pdfThu, 21 Nov 2019 13:39:35 +0100https://ask.sagemath.org/question/48820/how-to-find-a-short-form-of-recursive-defined-sequences/?comment=48834#post-id-48834