# How can you get the n'th function in a sequence defined by a recurrence relation?

Let a_0(x) and b_0(x) be given functions. Then define a_n and b_n by the following relations (or any)

a_n(x) = a_{n-1}(x+1) - a_{n-1}(x) + a_0(x+1)a_{n-1}(x) + b_{n-1}(x) b_n(x) = b_{n-1}(x+1) - b_{n-1}(x) + a_{n-1}(x)b_0(x+1)

How can I write a program to print the n'th pair of functions in the sequence?

I'm new to sagemath and I've been trying to work through this problem on my own, but the bugs I've been running across make me think the way I'm writing my methods is wrong. Here's what I came up with using a different relation

var('x,a,b')

#the first functions in the recurrence relation. Making these more complicated will give you wrong outputs.
def lam_0(x):
return a*x
def s_0(x):
return b

#The lam_n based on the starting function lam_0.
#Example: lam_2 would be lam_forward(lam_0, s_0, z, 2)
def lam_forward(lam_func, s_func, z, n = 1):
if n <= 0:
return lam_0(z)
else:
return lam_forward(lam_func, s_func, z + 1, n - 1) - lam_forward(lam_func, s_func, z, n - 1) + lam_forward(lam_func, s_func, z + 1, n - 1)*lam_0(z) + s_forward(lam_func, s_func, z+1, n-1)

#The s_n based on the starting function s_0.
def s_forward(lam_func, s_func, z, n = 1):
if n <= 0:
return s_0(z)
else:
return s_forward(lam_func, s_func, z+1, n-1) - s_forward(lam_func, s_func, z+1, n-1) + lam_forward(lam_func, s_func, z + 1, n - 1)*s_0(z)

#Print the n'th pair of functions
def printNthFunctions(n=0):
print('Lam_', n, ' =', lam_forward(lam_0(x), s_0(x), x, n).full_simplify())
print('S_', n, ' = ', s_forward(lam_0(x), s_0(x), x, n).full_simplify())

#BUG After n=1, this does not output the correct function, even though the individual functions are correct
def d_n(z, n):
return  s_forward(lam_0(z), s_0(z), z, n)*lam_forward(lam_0(z), s_0(z), z, n-1) - s_forward(lam_0(z), s_0(z), z, n-1)*lam_forward(lam_0(z), s_0(z), z, n)

edit retag close merge delete

Sort by ยป oldest newest most voted

If I am right, these are the recurrence relations you want to deal with: \begin{aligned} a_n(x) &= a_{n-1}(x+1) - a_{n-1}(x) + a_0(x+1)a_{n-1}(x) + b_{n-1}(x) \\ b_n(x) &= b_{n-1}(x+1) - b_{n-1}(x) + a_{n-1}(x)b_0(x+1) \end{aligned} I have run the code below in a Jupyter notebook, assuming that $a_0(x)=Ax$ and $b_0(x)=B$:

var("A,B,x")
def a(n,x):
if n==0:
return A*x
else:
return a(n-1,x+1) - a(n-1,x) + a(0,x+1)*a(n-1,x) + b(n-1,x)
def b(n,x):
if n==0:
return B
else:
return b(n-1,x+1) - b(n-1,x) + a(n-1,x)*b(0,x+1)

for n in range(5):
show(html(fr"$a_{{{n}}}(x)={latex(a(n,x).full_simplify())}$"))
show(html(fr"$b_{{{n}}}(x)={latex(b(n,x).full_simplify())}$"))
show(html("<hr>"))


This is the output:

$a_{0}(x)=A x$
$b_{0}(x)=B$

$a_{1}(x)=A^{2} x^{2} + A^{2} x + A + B$
$b_{1}(x)=A B x$
$a_{2}(x)=A^{3} x^{3} + 2 \, A^{3} x^{2} + 3 \, A^{2} + A B + {\left(A^{3} + 3 \, A^{2} + 2 \, A B\right)} x$
$b_{2}(x)=A^{2} B x^{2} + A^{2} B x + 2 \, A B + B^{2}$
$a_{3}(x)=A^{4} x^{4} + 3 \, A^{4} x^{3} + 7 \, A^{3} + 3 \, {\left(A^{4} + 2 \, A^{3} + A^{2} B\right)} x^{2} + 3 \, A^{2} + {\left(A^{2} + 4 \, A\right)} B + B^{2} + {\left(A^{4} + 13 \, A^{3} + 4 \, A^{2} B\right)} x$
$b_{3}(x)=A^{3} B x^{3} + 2 \, A^{3} B x^{2} + 5 \, A^{2} B + A B^{2} + {\left(2 \, A B^{2} + {\left(A^{3} + 5 \, A^{2}\right)} B\right)} x$
$a_{4}(x)=A^{5} x^{5} + 4 \, A^{5} x^{4} + 15 \, A^{4} + 2 \, {\left(3 \, A^{5} + 5 \, A^{4} + 2 \, A^{3} B\right)} x^{3} + 22 \, A^{3} + 2 \, A B^{2} + {\left(4 \, A^{5} + 34 \, A^{4} + 9 \, A^{3} B\right)} x^{2} + {\left(A^{3} + 16 \, A^{2}\right)} B + {\left(A^{5} + 39 \, A^{4} + 15 \, A^{3} + 3 \, A B^{2} + 3 \, {\left(2 \, A^{3} + 5 \, A^{2}\right)} B\right)} x$
$b_{4}(x)=A^{4} B x^{4} + 3 \, A^{4} B x^{3} + {\left(A^{2} + 6 \, A\right)} B^{2} + B^{3} + 3 \, {\left(A^{2} B^{2} + {\left(A^{4} + 3 \, A^{3}\right)} B\right)} x^{2} + {\left(11 \, A^{3} + 8 \, A^{2}\right)} B + {\left(4 \, A^{2} B^{2} + {\left(A^{4} + 20 \, A^{3}\right)} B\right)} x$

Of course, you can increase the final value of $n$ in the loop.

more

Thank you so much! Sorry for my late response. This was exactly what I was looking for.

( 2020-04-11 07:05:29 -0500 )edit