\documentclass{article}
\usepackage{latexsym,amssymb,amsmath,amsthm}
\textwidth 175mm
\textheight 10in
\oddsidemargin -1cm
\evensidemargin -1cm
\topmargin -2.5cm
\pagestyle{empty}
\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{\p}{\refstepcounter{пункт}%
({\bfseries\theпункт})\ }
\newcommand*{\lk}{\flqq}
\newcommand*{\pk}{\frqq}
\renewcommand*{\le}{\leqslant}
\renewcommand*{\ge}{\geqslant}
\newtheorem*{Lemm}{Lemma}
\begin{document}
\section*{Solutions for \lk Power Sums and Bernoulli Numbers\pk}
Most of the solutions below were known to the jury before~--- but
not all!
Later I hope to choose the best solutions for all problems from the submitted
works~--- that will be in fact the result of the conference.
You are encouraged to ask questions (by email: {\tt dotsenko@mccme.ru}).
\z\p\p The proof is standard. Let us formulate an equivalent question: how many
times does the term $x_1^{a_1}\cdots x_k^{a_k}$ occur in
$(x_1+\dots+x_k)^n$? This number is equal to the number of ways to split
$n$ given brackets into $k$ groups: first group containing $a_1$ brackets,
second one containing $a_2$ of them,\dots, $k$th one containing $a_k$ of
them. Details are left to the reader.
\z\p\p One can easily find a simple combinatorial
interpretation for $[a]^n$ and $[a]_n$ for an integer $a$: for
example, $[a]_n$ is the number of ways to choose
a chairman, a deputy chairman, \dots, a \lk deputy$^{n-1}$ chairman\pk\,
in a committee of $a$ persons.
{\bf Exercise. } Conclude the proof for integers $a,\,b$.
For general $a,b$ use the following fact: a polynomial in $a,b$ vanishes
in all integer points if and only all its coefficients are equal to 0.
\z Hint: show that both ${\binom n k}_q$ and the coefficients of the
left-hand side satisfy the same recurrence relation.
\z\label{a}\p The proof involves a very important method: calculus of
finite differences (see~\cite{FD}). The main idea is very simple: imagine
that you know a polynomial $Q(x)$ such that $Q(1)=0$ (\lk initial
condition\pk) and $Q(x+1)-Q(x)=x^k$. Then $Q(x)=P_k(x)$:
$1^k+2^k+\dots+(n-1)^k=Q(2)-Q(1)+Q(3)-Q(2)+\dots+Q(n)-Q(n-1)=Q(n)$.
Let us show that such a polynomial of degree $k+1$ exists (and is
unique).
Let $Q(x)=q_0+q_1x+\dots+q_kx^k+q_{k+1}x^{k+1}$. Then
$Q(x+1)-Q(x)=(k+1)q_{k+1}
x^k+({\binom {k+1} 2}q_{k+1}+kq_k)x^{k-1}+\dots$, so it is clear
that $q_i$ can be easily found one by one from these equations (such a
situation is called \lk a system of linear equations with an upper triangular
matrix\pk) and the $k+2$-tuple $(q_0,\dots,q_{k+1})$ is unique
(it is determined up to the constant term $q_0$, which is obtained from
the initial condition).
\p
\begin{center}
$P_1(x)=x(x-1)/2, P_2(x)=x(x-1)(2x-1)/6, P_3(x)=x^2(x-1)^2/4,$
$P_4(x)=x(x-1)(2x-1)(3x^2-3x-1)/30, P_5(x)=x^2(x-1)^2(2x^2-2x-1)/12$
\end{center}
\z This immediately
follows from the definition of the Bernoulli numbers.
Let us illustrate how powerful the method of generating functions is.
Let $$\dfrac{ t}{ e^t-1}=\sum_{k\ge0}
\dfrac{{\widehat B}_kt^k}{ k!}.$$
Then it is clear that
$$
t=\sum_{k\ge0}\dfrac{ t^{k+1}}{(k+1)!}\sum_{l\ge0}
\dfrac{{\widehat B}_lt^l}{ l!}=
\sum_{k\ge0}\left(\sum_{i=0}^{k}{\binom{k+1}i}{\widehat B}_i\right)
\dfrac{ t^{k+1}}{(k+1)!},
$$
so ${\widehat B}_k$ and $B_k$ satisfy the same recurrence relation
and initial condition and thus coincide. The rest of the proof is very simple:
the exponential generating function
for the power
sums $S_k(n)$ with fixed $n$ is $$\sum_{k=0}^{n-1}e^{kt}
=\dfrac{ e^{nt}-1}
{ e^t-1}=\dfrac{ e^{nt}-1}{ t}\cdot
\dfrac{ t}{ e^t-1}=\sum_{k\ge0}
\dfrac{ n^{k+1}t^k}{ k!}\sum_{l\ge0}
\dfrac{ B_lt^l}{ l!}=\sum_{k\ge0}
\left(\dfrac1{k+1}\sum_{i=0}^k{\binom {k+1}i}B_in^{k+1-i}\right)\dfrac{t^k}{k!}.$$
\z
\begin{tabular}{c|cccccccccc}
$n$&0&1&2&3&4&5&6&7&8&9\\
\hline
$B_n$&1&$-\dfrac12$&$\dfrac16$&0&$\dfrac{-1}{30}$&0&$\dfrac1{42}$&0
&$\dfrac{-1}{30}$&0\\
\end{tabular}
\begin{tabular}{c|cccccccccccc}
$n$&10&11&12&13&14&15&16&17&18&19&20\\
\hline
$B_n$&$\dfrac{5}{66}$&0&$\dfrac{-691}{2730}$&0&$\dfrac76$&0&$-\dfrac{3617}{510}$&0&
$\dfrac{43867}{798}$&0&$-\dfrac{174611}{330}$\\
\end{tabular}
$$
5, 7, 691, 3617, 43867\,\,\,{\rm are\,\,prime},\,\,\,6=2\cdot3,
\,\,\,
30=2\cdot3\cdot5,\,\,\, 42=2\cdot3\cdot7,\,\,\,
66=2\cdot3\cdot11,\,\,\,2730=2\cdot3\cdot5\cdot7\cdot13,\,\,
$$
$$
510=2\cdot3\cdot5\cdot17,\,\,
798=2\cdot3\cdot7\cdot19,\,\,\,174611=283\cdot617,\,\,\,330=2\cdot3\cdot5\cdot11.
$$
\z
(This solution was suggested by E.~Ferens--Sorotskij, O.~Styrt and O.~Evtifeeva
during the conference; I did not know it before. Other participants
checked that the function $f(t)=\dfrac{ t}{ e^t-1}+
\dfrac{ t}{ 2}$ is even, but the correct explanation meets
some difficulties$\dots$)
Let $k$ be the minimal odd number greater than 1 such that $B_k\ne0$.
$P_k(n)+n^k=P_k(n+1)=P_k(-n)$~--- see solution for {\bf 9(e)} for details.
This means that
$$
\dfrac{1}{k+1}\sum_{i=0}^{k}{\binom{k+1}i}B_i(-n)^{k+1-i}=
\dfrac{1}{k+1}\sum_{i=0}^{k}{\binom{k+1}i}B_in^{k+1-i}+n^k.
$$
By our hypothesis, $B_3=B_5=\dots=B_{k-2}=0$, therefore almost all terms cancel
and we have $n^k+2B_1n^k+2B_kn=0$. Since $B_1=-\dfrac12$, we see that $B_k=0$.
\z
$$
P_1(x)=\dfrac12x^2-\dfrac12x,\,\,\,\,P_2(x)=\dfrac13x^3-\dfrac12x^2+\dfrac16x, \,\,\,\,
P_3(x)=\dfrac14x^4-\dfrac12x^3+\dfrac14x^2,\,\,\,\,P_4(x)=\dfrac15x^5-\dfrac12x^4+\dfrac13x^3-\dfrac1{30}x,
$$
$$
P_5(x)=\dfrac16x^6-\dfrac12x^5+\dfrac5{12}x^4-\dfrac1{12}x^2,\,\,\,
P_6(x)=\dfrac17x^7-\dfrac12x^6+\dfrac12x^5-\dfrac16x^3+\dfrac1{42}x,\,\,\,
P_7(x)=\dfrac18x^8-\dfrac12x^7+\dfrac7{12}x^6-\dfrac7{24}x^4+\dfrac1{12}x^2,
$$
$$
P_8(x)=\dfrac19x^9-\dfrac12x^8+\dfrac23x^7-\dfrac7{15}x^5+\dfrac29x^3-\dfrac1{30}x,\,\,\,
P_9(x)=\dfrac1{10}x^{10}-\dfrac12x^9+\dfrac34x^8-\dfrac7{10}x^6+\dfrac12x^4-\dfrac3{20}x^2,
$$
$$
P_{10}(x)=\dfrac1{11}x^{11}-\dfrac12x^{10}+\dfrac56x^9-x^7+x^5-\dfrac12x^3+
\dfrac5{66}x,\,\,\,
P_{11}(x)=\dfrac1{12}x^{12}-\dfrac12x^{11}+\dfrac{11}{12}x^{10}-\dfrac{11}8x^8+
\dfrac{11}6x^6-\dfrac{11}8x^4+\dfrac5{12}x^2,
$$
$$
P_{12}(x)=\dfrac1{13}x^{13}-\dfrac12x^{12}+x^{11}-\dfrac{11}6x^9+\dfrac{22}7x^7-
\dfrac{33}{10}x^5+\dfrac53x^3-\dfrac{691}{2730}x,
$$
$$
P_{13}(x)=\dfrac1{14}x^{14}-\dfrac12x^{13}+\dfrac{13}{12}x^{12}-
\dfrac{143}{60}x^{10}+\dfrac{143}{28}x^8-\dfrac{143}{20}x^6
+\dfrac{65}{12}x^4-\dfrac{691}{420}x^2,
$$
$$
P_{14}(x)=\dfrac1{15}x^{15}-\dfrac12x^{14}+\dfrac76x^{13}-\dfrac{91}{30}x^{11}+
\dfrac{143}{18}x^9-\dfrac{143}{10}x^7+\dfrac{91}6x^5
-\dfrac{691}{90}x^3+\dfrac76x,
$$
$$
P_{15}(x)=\dfrac1{16}x^{16}-\dfrac12x^{15}+\dfrac54x^{14}-\dfrac{91}{24}x^{12}+
\dfrac{143}{12}x^{10}-\dfrac{429}{16}x^8+
\dfrac{455}{12}x^6-\dfrac{691}{24}x^4+\dfrac{35}4x^2,
$$
$$
P_{16}(x)=\dfrac1{17}x^{17}-\dfrac12x^{16}+\dfrac43x^{15}-\dfrac{14}3x^{13}+
\dfrac{52}3x^{11}-\dfrac{143}3x^9+\dfrac{260}3x^7-
\dfrac{1382}{15}x^5+\dfrac{140}3x^3-\dfrac{3617}{510}x,
$$
$$
P_{17}(x)=\dfrac1{18}x^{18}-\dfrac12x^{17}+\dfrac{17}{12}x^{16}-\dfrac{17}3x^{14}
+\dfrac{221}9x^{12}-\dfrac{2431}{30}x^{10}+\dfrac{1105}{6}x^8
-\dfrac{11747}{45}x^6+\dfrac{595}3x^4-\dfrac{3617}{60}x^2,
$$
$$
P_{18}(x)=\dfrac1{19}x^{19}-\dfrac12x^{18}+\dfrac32x^{17}-\dfrac{34}5x^{15}+
34x^{13}-\dfrac{663}5x^{11}+\dfrac{1105}3x^9-\dfrac{23494}{35}x^7
+714x^5-\dfrac{3617}{10}x^3+\dfrac{43867}{798}x,
$$
\begin{multline*}
P_{19}(x)=\dfrac1{20}x^{20}-\dfrac12x^{19}+\dfrac{19}{12}x^{18}-
\dfrac{323}{40}x^{16}+\dfrac{323}7x^{14}-\dfrac{4199}{20}x^{12}+\\
+\dfrac{4199}6x^{10}-\dfrac{223193}{140}x^8+2261x^6-\dfrac{68723}{40}x^4+
\dfrac{43867}{84}x^2
\end{multline*}
%\end{center}
\z
\p $6P_1(x)P_2(x)=5P_4(x)+P_2(x)$
\p $3P_2(x)P_2(x)=2P_5(x)+P_3(x)$
\p $12P_2(x)P_3(x)=7P_6(x)+5P_4(x)$
\p $2P_3(x)P_3(x)=P_7(x)+P_5(x)$
\p is obvious: denote by $\alpha$ the leading coefficient of the given
polynomial $P(x)$ of degree $k$ and apply the inductive hypothesis to the
polynomial ${\widehat P}(x):=P(x)-\alpha P_{k-1}(x)$ (of degree
less than $k$).
\p\label{b}
(This proof is, as far as I know, due to L.Positselskij. Recently I
found out that the collection of formulae for $P_k(x)$ in~\cite{Lin}
leads to another variant of the following lemma.)
Define an operation $T$ on polynomials by
$(TP)(x):=P(1-x)$. Assign $P_0(x)=x-\dfrac12$ (!!).
\begin{Lemm}
$(TP_k)(x)=(-1)^{k+1}P_k(x)$ for all $k$.
\end{Lemm}
\begin{proof}
It is obvious for $k=0$. Assume that $k>0$.
Recall that $P_k(x+1)-P_k(x)=x^k$, $P_k(1)=0$ (see the solution
for~\ref{a}),
$P_k(0)=0$ (use explicit formula (1)).
This means that $(-1)^{k+1}P_k(-(-x))-(-1)^{k+1}P_k(1-(-x))=(-x)^k$, i.e.,
($y:=-x$) $$y^k=(-1)^{k+1}P_k(-y)-(-1)^{k+1}P_k(1-y)=(-1)^{k+1}(TP_k)(y+1)-
(-1)^{k+1}(TP_k)(y).$$
$(-1)^{k+1}(TP_k)(1)=0$ because $P_k(x)$ vanishes at zero, hence $(-1)^{k+1}TP_k(x)$
satisfies the
same conditions and the
uniqueness of
$P_k$ completes the proof.
\end{proof}
The rest of the proof shows the power of linear algebra.
It is clear that $T(P_kP_l)=T(P_k)T(P_l)=(-1)^{k+l}P_kP_l$.
Let $P_k(x)P_l(x)$ (a polynomial of degree $k+l+2$) have the following
expansion in $P_j$'s: $P_k(x)P_l(x)=\sum\limits_{j=0}^{k+l+1}b_jP_j(x)$. It
follows that $\sum\limits_{j=0}^{k+l+1}
(-1)^{k+l+1}b_jP_j(x)=(-1)^{k+l}P_k(x)P_l(x)=
T(P_kP_l)(x)=\sum\limits_{j=0}^{k+l+1}(-1)^{j+1}b_jP_j(x)$ and since such an
expansion is unique we see that $b_j$ must vanish for
$j\not\equiv k+l+1\pmod{2}$.
(The following solution was submitted by O.~Golberg and M.~Levin
during the conference. It looks like the above solution for {\bf
7}.)
Let us notice that if
$P_k(x)P_l(x)=\sum\limits_{j=0}^{k+l+1}b_jP_j(x)$,
then $P_k(x+1)P_l(x+1)-P_k(x)P_l(x)=\sum\limits_{j=0}^{k+l+1}b_jx^j$.
But $P_k(x+1)=P_k(x)+x^k$, therefore the left-hand side equals
$x^{k+l}+x^kP_l(x)+x^lP_k(x)$. The $x^j$'s coefficients (with $j\equiv
k+l\pmod{2}$, $j to the Bernoulli numbers $B_k$ with odd $k$ and hence
they are equal to zero according to {\bf 7}, and $x^{k+l}$'s coefficient
equals $1+2B_1=0$. Therefore the corresponding $b_j$ are equal to zero.
{\bf Exercise. }(I do not know the complete answer.) Calculate the
coefficients $b_j$ (it is clear that the answer involves Bernoulli
numbers). Therefore the representation for $P_k(x)P_l(x)$ is just a set of
equations on Bernoulli numbers. Write out these equations. Is $\{B_n\}$
the unique sequence satisfying these equations?
\p
$60P_3(x)P_4(x)=27P_8(x)+35P_6(x)-2P_4(x)$.
\z
Let us introduce the notation: for rational $a,\,b$ we write $a\equiv
b\pmod{k}$ ($a$ is congruent to $b$ modulo $k$) if the numerator of $a-b$
is
divisible by $k$. (Most concentrated readers noticed this notation
above$\dots$)
\p Recall the Fundamental Theorem of Arithmetic
(speaking more precisely, this statement is equivalent to the traditional
form of FTA): if integers $a, b\not\equiv 0(p)$ then $ab\not\equiv 0(p)$.
This implies that multiplication by a non-zero remainder modulo $p$
is injective (i.e., maps different remainders into different ones).
Therefore it is obvious that for each non-zero remainder $a$ there exists (a
unique) remainder $b$ such that $ab-1\equiv0(p)$ (there are only
finitely many remainders, so the above means that each of them will occur).
\p\label{bb}
One may use the hint in order to prove the second statement. Let us deal
with the first one. For each $a$ not divisible by $p$ the
remainders of $a, 2a,\dots,(p-1)a$ form the complete system of non-zero
remainders modulo $p$. Hence $1\cdot2\cdots(p-1)(a^{p-1}-1)=
a\cdot2a\cdots(p-1)a-1\cdot2\cdots(p-1)\equiv0(p)$.
Cancel $(p-1)!$ (it is relatively prime to $p$) to conclude the proof.
\z
\p Consider the remainder ${\widehat k}$ of $k$ modulo $p-1$. Then
$a^k-a^{\widehat k}\equiv0(p)$ for all $a$ (it is obvious), so let us
show that $S_{\widehat k}(p)\equiv0(p)$. Let
$b$ be a non-zero remainder such that $b^{\widehat k}-1\not\equiv0(p)$.
Examine $b^{\widehat k}S_{\widehat k}(p)$. Since $b, 2b, \dots (p-1)b$
form the complete system of non-zero remainders, we see that $b^{\widehat
k}S_{\widehat k}(p)-S_{\widehat k}(p)\equiv0(p)$.
To conclude the proof, proceed as above.
\p is a straightforward corollary of {\bf 10(b)}: $a^{l(p-1)}-1$
is divisible by $a^{p-1}-1\equiv0(p)\dots$
{\bf Definition. }Let $p$ be a prime. Let us call a rational number a
$p$-integer if its denominator is not divisible by $p$.
\z
(Here we follow~\cite{NTh}.)
Setting $n=p^r$ in $(1)$, we see that
$$
\dfrac{S_{2k}(p^r)}{p^r}-B_{2k}=\dfrac1{2k+1}\sum_{j=0}^{2k-1}{\binom{2k+1}j}B_j
p^{r(2k-j)}.
$$
If $r$ is large enough the right-hand side (and the left-hand side as
well) is a $p$-integer.
On the other hand for $m\ge 1$
$$
S_{2k}(p^{m+1})=\sum_{u=0}^{p^m-1}\sum_{v=0}^{p-1}(u+vp^m)^{2k}
\equiv p\sum_{u=0}^{p^m-1}u^{2k}+kp^m\sum_uu^{2k-1}\sum_vv\equiv
pS_{2k}(p^m)(p^{m+1}),
$$
and this implies that
$\dfrac{S_{2k}(p^{m+1})}{p^{m+1}}-\dfrac{S_{2k}(p_m)}{p^m}$ is
an integer. Thus $\dfrac{S_{2k}(p)}{p}-B_{2k}$ is a $p$-integer as well. One
may replace $S_{2k}(p)$ by $0$ for $2k\not\equiv0(p-1)$
and $S_{2k}(p)$ by $1$ for $2k\equiv0(p-1)$ to obtain the
following statement (which is just what we need):
For any prime number $q$ \,$B_{2k}+\sum\limits_p\dfrac1p$ is a $q$-integer
(here the summation is taken over primes $p$ such that $2k\equiv0(p-1)$).
Hence this (rational) number is an integer.
\z One may check that $44\equiv0(p-1)$ for a prime $p$ $\Leftrightarrow$
$p\in\{2,3,23\}$. Hence the denominator of $B_{22}$ is 138 and
$B_{22}+\dfrac12+\dfrac13+\dfrac1{23}$
is an integer $\Rightarrow
B_{22}=6193-\dfrac12-\dfrac13-\dfrac1{23}=6193-\dfrac{121}{138}
=\dfrac{854513}{138}$.
\z
Most of the participants used here the following version of the
Dirichlet theorem: there is infinitely many primes having remainder
1 modulo 3.
The proof of this fact is interesting enough to be written
down here.
(Based on the works submitted by M.~Levin, O.~Golberg,
R.~Kralev, D.~Rusev, V.~Dimitrov. This elementary proof is well
known. A.~Entin and D.~Faifman used the quadratic
reciprocity law in their proof.)
Let us prove that for all primes $q$ there exist infinitely many primes
$p$ having remainder 1 modulo $q$ (one may rewrite this proof for a
composite $q$; it is similar, but slightly more technical).
Assume that there are only finitely many such primes: $p_1,\dots,p_k$.
Consider the number
$m=n^{q-1}+n^{q-2}+\dots+n+1=\dfrac{n^q-1}{n-1}$, where $n=2p_1\cdots
p_k$.
Let us notice that the greatest common divisor ($\gcd$) of $n^a-1$ and
$n^b-1$
equals $n^{\gcd(a,b)}-1$ (use Euclid's algorithm).
It follows that $\gcd(m,n^r-1)=\gcd(m,n-1)$ for $01$ ($m=n(p_1-1)\cdots
(p_k-1)$). It is clear that the denominator of
$\dfrac{ B_{2m}}{ 2m}$ is divisible by $p_i$ for
all $i=1,\dots,k$ (use {\bf 12} and {\bf 16}), so its numerator is equal to
$\pm1$ (by our hypothesis, if it is divisible by a prime $p$, then $p$ is
one of $p_i$'s).
This contradicts $\left|\dfrac{ B_{2m}}{ 2m}\right|>1$.
\z
(By I.~Good~(see~\cite{Go}); another proof of the main identity you can
find in~\cite{SF})\footnote{You can find the following proof in~\cite{CM}
as well!!!}
Denote this constant term by $C(a_1,\dots,a_k)$. Let us show that
$C(a_1,\dots,a_k)=C(a_1-1,a_2,\dots,a_k)+\dots+C(a_1,\cdots,a_k-1)$
(there are obvious initial conditions
$C(a_1,\dots,a_{k-1},0)=C(a_1,\dots,a_{k-1})$ and $C(0)=1$). Since multinomial
coefficients satisfy the same recurrence relation and initial condition,
the Dyson's conjecture follows.
The proof is very simple:
consider the polynomial
$f(x)=\sum\limits_{j=1}^n\prod\limits_{i\ne j}\dfrac{ x_i-x}
{ x_i-x_j}$. Its degree is $n-1$ and $f(x_1)=\dots=f(x_n)=1$,
so $f(x)\equiv1$.
Thus $$1=f(0)=\sum_{j=1}^n\prod_{i\ne j}\dfrac{ x_i}
{ x_i-x_j}=\sum_{j=1}^n\prod_{i\ne j}\dfrac{ 1}{
1-\dfrac{ x_j}{ x_i}}.
$$
Multiply
$
\prod\limits_{1\le i\ne j\le n}\left(1-\dfrac{ x_j}
{ x_i}\right)^{a_j}
$
by this equality to obtain the above
recurrence relation.
\z
It is a simple exercise on linear algebra. For any subspace let us write
out all its (ordered) linear bases. To calculate the number of
subspaces, one needs to find out how many bases we have written out and
how many bases span the same subspace. The number of
(ordered) sets of $k$ linearly independent vectors in
$n$-dimensional space over ${\mathbb F}_q$ can be easily
calculated as soon as it is known that this $n$-dimensional space consists
of $q^n$ points (it is obvious: this space is isomorphic to the space of
$n$-tuples ($a_1,\dots,a_n$) with $a_i\in{\mathbb F}_q$): you have $q^n-1$
opportunities to choose the first vector (any non-zero vector),
$q^n-q$ opportunities to choose the second vector (any not from
the subspace spanned by the first vector), $q^n-q^2$ opportunities to
choose the third vector (any not from the subspace spanned by the first
two vectors) etc. Therefore this number equals
$(q^n-1)\cdots(q^n-q^{k-1})=q^{k(k-1)/2}\dfrac{n!_q}{(n-k)!_q}(q-1)^k$.
Proceeding like that, we see that the number of bases that span the same
subspace is $q^{k(k-1)/2}k!_q(q-1)^k$. Hence the number of
subspaces is
$$
\dfrac{q^{k(k-1)/2}\dfrac{n!_q}{(n-k)!_q}(q-1)^k}{q^{k(k-1)/2}k!_q(q-1)^k}=
\dfrac{n!_q}{k!_q(n-k)!_q}={\binom nk}_q.
$$
\z
Denote by $y_{2n+1}^{(i)}$ the sum $\sum\limits_{k\equiv
i\pmod{p-1}}{\binom{2n+1}k}$,
$i=0,1,\dots,p-2$.
Let us prove that these $p-1$ sequences have period modulo $p$.
As we have
$y_{2n+1}^{(i)}=y_{2n-1}^{(i)}+2y_{2n-1}^{(i-1)}+y_{2n-1}^{(i-2)}$
(it is obvious),
it is enough to prove that $y_0^{(i)}\equiv
y_{p}^{(i)}\pmod{p}$ for all $0*0}\binom{2n+1}{k(p-1)}$, which
concludes the proof.
(This solution involves power sums.)
$$
S_{2n+1}(p)=\sum_{i=0}^{p-1}i^{2n+1}\equiv\sum_{j=0}^{p-1}(j+1)^{2n+1}=
\sum_{j=0}^{p-1}\sum_{k=0}^{2n+1}\binom{2n+1}kj^k=p+\sum_{k=1}^{2n+1}
\binom{2n+1}kS_k(p);
$$
proceed according to {\bf 11} to obtain
$$
0\equiv S_{2n+1}(p)\equiv\sum_{k=1}^{p-1}\binom{2n+1}kS_k(p)\equiv
\sum_{k>0}\binom{2n+1}{k(p-1)}\pmod{p},
$$
which is just what we need.
\z
Hint: let $B(x)=\dfrac{t}{e^t-1}+\dfrac{t}2$. Prove the
that $B(x)$ satisfies the following differential equation:
$B^2(x)-B(x)+xB'(x)=\dfrac{x^2}{4}$ and deduce the recurrence relation
from this equation.
\z
All solutions are very straightforward. I prefer the following
solution
submitted by E.~Ferens--Sorotskij, O.~Styrt and O.~Evtifeeva.
It is clear that $f(m,n)=f(n,m)$ and $f(-m,-n)=f(m,n)$.
As
$f(m,n)+f(m,-n)=\sum\limits_{0<2j<2k}\dfrac{1}{m^{2j}n^{2k-2j}}$
(the summands, containing $n^{2j+1}$ for some $j$, cancel,
the ones containing $n^{2j}$ for some $j$, double), we need to prove
that
\begin{multline*}
f(m,n)-f(m,m+n)-f(m+n,n)=f(m,n)+f(m,-n)\Leftrightarrow\\
f(m+n,n)+f(m,m+n)+f(m,-n)=0
\Leftrightarrow \\
f(m+n,n)+f(-m,-m-n)+f(-n,m)=0.
\end{multline*}
Let us prove that for all $a,b,c$ such that $abc\ne0$ and $a+b+c=0$
holds $f(a,-b)+f(b,-c)+f(c,-a)=0$. (And then substitute $a$ by $m+n$, $b$
by $-n$, $c$ by $-m$.) Let us perform some arithmetic transformations
with the formula for $f(m,n)$\,($m\ne n$):
\begin{multline*}
(n-m)f(m,n)=
\dfrac{1}{mn^{2k-2}}-
\dfrac{1}{n^{2k-1}}+\\
\dfrac{1}{m^{2k-1}}-
\dfrac{1}{m^{2k-2}n}+
\dfrac12\sum_{j=2}^{2k-2}\dfrac{1}{m^jn^{2k-j-1}}-
\dfrac12\sum_{j=2}^{2k-2}\dfrac{1}{m^{j-1}n^{2k-j}}=\\
\dfrac{1}{2mn^{2k-2}}-
\dfrac{1}{2m^{2k-2}n}+
\dfrac{1}{m^{2k-1}}-
\dfrac{1}{n^{2k-1}},
\end{multline*}
so
$$
f(m,n)=\dfrac{1}{n-m}\left(
\dfrac{1}{2mn^{2k-2}}-
\dfrac{1}{2m^{2k-2}n}+
\dfrac{1}{m^{2k-1}}-
\dfrac{1}{n^{2k-1}}
\right).
$$
One may easily complete the proof:
$$
f(a,-b)=\dfrac1c\left(
\dfrac{1}{2ab^{2k-2}}+
\dfrac{1}{2a^{2k-2}b}+
\dfrac{1}{a^{2k-1}}+
\dfrac{1}{b^{2k-1}}\right),
$$
$$
f(b,-c)=\dfrac1a\left(
\dfrac{1}{2bc^{2k-2}}+
\dfrac{1}{2b^{2k-2}c}+
\dfrac{1}{b^{2k-1}}+
\dfrac{1}{c^{2k-1}}\right),
$$
$$
f(c,-a)=\dfrac1b\left(
\dfrac{1}{2ca^{2k-2}}+
\dfrac{1}{2c^{2k-2}a}+
\dfrac{1}{c^{2k-1}}+
\dfrac{1}{a^{2k-1}}\right),
$$
\begin{multline*}
f(a,-b)+f(b,-c)+f(c,-a)=\\
\dfrac{1}{a^{2k-2}}\left(
\dfrac{1}{ab}+
\dfrac{1}{bc}+
\dfrac{1}{ca}\right)+
\dfrac{1}{b^{2k-2}}\left(
\dfrac{1}{ab}+
\dfrac{1}{bc}+
\dfrac{1}{ca}\right)+
\dfrac{1}{c^{2k-2}}\left(
\dfrac{1}{ab}+
\dfrac{1}{bc}+
\dfrac{1}{ca}\right)=\\
\left(
\dfrac{1}{a^{2k-2}}+
\dfrac{1}{b^{2k-2}}+
\dfrac{1}{c^{2k-2}}
\right)
\left(
\dfrac{1}{ab}+
\dfrac{1}{bc}+
\dfrac{1}{ca}\right)=\\
\left(
\dfrac{1}{a^{2k-2}}+
\dfrac{1}{b^{2k-2}}+
\dfrac{1}{c^{2k-2}}
\right)
\left(
\dfrac{a+b+c}{abc}\right)=0.
\end{multline*}
\z
Adding up the equalities of the previous problem for all
nonnegative integers $m,n$.
Let us notice that
$$
\sum_{m,n}\dfrac{1}{m^{2j}n^{2k-2j}}=\zeta(2j)\zeta(2k-2j),
$$
$$
\sum_{m,n}f(m,m+n)=\sum_{mn}f(m,n),
$$
therefore
\begin{multline*}
\left(k+\dfrac12\right)\zeta(2k)=\sum_{m=n}f(m,n)=
\sum_{m,n}f(m,n)-\sum_{mn}f(m,n)=\\
\sum_{m,n}\left(f(m,n)-f(m,m+n)-f(m+n,n)\right)=
\sum_{0<2j<2k}\sum_{m,n}\dfrac{1}{m^{2j}n^{2k-2j}}=
\sum_{0<2j<2k}\zeta(2j)\zeta(2k-2j),
\end{multline*}
so
$$
\dfrac{2k-1}{2}\zeta(2k)=\sum_{j=0}^{k}\zeta(2j)\zeta(2k-2j).
$$
Use the recurrence relation from {\bf 22}
to obtain the classical result
$$
\zeta(2k)=(-1)^{k-1}\dfrac{(2\pi)^{2k}B_{2k}}{2(2k)!}.
$$
{\bf Remark. }One may deduce from this formula the inequality which we
used in {\bf 18}.
\z Here you see some explanations.
\begin{itemize}
\item (This explanation leads to some very strange consequences.)
\begin{multline*}
\sum_{k\ge0}\dfrac{B_k}{k!}t^k=\dfrac{t}{e^t-1}=
-t\cdot\dfrac{1}{1-e^t}=
-t\cdot(1+e^t+e^{2t}+\dots)=\\
-t\cdot\left(1+\sum_{n\ge0}\dfrac{t^n}{n!}\sum_{k\ge1}k^n\right)=
-t-\sum_{n\ge1}\dfrac{t^n}{n!}\left(n\sum_{k\ge1}k^{n-1}\right).
\end{multline*}
Let us examine the $t^k$'s coefficients in both sides:
\begin{description}
\item[\rm at $t^n$ ($n>1$):]
$-n\sum_{k_\ge1}k^{n-1}=B_n,$
so $\zeta(1-n)=-\dfrac{B_n}{n}$;
\item[\rm at $t^1$:]
$-\sum_{k\ge1}1-1=-\dfrac12,$
so $\zeta(0)=-\dfrac12$
\item [\rm (at $t^0$:] $1=0$, so$\dots$).
\end{description}
\item
(This explanation was suggested by A.~Entin and D.~Faifman.)
Define Bernoulli polynomials $B_n(x)$ as follows:
$B_n(x)=nP_{n-1}(x)+B_n$. Then $P_{n-1}(x)=
\dfrac{B_n(x)-B_n}{n}$,
$$
k^{n-1}=P_{n-1}(k+1)-P_{n-1}(k)=
\dfrac{B_n(k+1)-B_n}{n}-\dfrac{B_n(k)-B_n}{n}=\dfrac{B_n(k+1)-B_n(k)}{n},
$$
$$
\sum_{k\ge1}k^{n-1}=\dfrac1n\sum_{k\ge1}\left(B_n(k+1)-B_n(k)\right)=
-\dfrac{B_n(1)}{n}=-\dfrac{nP_{n-1}(1)+B_n}{n}=-\dfrac{B_n}{n}.
$$
(Defining Bernoulli polynomials with different constant terms, we
can obtain any answer we want. I suppose that A.~Entin and D.~Faifman
preferred these polynomials becaused they managed to use their Fourier
expansions in {\bf 24}$\dots$)
\item
(The corresponding method of summation is attributed to Abel.)
It is easy to check the following equalities (which involve only formal
power series):
$$
1-2x+3x^2-4x^3+\dots=\dfrac{1}{(1+x)^2},\,\,\,
1^2-2^2x+3^2x^2-4^2x^3+\dots=\dfrac{1-x}{(1+x)^3}.
$$
This means that
\begin{multline*}
1+2+\dots-4(1+2+\dots)=1-2+3-4+\dots=
\left.1-2x+3x^2-4x^3+\dots\right|_{x=1}=
\left.\dfrac{1}{(1+x)^2}\right|_{x=1}=\dfrac14,\\
1^2+2^2+\dots-8(1^2+2^2+\dots)=1^2-2^2+3^2-4^2+\dots=
\left.1^2-2^2x+3^2x^2-4^2x^3+\dots\right|_{x=1}=
\left.\dfrac{1-x}{(1+x)^3}\right|_{x=1}=0,
\end{multline*}
so $1+2+\dots=-\dfrac1{12}$, $1^2+2^2+\dots=0$.
{\bf Exercise. }(Warning: it is not easy.) Proceed this explanation.
\end{itemize}
\z
This text in fact contains solutions for most of the problems on
numerators and denominators of Bernoulli numbers. Unfortunately, nobody
found it during the conference. Compare this solution with the one
in~\cite{PN} (first you need to read the chapter on $p$-adic analysis
there).
Let us denote by $\sigma_{2m}$ an integer such that all numbers
${\displaystyle \dfrac{1}{2m+1}B_kp^{\displaystyle\sigma_{2m}}}$ are
$p$-integer ($0\le k\le
2m-1$). Then
$$
S_{2m}(p^r)-p^rB_{2m}\equiv0\pmod{p^{\displaystyle
2r-\sigma_{2m}}}\eqno(*)
$$.
Let $r$ be large enough, for example, $r>{\rm
max\,}(\sigma_{2m}+2m+N,\sigma_{2n}+2n+N)$.
Consider an integer $a$, which is not divisible by $p$.
For $i=1,\dots,p^r-1$ denote by $b_i(r)$ the remainder of $ia$ modulo
$p^r$:
$ia=b_i(r)+p^rq_i(r)$, $02m$ (it is clear), so
$$
(a^{2m}-1)\dfrac{B_{2m}}{2m}\equiv
\sum_{i=1}^{p^r-1}b_i(r)^{2m-1}q_i(r)\pmod{p^{\displaystyle
r-\sigma_{2m}-2m}}.\eqno(**)
$$
Denote by $\Sigma_{2m}$ the part of the sum in the right-hand side
containing those $b_i(r)$ which are not divisible by $p$.
Let us deal with the remaining summands:
$\sum\limits_{i=1}^{p^{r-1}-1}b_{pi}(r)^{2m-1}q_{pi}(r)$.
Let $c_i=\dfrac{b_{pi}(r)}{p}$
($i=1,\dots,p^{r-1}-1$).
It is clear that $c_i=b_i(r-1)$, $q_{pi}(r)=q_i(r-1)$.
Rewrite (**) with $r:=r-1$:
$$
(a^{2m}-1)\dfrac{B_{2m}}{2m}\equiv
\sum_{i=1}^{p^{r-1}-1}b_i(r-1)^{2m-1}q_i(r-1)
\pmod{p^{\displaystyle
r-1-\sigma_{2m}-2m}}.
$$
It is obvious that
$$
\sum_{i=1}^{p^{r-1}-1}b_i(r-1)^{2m-1}q_i(r-1)=
\sum_{i=1}^{p^{r-1}-1}c_i^{2m-1}q_i(r-1)=
\dfrac{1}{p^{2m-1}}
\sum_{i=1}^{p^{r-1}-1}b_{pi}(r)^{2m-1}q_{pi}(r).
$$
Therefore
$$
p^{2m-1}(a^{2m}-1)\dfrac{B_{2m}}{2m}\equiv
\sum_{i=1}^{p^{r-1}-1}b_{pi}(r)^{2m-1}q_{pi}(r)
\pmod{p^{\displaystyle
r-\sigma_{2m}-2m}}
$$
(use that $2m-1\ge1$).
Substitute this into (**) to obtain
$$
(a^{2m}-1)\dfrac{B_{2m}}{2m}\equiv
\Sigma_{2m}+
\sum_{i=1}^{p^{r-1}-1}b_{pi}(r)^{2m-1}q_{pi}(r)\equiv
\Sigma_{2m}+p^{2m-1}(a^{2m}-1)\dfrac{B_{2m}}{2m}
\pmod{p^{\displaystyle
r-\sigma_{2m}-2m}},
$$
and rewrite this as follows:
$$
(a^{2m}-1)(1-p^{2m-1})\dfrac{B_{2m}}{2m}\equiv
\Sigma_{2m}\pmod{p^{\displaystyle
r-\sigma_{2m}-2m}},
$$
therefore (for $r$ large enough)
$$
(a^{2m}-1)(1-p^{2m-1})\dfrac{B_{2m}}{2m}\equiv \Sigma_{2m}
\pmod{p^{N+1}}
$$
and
$$
(a^{2n}-1)(1-p^{2n-1})\dfrac{B_{2n}}{2n}\equiv \Sigma_{2n}
\pmod{p^{N+1}}.
$$
Since $2m-2n$ is divisible $p^{N+1}-p^N=\varphi(p^{N+1})$, аnd
the numbers $b_i(r)$ (which occur in $\Sigma_{2m}$ and
$\Sigma_{2n}$) are
not
divisible by $p$, it follows that (use Euler's theorem)
$$
(a^{2n}-1)(1-p^{2n-1})\dfrac{B_{2n}}{2n}\equiv
\Sigma_{2n}\equiv\Sigma_{2m}\equiv
(a^{2m}-1)(1-p^{2m-1})\dfrac{B_{2m}}{2m}
\pmod{p^{N+1}},
$$
so (recall that $a$ is not divisible by $p$ as well)
$$
(a^{2n}-1)\left((1-p^{2n-1})\dfrac{B_{2n}}{2n}-
(1-p^{2m-1})\dfrac{B_{2m}}{2m}\right)
\equiv0\pmod{p^{N+1}}.
$$
Choose $a$ such that $a^{2n}-1$ is not divisible by $p$ to complete the
proof
(it is possible because $2n$ is not divisible by $p-1$).
\begin{thebibliography}{XXXX}
\bibitem[BSh]{NTh}
Z.~I.~Borevich, I.~R.~Shafarevich. Number theory.
(In Russian: Moscow, Nauka Publishers, 1985.)
\bibitem[Ge]{FD} A.~O.~Gel'fond. Calculus of finite differences.
(In Russian: Moscow-Leningrad, GITTL, 1952.)
\bibitem[Go]{Go} I.~J.~Good. Short proof of a conjecture of
Dyson. J.~Math.~Phys., 11, 1970.
\bibitem[GKP]{CM} R.~L.~Graham, D.~E.~Knuth, O.~Patashnik. Concrete
mathematics. Addison--Wesley, 1998. (In Russian: Moscow, Mir Publishers,
1998.)
\bibitem[Ko]{PN} N.Koblitz. $P$-adic numbers, $p$-adic analysis and
zeta-functions. Springer--Verlag, 1977.
(In Russian: Moscow, Mir Publishers, 1982.)
\bibitem[Mac]{SF} I.~G.~Macdonald. Symmetric functions and
Hall polynomials. Clarendon Press, Oxford, 1979.
(In Russian: Moscow, Mir Publishers, 1985.)
\bibitem[MS]{CC} J.~W.~Milnor, J.~D.~Stasheff. Characteristic classes.
(In Russian: Moscow, Mir Publishers, 1979.)
\bibitem[Pr]{Lin} V.~V.~Prasolov. Problems and theorems of linear
algebra. (In Russian: Moscow, Nauka Publishers, 1996.)
\end{thebibliography}
\end{document}
*