Just a little thought on sums of a specific form

I just had a nice thought about simple sums of the form $ \phi(n,p)=\sum_{i=0}^ni^p$.

Two simple start cases

It is well-known, that $ \phi(n,1)=\sum_{i=0}^ni=\dfrac{n\cdot(n+1)}{2}$ (this can be shown quite easily via induction).

Consider the fact, that $ \phi(n,0)=\sum_{i=0}^n1 = n+1$ (and not $ n$ as one could assume!). This is because $ 0^0=1$.

A nice trick to derive sums of higher exponents

Consider the following: If we want to compute $ f(n,2)=\sum_{i=0}^ni^2$, we can do some basic transformations to obtain something useful:


$\displaystyle \phi(n,2)$ $\displaystyle =$ $\displaystyle \sum_{i=0}^ni^2=$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{n-1}(i+1)^2=$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{n-1}(i^2+2i+1)=$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{n-1}i^2 + 2\cdot\sum_{i=0}^{n-1}i + \sum_{i=0}^{n-1}1=$  
  $\displaystyle =$ $\displaystyle \phi(n-1,2)+2\phi(n-1,1)+\phi(n-1,0)=$  
  $\displaystyle =$ $\displaystyle \phi(n,2) - n^2 +2\phi(n-1,1)+\phi(n-1,0)$  

In fact, we obtain $ \phi(n,2)=\phi(n,2)-n^2+2\phi(n-1,1)+\phi(n-1,0)$, which leads us immediately to $ 0 = 2\phi(n-1,1)+\phi(n-1,0)$. From this we can conclude $ \phi(n-1,1)=\dfrac{n^2 - \phi(n-1,0)}{2}$. That means, we could compute $ \phi(n,1)$ with an attempt to compute $ \phi(n,2)$.

Generalisation

The above calculation leads to the question, if this trick can be applied to higher order functions. In fact, it turns out, that it is possible.

So again we start with $ \phi(n,p)$ and try to do the same as above:


$\displaystyle \phi(n,p)$ $\displaystyle =$ $\displaystyle \sum_{i=0}^{i-1}(i+1)^p=$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{n-1}\left[ \sum_{k=0}^p \binom{p}{k} i^k \right]=$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{n-1}\left[ \sum_{k=0}^{p-1} \binom{p}{k} i^k + i^p \right]=$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{n-1}\left[ \sum_{k=0}^{p-1} \binom{p}{k} i^k \right] + \sum_{i=0}^ni^p - n^p=$  
  $\displaystyle =$ $\displaystyle \sum_{i=0}^{n-1}\left[ \sum_{k=0}^{p-1} \binom{p}{k} i^k \right] + \phi(n,p) - n^p$  

Swapping the sums and basic tranformations lead to:

$\displaystyle 0 = \left(\sum_{k=0}^{p-1}\binom{p}{k}\cdot\sum_{i=0}^{n-1}i^k\right)-n^p = \left(\sum_{k=0}^{p-1}\binom{p}{k}\cdot\phi(n-1,k)\right)-n^p$    

Starting with this equation it is possible to compute the closed form of $ \phi(n,k)$ for $ n,k\in\mathbb{N}$.

More precisely, the above equation can be tranfsormed to the following recursive formula:

$\displaystyle \phi(n,p)=\dfrac{(n+1)^{p+1}-\sum_{k=0}^{p-1}\binom{p+1}{k}\cdot\phi(n,k)}{p+1}$    

This calculation shows in particular, that $ \phi(n,k)$ can be written as a polynomial.

Comments

phimuemue

2010-03-31 14:26:13

Note that in the equation in "Gereralisation" there occured a little error: It must be "n-1" and not "i-1".