Berechenbarkeit/Beta-Funktion/Folgenrepräsentierung/Fakt/Beweis

Beweis

Es sei die endliche Folge ${}(a_{0},a_{1},\ldots ,a_{s})$ vorgegeben. Wir wählen eine Primzahl ${}p$, die größer als alle ${}a_{i}$ und größer als ${}s+1$ ist. Es sei

${}{\begin{aligned}n&:=1\cdot p^{0}+a_{0}p^{1}+2p^{2}+a_{1}p^{3}+\cdots +(s+1)p^{2s}+a_{s}p^{2s+1}\\&=\sum _{i=0}^{s}a_{i}p^{2i+1}+\sum _{i=0}^{s}(i+1)p^{2i}\\&=\sum _{i=0}^{s}(i+1+a_{i}p)p^{2i}.\end{aligned}}$

Die vorgegebene Folge ist also die Folge der Ziffern der ungeraden Stellen in der ${}p$-adischen Ziffernentwicklung von ${}n$. Wir behaupten ${}\beta (p,n,k)=a_{k}$ für ${}k\leq s$. Zunächst erfüllt ${}a_{k}$ die in der Definition der ${}\beta$-Funktion formulierten Eigenschaften, und zwar mit

$b_{0}=1p^{0}+a_{0}p^{1}+2p^{2}+a_{1}p^{3}+\cdots +kp^{2k-2}+a_{k-1}p^{2k-1}\,,$

${}b_{1}=p^{2k}\,,$

$b_{2}=(k+2)+a_{k+1}p+(k+3)p^{2}+\cdots +(s+1)p^{2(s-k)-2}+a_{s}p^{2(s-k)-1}\,.$

Die erste Eigenschaft ergibt sich aus

${}{\begin{aligned}n&=\sum _{i=0}^{s}a_{i}p^{2i+1}+\sum _{i=0}^{s}(i+1)p^{2i}\\&=\sum _{i=0}^{k-1}a_{i}p^{2i+1}+\sum _{i=0}^{k-1}(i+1)p^{2i}+\sum _{i=k}^{s}a_{i}p^{2i+1}+\sum _{i=k}^{s}(i+1)p^{2i}\\&=b_{0}+p^{2k}{\left(\sum _{i=0}^{s-k}a_{k+i}p^{2i+1}+\sum _{i=0}^{s-k}(k+i+1)p^{2i}\right)}\\&=b_{0}+p^{2k}{\left(k+1+a_{k}p+\sum _{i=1}^{s-k}a_{k+i}p^{2i+1}+\sum _{i=1}^{s-k}(k+i+1)p^{2i}\right)}\\&=b_{0}+b_{1}{\left(k+1+a_{k}p+b_{2}p^{2}\right)},\end{aligned}}$

die anderen sind klar. Wenn umgekehrt ein ${}a$ die Bedingungen erfüllt (mit $c_{0},c_{1},c_{2}$), wobei ${}c_{1}=p^{2\ell }$ ist, so ist

${}{\begin{aligned}n&=b_{0}+(k+1)p^{2k}+a_{k}p^{2k+1}+b_{2}p^{2k+2}\\&=c_{0}+(k+1)p^{2\ell }+ap^{2\ell +1}+c_{2}p^{2\ell +2}.\end{aligned}}$

Da die ${}p$-adische Entwicklung von ${}n$ eindeutig ist, folgen daraus und aus den weiteren Bedingungen die Gleichheiten ${}\ell =k$ und ${}a=a_{k}$.

Zur bewiesenen Aussage