1 | initial version |

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.

2 | No.2 Revision |

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.

3 | No.3 Revision |

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

4 | No.4 Revision |

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

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.