Ask Your Question

Solving Recurrence equation for $n$

asked 2015-02-12 02:52:16 +0100

student gravatar image

updated 2015-02-12 02:54:19 +0100

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?

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted

answered 2015-02-16 09:45:16 +0100

rws gravatar image

updated 2015-02-16 09:47:41 +0100

Is 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. For examples see my paper.

However, even more simple, but without getting any asymptotics as byproduct, would be to use matrix exponentiation. See for example This looks like a Project Euler question anyway.

edit flag offensive delete link more

answered 2015-02-12 03:36:18 +0100

kcrisman gravatar image

Nothing native, but sympy has rsolve and Maxima has solve_rec (see e.g. this sage-support thread). Unless this ticket has something that helped?

edit flag offensive delete link more

Your Answer

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

Add Answer

Question Tools


Asked: 2015-02-12 02:52:16 +0100

Seen: 1,448 times

Last updated: Feb 16 '15