# Recursive Function Error

I'm trying to write a reciusive function to compute $$S_p=1^p+2^p+3^p+\dots+n^p,$$ where both $n$ and $p$ are positive integers. My Sage code correctly returns $S_1$, but does not work for $p>1$. Any ideas?

I am not a big Sage user, but I am using it as a way to introduce pre-calculus students to CAS. Hopefully, I will be able to share this post with my students, and certainly, give credit to anyone that helps fix this mess.

Here's the code:

sage: reset()
sage: k,n,p=var('k,n,p')
sage: assume(k,'integer')
sage: assume(n,'integer')
sage: assume(p,'integer')
sage: def S(p):
....:     if p == 1:
....:         return n*(n+1)/2
....:     else:
....:         return ((n+1)^(p+1) - n - 1 - sum(binomial(p+1,k)*S(p-k+1),k,2,p))
....: /(p+1)
....:
sage: S(1)
1/2*(n + 1)*n
sage: S(2)

edit retag close merge delete

Sort by ยป oldest newest most voted

Since the sum bounds are not symbolic variables but given integers, it's better to avoid using the symbolic sum(<expr>,k,2,p) but rather use Python's sum(<expr> for k in (2..p)):

n=var('n')
assume(n,'integer')
def S(p):
if p==1:
return n*(n+1)/2
return ((n+1)^(p+1) - n - 1 - sum(binomial(p+1,k)*S(p-k+1) for k in (2..p)))/(p+1)


As a side note - you don't need to define k and p as global symbolic variables, since p is defined as an argument of function S(p), while k is the sum index and automatically defined as a local variable within the sum context.

more

Thank you, Max Alekseyev. I will be sure to share this with my students!

( 2021-03-20 23:58:11 +0100 )edit

My understanding of your problem is that, given a fixed integer p, you want to compute the polynomial in n of $S_p$, viewed as a symbolic expression. If it is the case you write a function like this :

sage: k,n = SR.var('k,n')
sage: def S(p):
....:     return sum(k^p,k,1,n)


Then you can compute your polynomals (viewed as symbolic expressions)

sage: S(1)
1/2*n^2 + 1/2*n
sage: S(2)
1/3*n^3 + 1/2*n^2 + 1/6*n
sage: S(5)
1/6*n^6 + 1/2*n^5 + 5/12*n^4 - 1/12*n^2
sage: S(10)
1/11*n^11 + 1/2*n^10 + 5/6*n^9 - n^7 + n^5 - 1/2*n^3 + 5/66*n


Note that p is not a symbol, but the input of a Python function, which turns out to be an integer.

EDIT (regarding your comment) Recursivity is not a silver bullet and should be promoted wisely. In the present case, it is far from offering any computational benefit, even for relative small value of p we get a factor 1000 slowdown (and it get worse when p increases), see :

sage: n=var('n')
....: assume(n,'integer')
....: def S(p):
....:     if p==1:
....:         return n*(n+1)/2
....:     return ((n+1)^(p+1) - n - 1 - sum(binomial(p+1,k)*S(p-k+1) for k in (2..p)))/(p+1)
....:
sage: %time S(20)
CPU times: user 36.2 s, sys: 5.87 ms, total: 36.3 s
Wall time: 36.2 s

sage: sage: k,n = SR.var('k,n')
....: sage: def S(p):
....: ....:     return sum(k^p,k,1,n)
....:
sage: %time S(20)
CPU times: user 43.3 ms, sys: 3.37 ms, total: 46.7 ms
Wall time: 30.2 ms

more

Thank you very much. I Will certainly share this with my students.

However, I'm really trying to derive a recursive function to do this, mainly because I spent some time deriving a recursive relationship for computing $$S_p$$.

( 2021-03-20 18:38:37 +0100 )edit