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.Mon, 16 Feb 2015 09:45:16 +0100Solving Recurrence equation for $n$https://ask.sagemath.org/question/25816/solving-recurrence-equation-for-n/ I have a recurrence equation $t_n$ which is defined as
$$
t_n=2.5t_{n-1}-1.5t_{n-4},\qquad \text{for }n\geq5
$$
Where $t_1=5$, $t_2=10.5$, $t_3=26.25$, and $t_4=62.625$.
I need to solve my recurrence equation for $n$ when $t_n=13\times10^{10}$. How can I achieve this in Sage?Thu, 12 Feb 2015 02:52:16 +0100https://ask.sagemath.org/question/25816/solving-recurrence-equation-for-n/Answer by kcrisman for <p>I have a recurrence equation $t_n$ which is defined as</p>
<p>$$
t_n=2.5t_{n-1}-1.5t_{n-4},\qquad \text{for }n\geq5
$$</p>
<p>Where $t_1=5$, $t_2=10.5$, $t_3=26.25$, and $t_4=62.625$.</p>
<p>I need to solve my recurrence equation for $n$ when $t_n=13\times10^{10}$. How can I achieve this in Sage?</p>
https://ask.sagemath.org/question/25816/solving-recurrence-equation-for-n/?answer=25817#post-id-25817Nothing native, but [sympy has `rsolve`](http://docs.sympy.org/0.7.5/modules/solvers/solvers.html#module-sympy.solvers.recurr) and [Maxima has `solve_rec`](http://maxima.sourceforge.net/docs/manual/de/maxima_70.html) (see e.g. [this sage-support thread](https://groups.google.com/forum/#!topic/sage-support/pYvjN7da9LY)). Unless [this ticket](http://trac.sagemath.org/ticket/15144) has something that helped?Thu, 12 Feb 2015 03:36:18 +0100https://ask.sagemath.org/question/25816/solving-recurrence-equation-for-n/?answer=25817#post-id-25817Answer by rws for <p>I have a recurrence equation $t_n$ which is defined as</p>
<p>$$
t_n=2.5t_{n-1}-1.5t_{n-4},\qquad \text{for }n\geq5
$$</p>
<p>Where $t_1=5$, $t_2=10.5$, $t_3=26.25$, and $t_4=62.625$.</p>
<p>I need to solve my recurrence equation for $n$ when $t_n=13\times10^{10}$. How can I achieve this in Sage?</p>
https://ask.sagemath.org/question/25816/solving-recurrence-equation-for-n/?answer=25840#post-id-25840Is the exact answer needed? I guess not, since the coefficients are given in floating point. Then an estimate with five significant digits should do. This is usually done symbolically by constructing the (rational) generating function of the recurrence, computing the roots of the denominator polynomial, and from the largest root `r` the asymptotics which is of form `c*r^n` for linear recurrences. This can be done manually, with Sage performing these step by step, or (when you have the g.f.) using code from [ticket #10519](http://trac.sagemath.org/ticket/10519). For examples see [my paper](https://scholar.google.com/citations?view_op=view_citation&hl=en&user=M2Ky9OkAAAAJ&citation_for_view=M2Ky9OkAAAAJ:qjMakFHDy7sC).
However, even more simple, but without getting any asymptotics as byproduct, would be to use matrix exponentiation.
See for example http://fusharblog.com/solving-linear-recurrence-for-programming-contest/. This looks like a Project Euler question anyway.Mon, 16 Feb 2015 09:45:16 +0100https://ask.sagemath.org/question/25816/solving-recurrence-equation-for-n/?answer=25840#post-id-25840