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