# 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