
\documentclass{article}
\usepackage{list,economic,latexsym,amsmath,amsthm,russcorr}
\begin{document}
\reversemarginpar
\newcounter{aaa}
\setcounter{aaa}{19}
\newtheorem*{опр}{Definition}
\newtheorem*{zam}{Remark}
\section*{Power Sums and Bernoulli Numbers}
{
\small
\subsubsection*{A Short Preface/Disclaimer}

The text below shows the connection between two series of problems. First of
them is to find an explicit formula for the sum of $k$th powers of the
first $n$ integers. The answer
here involves one remarkable sequence of rational numbers~--- Bernoulli
numbers. The second series of problems is about number-theoretic
properties
of these numbers.  This sequence is often used by mathematicians who
specialize in number theory, calculus (of real and $p$-adic numbers), algebraic
topology, Lie groups etc.
Therefore the most remarkable properties of this sequence are already
discovered and there is not much hope for something new. Thus the problems
given do not contain some exciting statements which are so new that the jury
is not sure whether they are true etc.
So, if you want to deal with \лк problems for explorers\пк , you should
certainly turn to another problem.

%Dalee idut 2 mesta s raznym upravleniem v identichnoi situacii;
%chto luchshe --- 'marked with' (ya by vse-taki skazal tak) ili 'marked
%by'? I, navernoe, nuzhny artikli?

I use the following notation: the problems which involve strong machinery
which is not well known (such as generating functions), are marked by a
diamond ($^\diamondsuit$).
Standard statements (some of them help you to get acquainted with the
language involved, some are just hints) are marked by a box ($^\Box$).
I think that it is very useful to all participants to prove these
statements themselves (they are not very difficult).
}

\subsection*{Binoms: a Reminder}
% AVB: здесь и далее - в заголовках все слова кроме служебных (артиклей,
% предлогов и пр) - с большой буквы. Собственно, и выше тоже.

Some problems below involve binomial coefficients which show up in
Newton's
binomial theorem. That is why here you see some statements generalizing
this famous result.

{\bf Definition/reminder. }
{\it
Binomial coefficients ${\binom n k}$ are defined for $n,\,k\ge0$
by the equality ${\binom n k}=\frac{n!}{k!(n-k)!}$. In general,
one can define a multinomial coefficient
${\binom n {a_1,\,a_2,\,\ldots,\,a_m}}$ by
${\binom n {a_1,\,a_2,\,\ldots,\,a_m}}=\frac{n!}{a_1!a_2!\ldots a_m!}$
(for $m$-tuples of nonnegative integers $(a_1,\,a_2,\ldots,a_m)$ such
that
$a_1+a_2+\ldots+a_m=n$; it is clear that ${\binom n k}={\binom n
{k,\,n-k}}$).
A $q$\д binomial coefficient
${\binom n k}_q=\frac{n!_q}{k!_q(n-k)!_q}$, where $n!_q=1\cdot(1+q)\cdots
(1+q+\ldots+q^{n-1})$, is another generalization for this notion.
Define Pochhammer symbols as follows:
$[a]_n=a(a-1)\cdots(a-n+1),\,[a]^n=a(a+1)\cdots(a+n-1)$; $[a]_0=[a]^0=1$.
}

\zzz Prove the following identities for all $x_1,\,x_2,\ldots,x_m$:

\p (I.~Newton's binomial theorem.)
$(x_1+x_2)^n=x_1^n+nx_1^{n-1}x_2+\ldots+{\binom n i}x_1^ix_2^{n-i}+
\ldots+x_2^n=\sum_{i=0}^{n}{\binom n i}x_1^ix_2^{n-i}$.

\p (Multinomial theorem.)
$(x_1+x_2+\ldots+x_m)^n=\sum_{a_1,\,a_2,\ldots,a_m}^{}
{\binom n {a_1,\,a_2,\ldots,a_m}}
x_1^{a_1}x_2^{a_2}\cdots x_m^{a_m}$, where the summation is taken over all
multinomial
coefficients with $a_1+\ldots+a_m=n$.

\zzz Prove the following identities for all $a,\,b $ and integer $n\ge0$:

\p $[a+b]_n=\sum_{i=0}^{n}{\binom n i}[a]_i[b]_{n-i}$.

\p $[a+b]^n=\sum_{i=0}^{n}{\binom n i}[a]^i[b]^{n-i}$.

\zzz Prove for all $q,\,z $ and integer $n\ge1$ the identity
$(1+z)(1+qz)\cdots(1+q^{n-1}z)=\sum_{k=0}^{n}{\binom n k}_qz^kq^{k(k-1)/2}$.
(Hence ${\binom n k}_q$ for all $n,\, k$ is a polynomial in $q$,
which might not be obvious at a glance.)

\bigskip
{\bf A question ({\it it is even less obligatory than other problems}). }
Can you suggest other interpretations
for
${\binom n k}$, ${\binom n {a_1,\,a_2,\,\ldots,\,a_n}}$, ${\binom n k}_q$?

\subsection*{Power Sums}

People who know history of mathematics say that Bernoulli numbers
were introduced by Jacob Bernoulli in his
book \лк Ars Conjectandi\пк\footnote
{i.e., \лк The Art of Conjecturing\пк . It is one of the first books
on probability theory.}, which contains the following
problem:

{\bf JB
%\footnote{Jacob Bernoulli}
 problem. }
{\it Denote by $S_k(n)$ the sum $1^k+2^k+\ldots+(n-1)^k$. Find a polynomial
$P_k(x)$ such that $P_k(n)=S_k(n)$ for all $n$.}

\z
\p Prove that for all $k$ there exists such a polynomial $P_k(x)$.

\p Find $P_k(x)$ for $k=1,2,3,4,5$.

Bernoulli found out (when he wrote down a list of $P_k$'s for small $k$)
that coefficients of the polynomials $P_k$
satisfy the following rule: there exists a sequence of numbers
$B_0,\,B_1,\,B_2,\ldots,B_m,\ldots$ such that
\begin{equation}
\label{bern}
S_k(n)=\frac1{k+1}\left(B_0n^{k+1}+{\binom{k+1}1}B_1n^k+\ldots
+{\binom{k+1}k}B_kn \right)
=\frac1{k+1}\sum_{i=0}^k{\binom{k+1}i}B_in^{k+1-i}.
\end{equation}

The proof is not very difficult if the problem is well formulated
(such a situation is quite typical).
\newpage
\begin{опр}
Bernoulli numbers $B_m$ are defined from the recurrence relation
\footnote{The most convenient form of this relation is
$(B+1)^{k+1}=B^{k+1}$ where you should expand the expression in left-hand side
and use the so-called evaluation map: $B^i\mapsto B_i$.
And those readers who worked with generating functions can check that
the exponential generating function for $B_i$ is just
$B(t)=\frac{t}{e^t-1}$.}

\begin{equation}
\label{recc}
\sum_{i=0}^k{\binom{k+1}i}B_i=B_0+{\binom{k+1}1}B_1+\ldots+
{\binom{k+1}i}B_i+\ldots+(k+1)B_k=0
\end{equation}
for $k>0$ and the initial condition $B_0=1$.
\end{опр}

\z Prove that~(\ref{bern}) holds for $B_k$ defined by~(\ref{recc}).

\z Write out the first $20$ Bernoulli numbers.
Decompose their numerators and denominators into primes (hint: the
numerators are
mostly primes, but it is
not true in general~--- see $B_{20}$).

\z Prove that for odd  $n>1\, B_n=0$.


Now one can easily solve the JB problem.

\z Write out polynomials $P_k$ for $k<20$.
\footnote{Bernoulli was proud that he managed to find $S_{10}(1000)$ \лк 
for less than half quarter of an hour\пк .}

%(I mean "for $k<20$", and the
%upper digit is just the footnotemark.)


As soon as you have written out the first 20 of $P_k$'s,
you can think of some formulae which involve these polynomials.
The most obvious is $P_1(x)\cdot P_1(x)=P_3(x)$.
\z Fill the gaps:
\p $6P_1(x)\cdot P_2(x)=\ldots P_4(x)+\ldots P_2(x)$
\,\,\p $3P_2(x)\cdot P_2(x)=\ldots P_5(x)+\ldots P_3(x) $

\p $12P_2(x)\cdot P_3(x)=\ldots P_6(x)+\ldots P_4(x)$
\,\,\p $2P_3(x)\cdot P_3(x)=\ldots P_7(x)+\ldots P_5(x)$

\p Prove that for any polynomial of degree $k$ there exists a unique
representation $a_{-1}+a_0P_0(x)+a_1P_1(x)+\ldots+a_{k-1}P_{k-1}(x)$
with some numbers $a_{-1},\,a_0,\ldots,a_{k-1}$ (which depend on a polynomial).

Now you can state some conjectures. You can even prove some of them\ldots

\p Prove that in such a representation for $P_n(x)P_m(x)$ 
only polynomials $P_l$ with even $m+n+1-l$ occur with non-zero
coefficients.
(Hint: what is the {\it correct} definition for $P_0$?)

\ldots but not all of them\ldots

\p Find such a representation for $P_3(x)P_4(x)$.

\subsection*{Numerators and Denominators}
The following topics in number theory became popular after
E.~Kummer's works in 1850's, who discovered the connection between
the prime divisors of Bernoulli numbers' numerators and the Last
Fermat Theorem\footnote{Employing very strong number-theoretic
machinery,
% AVB employing very strong; 
% 
he proved that the Last Fermat Theorem is true
for primes $p$ such that for any $n$\, $p$ does not occur in the
numerator of $B_{2n}/2n$.
Such primes are called regular. Nobody knows if there are infinitely
many regular primes, although Jensen in 1915 proved that there are
infinitely many primes which are not regular. The first non-regular
prime number is $37$. It occurs in the $B_{32}/32$'s numerator
$7709321041217$.}.
It seems to be one of the main reasons for a very strange behaviour
of those numerators, although there is an explicit formula for the
denominators.

\zzz Let $p$ be a prime number.
\p Prove that remainders modulo $p$ form a field.
(The definitions of addition and multiplication are obvious.
So, you have to prove that for any $a$ which is not divisible by $p$
there exists $b$ such that $ab$ has remainder $1$
modulo $p$ and that different $b$'s satisfying that have equal remainders
modulo $p$.).
\p Prove that for any $a$ which is not divisible by $p$
$a^{p-1}-1$ is divisible by $p$ and that for $k<p-1$ there exists
$b$ which is not divisible by $p$ such that $b^k-1$ is not divisible
by $p$.
(Hint. A polynomial of degree $k$ over any field has no more than $k$ roots.)

\z Prove that: \p $S_k(p)$ is divisible by $p$ unless $k$ is divisible by
$p-1$ \p otherwise $S_k(p)+1$ is divisible by $p$.

\z (Т.~Кlausen ---~C.~von Staudt, 1840) \label{KvS}
$B_{2n}+\sum\limits_p\frac1p$ --- is integral, where the summation is
taken over primes
$p$ such  that $2n$ is divisible by $p-1$.

\z Without drawing on the recurrence relation calculate
$B_{22}$
which is greater than 6192 and less than 6193.

\z Prove that the denominator of $B_{2n}$ is equal to $6$
for infinitely many $n$.

\zz \p Prove that for any integer $n$ $2^{2n}(2^{2n}-1)B_{2n}/2n$ is
an integer.

%(Hint. Use the generating function
%$B(t)$ to calculate power series for $\tg t=\frac{e^{2it}-1}{i(e^{2it}+1)}$
%and work with that series.)

\p Prove that for any integer $a,\,n $ $a^{2n}(a^{2n}-1)B_{2n}/2n$
is an integer.
%(Hint. Find $(log f)'=f'/f$, where $f(t)=\frac{e^{at}-1}{e^t-1}$.)

One can obtain some information (in fact, very very little)
about the Bernoulli numbers' numerators and denominators
from the following problem.

\z (C.~von Staudt, 1845) The denominator of $B_{2n}/n$ is divisible by
a prime $p$ if and only if the denominator of $B_{2n}$ is divisible by
$p$.

\end{document}

 
