Recursive Function Error

asked 2021-03-20 18:10:40 +0100

b@nnon.us
23 ●1 ●1 ●4

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 flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2021-03-20 23:21:43 +0100

Max Alekseyev

6488 ●9 ●47 ●153

updated 2021-03-20 23:28:32 +0100

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.

edit flag offensive delete link

Comments

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

b@nnon.us ( 2021-03-20 23:58:11 +0100 )edit

add a comment

answered 2021-03-20 18:29:37 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

updated 2021-03-21 00:11:36 +0100

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

edit flag offensive delete link

Comments

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$$.

b@nnon.us ( 2021-03-20 18:38:37 +0100 )edit

add a comment

Your Answer

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

Add Answer

Recursive Function Error

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Recursive Function Error edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Recursive Function Error