# Revision history [back]

My understanding of your problem is that, given a fixed integer p, you want to compute the polynomial in n of $S_p$, vuewed as a symbolic expreesion. 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.

My understanding of your problem is that, given a fixed integer p, you want to compute the polynomial in n of $S_p$, vuewed viewed as a symbolic expreesion. 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.

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


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