%comp.tex:
%%a Plain TeX file by Doron Zeilberger (1 page)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
The Composition Enumeration Reciprocity Theorem:
}
\centerline
{
\bf
The Number of Compositions of $n$ Into Parts $k\, ( \, mod \,\, a)$ ($k<a$) Equals 
}
\centerline
{
\bf
The Number of Compositions of $n+a-k$ Into Parts
$a\,(\, mod \,\, k)$ that are $\geq a$
}
\rm
\bigskip
\centerline{ {\it
Doron 
ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg  at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/} .
Feb. 28, 2012.
Supported in part by the NSF.
Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger.
}
}

{\bf Theorem}: See title .

{\bf Proof}: Given a composition $(k+an_1,k+an_2, \dots , k+an_r)$ of $n$, construct the word,
in the {\it alphabet} $\{k,a\}$,
$w:=k a^{n_1}ka^{n_2} \dots  ka^{n_r}$ (whose sum is $n$). Now replace the first letter ($k$) of $w$
by $a$, getting a  word $w':=a a^{n_1}ka^{n_2} \dots  ka^{n_r}$, still in the alphabet $\{k,a\}$ but
whose sum is $n+a-k$, and now parse it as $w'=a k^{m_1} a k^{m_2} \dots a k^{m_s}$ that gives you
the following composition of $n+a-k$ into parts that are $a (mod \,\, k)$ and $\geq a$: 
$$
(a+m_1k , \dots , a+m_sk) \quad . \quad \halmos
$$
{\bf Remark}: The case $k=1,a=2$ (with essentially the same bijective proof) was done in
Drew Sills' nice article {\it Compositions, Parititions, and Fibonacci Numbers}, that appeared
in the {\it Fibonacci Quarterly} {\bf 40} (2011), 348-354, available on-line at \hfill \break
{\tt http://math.georgiasouthern.edu/\~{}asills/comps/CompositionsFQRev.pdf} .

\end
