Algebra - Introduction

Summation Notation¶

The Binomial Theorem¶

(x+y)^n=\sum_{d=0}^n\binom{n}{d}x^{n-d}y^d

(1)

Sums of Powers¶

Faulhaber’s Formula¶

Leading Term Only¶

Proof 1

We proceed by induction on $p$ . If $p=0$ , then $S_p(n)=\sum_{k=1}^nk^0=n$ , which has degree $p+1=1$ and leading coefficient $\frac{1}{p+1}=1$ .

Now suppose the claim is true for all $q < p$ . We will prove the claim holds for $p$ . We have

\newcommand{\comment}[1]{ \text{\phantom{(#1)}} \tag{#1} } \begin{align*} (n+1)^{p+1}-1&=\sum_{k=1}^n(k+1)^{p+1}-k^{p+1},\\ \comment{by Binomial Theorem} &=\sum_{k=1}^n\sum_{d=0}^{p}\binom{p+1}{d}k^d,\\ \comment{re-arranging sums} &=\sum_{d=0}^{p}\binom{p+1}{d}\cdot\sum_{k=1}^nk^d,\\ \comment{by definition of $S_d$} &=\sum_{d=0}^{p}\binom{p+1}{d}\cdot S_d(n),\\ n^{p+1}+\sum_{d=1}^{p}\binom{p+1}{d}n^d&=(p+1)\cdot S_{p}(n)+\sum_{d=0}^{p-1}\binom{p+1}{d}\cdot S_d(n). \end{align*}

(2)

By the inductive hypothesis, the sum on right-hand side is a polynomial of degree at most $p$ . But the left-hand side is a polynomial of degree $p+1$ , so $S_p(n)$ must have a term of degree $p+1$ and no higher. Furthermore, as the coefficient for the $p+1$ term on the left is 1, the coefficient of the $p+1$ term on the right must be $\frac{1}{p+1}$ .

Bernoulli Numbers¶

import math
def s(d, n):
    return sum(x**d for x in range(1, n+1))

n = 5; i = 3
print( (n+1)**(i+1) - 1)
print( sum( math.comb(i+1,d) * s(d,n) for d in range(0,i+1)) )

1295
1295

The above discussion gives us an inductive definition of the coefficients. Using Theorem 1, we can write

\begin{align*} n^{p+1}+\sum_{d=1}^{p}\binom{p+1}{d}n^d&=(p+1)\cdot S_{p}(n)+\sum_{d=0}^{p-1}\binom{p+1}{d}\cdot S_d(n),\\ S_{p}(n)&=\frac{(n+1)^{p+1}-1 - \sum_{d=0}^{p-1}\binom{p+1}{d}\cdot S_d(n)}{p+1}. \end{align*}

(3)

Since we know that $S_0(n) = n$ , we can recursively compute higher sum formulas.

S_1(n)=\frac{(n+1)^2-1-S_0(n)}{2} =\frac{(n+1)^2-1-n}{2} =\frac{n^2+n}{2} =\frac{1}{2}n^2+\frac{1}{2}n

(4)

S_2(n)=\frac{(n+1)^3-1-\binom{3}{0}S_0(n)-\binom{3}{1}S_1(n)}{3} =\frac{1}{3}n^3+\frac{1}{2}n^2+\frac{1}{6}n

(5)

Example 1

def s(p, n):
    if p==0:
        return n
    else:
        return ( 
                (n+1)**(p+1) - 1 - 
                sum( math.comb(p+1, d) * s(d, n) for d in range(0, p) ) 
                ) / (p+1)
p = 12; n = 15
print( s(p, n) )
print( sum( x**p for x in range(n + 1) ) )

223160292749512.0
223160292749512

Faulhaber’s Formula¶

\sum_{k=1}^{n}k^p=\frac{1}{p+1}\sum_{r=0}^p\binom{p+1}{r}B_rn^{p+1-r}