% LaTeX source for matrix derivation of sums of powers of integers

\documentclass{article}

\usepackage{amstex}
\usepackage{amssymb}
\usepackage{times}

\begin{document}

\begin{center}
  {\large \textbf{MATRIX DERIVATION OF $\sum n^k$}}
\end{center}

\bigskip
\noindent Consider the formulae
\begin{align*}
  2^4-1^4&=1+4.1+6.1^2+4.1^3\\
  3^4-2^4&=1+4.2+6.2^2+4.2^3\\
  4^4-3^4&=1+4.3+6.3^2+4.3^3\\
  &\vdots\\
  n^4-(n-1)^4&=1+4.(n-1)+6.(n-1)^2+4.(n-1)^3.
\end{align*}
By addition we see that
\[ n^4=n+4S_1(n-1)+3+6S_2(n-1)+4S_3(n-1) \]
where
\[ S_r(n)=\sum_{i=1}^ni^r \]
and similarly we get the general result
\[ n^r=n+{r\choose 1}S_1(n-1)+{r\choose r-2}S_2(n-1)+\dots+
        \binom{r}{r-1}S_{r-1}(n-1). \]
The equations
\begin{align*}
  n&=n\\
  n^2&=n+S_1(n-1)\\
  n^3&=n+3S_1(n-1)+3S_2(n-1)\\
  n^4&=n+4S_1(n-1)+6S_2(n-1)+4S_3(n-1)\\
  n^5&=n+5S_1(n-1)+10S_2(n-1)+10S_3(n-1)+5S_4(n-1)\hbox{, etc.}
\end{align*}
can be written in matrix form as
\[ \left(\begin{array}{c}n\\ n^2\\ n^3\\ n^4\\ n^5\\ \vdots\end{array}\right)
   =\left(\begin{array}{ccccccc}
           1&0&0&0&0&0&\dots\\
           1&2&0&0&0&0&\dots\\
           1&3&3&0&0&0&\dots\\
           1&4&6&4&0&0&\dots\\
           1&5&10&10&5&1&\dots\\
           \vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots
     \end{array}\right)
  \left(\begin{array}{c}
    n\\ S_1(n-1)\\ S_2(n-1)\\ S_3(n-1)\\ S_4(n-1)\\ \vdots
  \end{array}\right)
\]
Since this matrix of coefficients is triangular, it may be readily
inverted to give
\[ \left(\begin{array}{c}
     n\\ S_1(n-1)\\ S_2(n-1)\\ S_3(n-1)\\ S_4(n-1)\\ \vdots
   \end{array}\right)
   =\left(\begin{array}{cccccc}
          1&0&0&0&0&\dots\\
          -1/2&1/2&0&0&0\\
           1/6&-1/2&1/3&0&0&\dots\\
           0&1/4&-1/2&1/4&0&\dots\\
          -1/30&0&1/3&-1/2&1/5&\dots\\
           \vdots&\vdots&\vdots&\vdots&\vdots&\ddots
     \end{array}\right)
     \left(\begin{array}{c}
       n\\ n^2\\ n^3\\ n^4\\ n^5\\ \vdots
     \end{array}\right).
\]
To obtain the sums to $n$ terms instead of $n-1$ we use $S_r(n)=S_r(n-1)+n^r$,
which has the effect of adding 1\textit{s} to the numbers immediately below the
main diagonal of the matrix, turning each $-1/2$ into $1/2$.  The final result
is then
\[ \left(\begin{array}{c}
     n\\ S_1(n)\\ S_2(n)\\ S_3(n)\\ S_4(n)\\ \vdots
   \end{array}\right)
   =\left(\begin{array}{cccccc}
           1&0&0&0&0&\dots\\
           1/2&1/2&0&0&0&\dots\\
           1/6&1/2&1/3&0&0&\dots\\
           0&1/4&1/2&1/4&0&\dots\\
          -1/30&0&1/3&1/2&1/5\\
           \vdots&\vdots&\vdots&\vdots&\vdots&\ddots
     \end{array}\right)
     \left(\begin{array}{c}
       n\\ n^2\\ n^3\\ n^4\\ n^5\\ \vdots
     \end{array}\right).
\]
The numbers in the first column of this matrix are known as the
``Bernoulli numbers''.

\begin{flushright}
  P.M.L.
\end{flushright}

\end{document}

%