\documentclass{article}
\usepackage{latexsym,amsmath,amsthm,amssymb}
\textwidth 175mm
\textheight 10in
\oddsidemargin -1cm
\evensidemargin -1cm
\topmargin -2.5cm
\pagestyle{empty}
\newcommand{\lk}{\flqq}
\newcommand{\pk}{\frqq}
\newcounter{§ ¤ ç }
\newcommand{\§ £}[1]{%
\setcounter{§ ¤ ç }{-1}
\par
\vspace{1em plus 1pt}%
\vbox{%
\begin{center}
\large\bfseries #1
\end{center}
}%
\nopagebreak[4]%
}
\newcounter{¯ãªâ}[§ ¤ ç ]
%\renewcommand{\the¯ãªâ}{\ralph{¯ãªâ}}
\renewcommand{\the¯ãªâ}{\alph{¯ãªâ}}
\newcommand{\z}{\par\refstepcounter{§ ¤ ç }%
{\bfseries\the§ ¤ ç .}\ }
\newcommand{\zz}{\par\refstepcounter{§ ¤ ç }%
{\bfseries\the§ ¤ ç $^\diamondsuit$}.\ }
\newcommand{\zzz}{\par\refstepcounter{§ ¤ ç }%
{\bfseries\the§ ¤ ç $^\Box$
}.\ }
\newcommand{\p}{\refstepcounter{¯ãªâ}%
({\bfseries\the¯ãªâ})\ }
\begin{document}
\reversemarginpar
\newcounter{aaa}
\setcounter{aaa}{19}
\newtheorem*{ddef}{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 \lkÈproblems for explorers\pk , you should
certainly turn to another problem.
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}
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 \lk Ars Conjectandi\pkÓ\footnote
{i.e., \lk The Art of Conjecturing\pk. It is one of the first books
on probability theory.}, which contains the following
problem:
{\bf JB 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{ddef}
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{ddef}
\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)$ \lkÈÓ
for less than half quarter of an hour\pk.}
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,
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 $k1$ for large $k$.)
\section*{Power Sums and Bernoulli Numbers: after the semifinal}
\subsection*{More on multinomial coefficients}
Nobody has ever tried to suggest interpretations for \hbox{$\dots$}--nomial coefficients.
The two following problems show very curious interpretations.
\z (Freeman Dyson's conjecture) Let $a_1,\ldots,a_n$ be nonnegative
integers. Prove that the constant term in the $\prod_{1\le i\ne j\le
n}^{}(1-\frac{x_j}{x_i})^{a_j}$ is equal to ${\binom {a_1+\ldots+
a_n}{a_1,\ldots,a_n}}$.
\zz Prove that ${\binom n k}_q$ is equal to the number
of $k$-dimensional subspaces in $n$-dimensional space over finite
field $\mathbb F_q$.
\subsection*{Do you know a solution not drawing on the \lk Power Sums
and \ldots\pkÓ?}
You are encouraged both to find an elementary solution and to suggest your
own problems\ldots
\z (suggested by O.~Golberg and M.~Levin) Let $n$ be an integer
and $p>2$ be a prime. Prove that $\sum\limits_{k>0}^{}{\binom{2n+1}{k(p-1)}}$ is
divisible by $p$. (It is convenient to define ${\binom{n}{k}}=0$ when $n1$):
$$
\sum_{i=0}^{k}{\binom {2k}{2i}}B_{2i}B_{2k-2i}=(1-2k)B_{2k}.
$$
\z Let $f(m,n)$ be the sum $\frac{\displaystyle 1}{\displaystyle mn^{2k-1}}
+\frac{\displaystyle 1}{\displaystyle m^{2k-1}n}+
\frac12\sum\limits_{j=2}^{2k-2}\frac{\displaystyle 1}{\displaystyle m^jn^{2k-j}}$. Prove that $$f(m,n)-f(m+n,n)-
f(m,m+n)=\sum_{0<2j<2k}^{}\frac{1}{m^{2j}n^{2k-2j}}.$$
\z Euler proved that $\sum_{n\ge1}^{}\frac1{n^2}=\frac{\pi^2}{6}$.
Use this result to calculate $\sum_{k\ge1}^{}\frac1{n^{2k}}$ for all integers
$k$. (The answer involves Bernoulli numbers.)
\zz Try to explain the following equalities:
\p $1+2+\ldots=-\frac{1}{12}$
\p $1^2+2^2+\ldots=0$
\p $1^{n-1}+2^{n-1}+\ldots=-\frac{B_n}{n}$ for an integer $n>1$.
\z Suppose that integers $m,
n$ and prime $p$ are such that $2m$ is not divisible by $p-1$ and $2m-2n$ is
divisible by $p^N(p-1)$ for an integer $N$. Prove that the numerator of
$(1-p^{2m-1})\frac{B_{2m}}{2m}-(1-p^{2n-1}) \frac{B_{2n}}{2n}$ is divisible
by $p^{N+1}$. (This means that \lkÓ$p$-adic $\zeta$-function is continuous\pk.)
\end{document}