Fibonacci sequence. The Fibonacci sequence \((f_n)_{n \in \mathbb{N}}\) is defined by \[f_0=0, \ \ f_1=1,\] \[f_{n}=f_{n-1}+f_{n-2}\quad \text{ for }\quad n \geq 2.\]
Example. \[f_2=0+1=1,\] \[f_3=1+1=2,\] \[f_4=1+2=3,\] \[f_5=2+3=5,\] \[f_6=8, \ \ f_7=13, \ \ f_8=21.\]
Consider \[\begin{aligned} {\color{red}\sum_{n=0}^{\infty}f_n x^n}&=x+\sum_{n=2}^{\infty}(f_{n-1}+f_{n-2})x^n \\& =x+x\sum_{n=2}^{\infty}f_{n-1}x^{n-1}+x^2\sum_{n=2}^{\infty}f_{n-2}x^{n-2}\\& =(x+x^2)\sum_{n=0}^{\infty}f_n x^n+x. \end{aligned}\]
Denoting \({\color{red}F(x)=\sum_{n=0}^{\infty}f_n x^n}\) we have \[F(x)=x+F(x)(x+x^2),\] so \[{\color{red}F(x)}={\color{blue}\frac{x}{1-x-x^2}}.\]
Then \[1-x-x^2=-(x+\phi)(x+\psi),\] where \[\phi=\frac{1+\sqrt{5}}{2}, \quad \psi=\frac{1-\sqrt{5}}{2}.\]
Then \[F(x)=-\frac{x}{(x+\phi)(x+\psi)}=\frac{A}{x+\phi}+\frac{B}{x+\psi},\]
which is equivalent to \[-x=A(x+\psi)+B(x+\phi).\]
Hence \[A=\frac{-\phi}{\sqrt{5}}=\frac{1+\sqrt{5}}{2\sqrt{5}}, \quad B=\frac{\psi}{\sqrt{5}}=\frac{1-\sqrt{5}}{2\sqrt{5}}.\]
So \[{\color{blue}F(x)=\frac{1}{\sqrt{5}}\left(\frac{\psi}{x+\psi}-\frac{\phi}{x+\phi}\right)}.\]
Recall that for \(|x|<1\) we have
\[\frac{1}{1-x}=\sum_{n=0}^{\infty}x^n.\]
Therefore \[\frac{\psi}{x+\psi}=\frac{1}{1+\frac{x}{\psi}}=\frac{1}{1-x\phi}=\sum_{n=0}^{\infty}\phi^n x^n,\] \[\frac{\phi}{x+\phi}=\sum_{n=0}^{\infty}\psi^nx^n.\]
Finally, we have \[\begin{aligned} {\color{red}\sum_{n=0}^{\infty}f_nx^n}&{\color{red}=F(x)}\\&={\color{blue}\frac{x}{1-x-x^2}}=\frac{1}{\sqrt{5}}\left(\frac{\psi}{x+\psi}-\frac{\phi}{x+\phi}\right)\\&=\frac{1}{\sqrt{5}}\left(\sum_{n=0}^{\infty}\phi^n x^n-\sum_{n=0}^{\infty}\psi^nx^2\right)=\sum_{n=0}^{\infty}\frac{1}{\sqrt{5}}(\phi^n-\psi^n)x^n. \end{aligned}\]
Thus the formula for \((f_n)_{n \in \mathbb{N}}\) is given by
\[{\color{brown}f_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)}.\].
Suppose \(a_0, a_1, \ldots, a_n \in \mathbb C\) and \(a_n \neq 0\) with \(n \in \mathbb N\). Let \[P(z) = \sum_{k=0}^n a_kz^k\] then \(P(z)=0\) for some complex number \(z \in \mathbb C\).
Without loss of generality, we assume that \(a_n = 1\) and let \[\mu = \inf_{z \in \mathbb C} |P(z)|.\] If \(|z| = R\), then by the triangle inequality we have \[\begin{aligned} |P(z)| &\geq \big||a_nz^n| - |a_{n-1}z^{n-1}| - \ldots - |a_0|\big|\\ &=R^n \cdot (1 - |a_{n-1}|R^{-1} -\ldots - |a_0|R^{-n}). \end{aligned}\] The right-hand side tends to \(\infty\) as \(R \to \infty\).
Hence, by the definition of divergence, there is \(R_0>0\) such that \[|P(z)| > \mu \quad \text{ if }\quad |z| > R_0.\]
Since \(|P|\) is continuous on the closed circle with center \(0\) and radius \(R_0\), it attains its minimum value at some \(z_0\in \mathbb C\) so that \(|z_0| \leq R_0\).
We claim that \(\mu = 0\). If not, set \(Q(z) = \frac{P(z+z_0)}{P(z_0)}\) then \(Q\) is a nonconstant polynomial with \(Q(0) = 1\) and \[|Q(z)|\geq 1 \quad \text{ for all } \quad z \in \mathbb C.\]
There is a smallest integer \(1 \leq k \leq n\) such that \[Q(z) = 1 + b_kz^k + \ldots + b_nz^n,\qquad b_k \neq 0.\]
Then there is \(\theta \in \mathbb R\) such that \[e^{ik\theta} b_k = -|b_k|.\]
If \(r>0\) and \(r^k|b_k| <1\), then the equation above implies that \[|1+b_k r^k e^{ik\theta}|= |1 - r^k|b_k|| = 1 - r^k|b_k|,\] so that \[|Q(re^{i\theta})| \leq 1 - r^k\{|b_k| - r|b_{k+1}| - \ldots - r^{n-1} |b_n|\}.\]
For sufficiently small \(r\) the expression above in braces is positive. Hence \[|Q(re^{i\theta})| < 1.\] Thus \(\mu = 0\) and \(P(z_0) = 0\).$$\tag*{$\blacksquare$}$$
For \(n\in \mathbb N\), we have \[\begin{aligned} n! = \sqrt{2\pi} n^{n+1/2} e^{-n} e^{r_n}, \end{aligned}\] where \(r_n\) satisfies the double inequality \[\begin{aligned} \frac{1}{12n + 1} < r_n < \frac{1}{12n }. \end{aligned}\]
The usual textbook proofs replace the first inequality above by the weaker inequality \[r_n > 0,\] or \[r_n > \frac{1}{12n + 6}.\]
Let \[S_n = \log(n!) = \sum_{p=1}^{n-1} \log (p+1)\] and write \[\begin{aligned} \log (p+1) = A_p + b_p - \varepsilon_p, \end{aligned}\] where \[\begin{aligned} A_p &= \int_p^{p+1} \log x \, dx, \\ b_p &= [ \log (p+1) - \log p ]/2, \\ \varepsilon_p &= \int_p^{p+1} \log x \, dx - [ \log (p+1) + \log p ]/2. \end{aligned}\]
The partition of \(\log (p+1)\), regarded as the area of a rectangle with base \((p, p+1)\) and height \(\log (p+1)\), into a curvilinear area, a triangle, and a small sliver is suggested by the geometry of the curve \(y = \log x\). Then \[S_n = \sum_{p=1}^{n-1} (A_p + b_p - \varepsilon_p) = \int_1^n \log x \, dx + \frac{1}{2} \log n - \sum_{p=1}^{n-1} \varepsilon_p.\] Since \(\int \log x \, dx = x \log x - x\) we can write \[\begin{aligned} S_n = (n + 1/2) \log n - n + 1 - \sum_{p=1}^{n-1} \varepsilon_p, \end{aligned}\] where \[\varepsilon_p = \frac{2p + 1}{2} \log \Big( \frac{p+1}{p} \Big) - 1.\]
Using the well known series expansions \[\log \Big( \frac{1+x}{1 - x} \Big) = 2 \sum_{k=0}^\infty \frac{x^{2k+1}}{2k+1}\] valid for \(|x| < 1\), and setting \(x = (2p+1)^{-1}\), so that \((1+x)/(1-x) = (p+1)/p\), we find that \[\begin{aligned} \varepsilon_p = \sum_{k=0}^\infty \frac{1}{(2k+3)(2p+1)^{2k+2}}. \end{aligned}\] We can therefore bound \(\varepsilon_p\) above: \[\begin{aligned} \varepsilon_p < \frac{1}{3 (2p+1)^{2}} \sum_{k=0}^\infty \frac{1}{(2p+1)^{2k}} = \frac{1}{12} \Big( \frac{1}{p} - \frac{1}{p+1} \Big), \end{aligned}\]
Similarly, we bound \(\varepsilon_p\) below: \[\begin{aligned} \varepsilon_p > \frac{1}{3 (2p+1)^{2}} \sum_{k=0}^\infty \frac{1}{ [3 (2p+1)^{2} ]^k } &= \frac{1}{3 (2p+1)^{2}} \frac{1}{ 1 - \frac{1}{3 (2p+1)^{2} } }\\ &> \frac{1}{12} \Big( \frac{1}{p + 1/12} - \frac{1}{p+1+ 1/12} \Big). \end{aligned}\]
Now define \[\begin{aligned} B = \sum_{p=1}^\infty \varepsilon_p, \qquad r_n = \sum_{p=n}^\infty \varepsilon_p, \end{aligned}\] where from the lower and upper bound for \(\varepsilon_p\) we have \[\begin{aligned} 1/13 < B < 1/12. \end{aligned}\]
Then we can write \[\begin{aligned} S_n &= (n + 1/2) \log n - n + 1 - \sum_{p=1}^{n-1} \varepsilon_p\\ &= (n+1/2) \log n - n + 1 - B + r_n, \end{aligned}\] or, setting \(C = e^{1-B}\), as \[n! = C n^{n+1/2} e^{-n} e^{r_n},\] where \(r_n\) satisfies \[1/(12n + 1) < r_n < 1/(12n).\] The constant \(C\), lies between \(e^{11/12}\) and \(e^{12/13}\), may be shown to have the value \(\sqrt{2\pi}\). This completes the proof. $$\tag*{$\blacksquare$}$$
A sequence \((a_k)_{k\in\mathbb{N}\cup\{0\}}\subseteq[0, 1]\) is called equidistributed if for any real numbers \(a, b\) with \(0\le a<b\le 1\) one has \[\lim_{N \to \infty} \frac{\#\{k\in[0, N)\cap\mathbb{Z}\colon a_k \in [a, b] \}}{N} = b-a.\]
The following statements are equivalent:
The sequence \((a_k)_{k\in\mathbb{N}\cup\{0\}}\subseteq[0, 1]\) is equidistributed.
For every \(m \in \mathbb{Z}\setminus \{0\}\) we have \[\lim_{N \to \infty} \frac{1}{N} \sum_{k=0}^{N-1} e^{2 \pi i m a_k}= 0.\]
For every continuous function \(f\in C([0, 1], \mathbb{C})\) we have that
\[\begin{aligned} \lim_{N \to \infty} \frac{1}{N} \sum_{k=0}^{N-1} f (a_k) = \int_{0}^1 f(x)dx. \end{aligned}\]
We first prove the equivalence of \((a)\) and \((c)\). Assume that \((c)\) holds, and fix \(0\le a<b\le 1\). Given a sufficiently small \(\varepsilon>0\), we define continuous functions \(f^{-}, f^{+}:[0, 1]\to[0,1]\) that approximate the indicator function \(\mathbf{1}_{{[a, b]}}\) by \[\begin{aligned} f^{+}(x)= \begin{cases} 1 & \text{ if } a\le x\le b;\\ \varepsilon^{-1}(x-(a-\varepsilon))& \text{ if } \max\{0, a-\varepsilon\}\le x<a;\\ \varepsilon^{-1}((b+\varepsilon)-x)& \text{ if } b<x\le \max\{b+\varepsilon, 1\};\\ 0 & \text{ otherwise}, \end{cases} \end{aligned}\] and \[\begin{aligned} f^{-}(x)= \begin{cases} 1 & \text{ if } a+\varepsilon\le x\le b-\varepsilon;\\ \varepsilon^{-1}(x-a)& \text{ if } a\le x<a+\varepsilon;\\ \varepsilon^{-1}(b-x)& \text{ if } b-\varepsilon<x\le b;\\ 0 & \text{ otherwise}. \end{cases} \end{aligned}\]
Notice that \(f^{-}(x)\le \mathbf{1}_{{[a, b]}}(x)\le f^{+}(x)\) for all \(x\in[0, 1]\), and \[\int_0^1(f^{+}(x)-f^{-}(x))dx\le 2\varepsilon.\] It follows that \[\frac{1}{N} \sum_{k=0}^{N-1} f^{-} (a_k)\le \frac{1}{N} \sum_{k=0}^{N-1} \mathbf{1}_{{[a, b]}}(a_k) \le \frac{1}{N} \sum_{k=0}^{N-1} f^{+} (a_k).\] By (c) we have \[\begin{aligned} b-a-2\varepsilon&\le \int_0^1f^{-}(x)dx\le \liminf_{N\to\infty}\frac{1}{N} \sum_{k=0}^{N-1} \mathbf{1}_{{[a, b]}}(a_k)\\ &\le\limsup_{N\to\infty}\frac{1}{N} \sum_{k=0}^{N-1} \mathbf{1}_{{[a, b]}}(a_k) \le \int_0^1f^{+}(x)dx\le b-a+2\varepsilon. \end{aligned}\]
Thus \((a)\) is proved, since \[\liminf_{N\to\infty}\frac{1}{N} \sum_{k=0}^{N-1} \mathbf{1}_{{[a, b]}}(a_k)= \limsup_{N\to\infty}\frac{1}{N} \sum_{k=0}^{N-1} \mathbf{1}_{{[a, b]}}(a_k)=b-a.\] Assume that \((a)\) holds. Given a continuous function \(f\) on \([0, 1]\) and given \(\varepsilon > 0\), we find a step function, i.e. \[g = \sum_{j=1}^m c_j \mathbf{1}_{{I_j}},\] such that \(\|f -g\|_{{\infty}} < \varepsilon/3\), where \(c_j \in \mathbb{C}\) and \(I_j\subseteq[0, 1]\) are intervals. Since \(g\) is a finite linear combination of indicator functions, there is an \(N_0\in \mathbb N\) such that for \(N \ge N_0\) we have \[\Big| \frac{1}{N} \sum_{k=0}^{N-1} g (a_k) - \int_{0}^1 g(x)dx \Big| < \varepsilon/3.\]
Since \[\Big|\int_{0}^1 f(x)dx - \int_{0}^1 g(x)dx\Big| \le \| f -g\|_{{\infty}} < \varepsilon/3\] and \[\Big| \frac{1}{N} \sum_{k=0}^{N-1} g (a_k) - \frac{1}{N} \sum_{k=0}^{N-1} f (a_k) \Big| \le \| f -g\|_{{\infty}} < \varepsilon/3,\] it follows that for \(N \ge N_0\) we have \[\Big| \frac{1}{N} \sum_{k=0}^{N-1} f (a_k) - \int_{0}^1 f(x)dx\Big| < \varepsilon,\] thus \((c)\) holds.
We now prove the equivalence of \((b)\) and \((c)\). In one direction this is clear. To see that \((b)\) implies \((c)\) we fix a continuous function \(f\) on \([0, 1]\). Then for a given \(\varepsilon > 0\) by Weierstrass theorem we pick a trigonometric polynomial \(p\) such that \(\|f-p\|_{\infty}<\varepsilon/3\). Since \[p(x)=\sum_{m=-M}^Mc_me^{2\pi i mx}\] for some \(M\in\mathbb{N}\) and \(c_m\in\mathbb{C}\), then by \((b)\) we have \[\lim_{N\to\infty}\frac{1}{N} \sum_{k=0}^{N-1} p(a_k)=c_0=\int_{0}^1 p(x)dx.\] Hence a \(3\)-epsilon argument completes the proof, as we have \[\qquad\Big| \frac{1}{N} \sum_{k=0}^{N-1} f (a_k) - \int_{0}^1 f(x)dx\Big| < \varepsilon. \qquad \tag*{$\blacksquare$}\]
Example.
The sequence \((\{k \sqrt{2}\})_{k\in\mathbb{N}\cup\{0\}}\) is equidistributed on \([0, 1]\).
We check this by verifying condition \((b)\) of the previous theorem. Indeed if \(m \in \mathbb{Z}\setminus\{0\}\) then \[\lim_{N \to \infty} \frac{1}{N} \sum_{k=0}^{N-1} e^{2\pi i m ( k \sqrt{2} - \lfloor k \sqrt{2} \rfloor )} = \lim_{N \to \infty} \frac{1}{N} \frac{e^{2\pi i N m \sqrt{2} } - 1}{ e^{2\pi i m \sqrt{2} } -1} = 0,\] since \(m \sqrt{2}\in\mathbb{R}\setminus\mathbb{Q}\) thus the denominator never vanishes.
Naturally, the same conclusion is valid for any other irrational number \(\alpha\in\mathbb{R}\setminus\mathbb{Q}\) in place of \(\sqrt{2}\).
We will consider the sequence of the first digits of powers of 2. Namely, for \(m\in\mathbb{N}\) let \[d_m = \text{first digit of $2^m$}.\] For instance we have \(d_1=2\), \(d_2 = 4\), \(d_3 = 8\), \(d_4 =1\), \(d_5 = 3, \ldots\). Here is a list of the first \(20\) powers of \(2\): \[\begin{aligned} 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192,\\ 16384, 32768, 65536, 131072, 262144, 524288, 1048576. \end{aligned}\] The sequence of the first digits of the first 40 powers of \(2\) is: \[\begin{aligned} 2, 4, 8, 1, 3, 6, 1, 2, 5, 1,\\ 2, 4, 8, 1, 3, 6, 1, 2, 5, 1,\\ 2, 4, 8, 1, 3, 6, 1, 2, 5, 1,\\ 2, 4, 8, 1, 3, 6, 1, 2, 5, 1. \end{aligned}\]
Gelfand’s problem.
Do we ever see \(7\) or \(9\)? Gelfand’s question asks: how often do we see a power of \(2\) that starts with \(7\), and with what frequency?
Surprisingly, we will show here that there are infinitely many \(m\in\mathbb{N}\) such that \(2^m\) starts with \(7\) and we even find their frequency.
The existence of this frequency will follow from the uniform distribution of multiples of an irrational number modulo \(1\).
The crucial observation is that the first digit of \(2^m\) is equal to \(k\) if and only if there is a nonnegative integer \(s\) such that \[k 10^s \le 2^m < (k + 1) 10^s.\]
Taking logarithms with base \(10\) we obtain \[s + \log_{10} k \le m \log_{10} 2 < s + \log_{10} (k+1),\] but since \(0 \le \log_{10} k\) and \(\log_{10} (k+1) \le 1\), taking fractional parts we obtain that \[s = \lfloor m \log_{10} 2 \rfloor\] and that \[\begin{aligned} \qquad \log_{10} k \le m \log_{10} 2 - \lfloor m \log_{10} 2 \rfloor < \log_{10} (k+1). \qquad {\color{purple}(*)} \end{aligned}\]
Since the number \(\log_{10} 2\) is irrational, it follows that the sequence \((\{m \log_{10} 2\})_{m\in\mathbb{N}}\) is dense in \([0, 1]\).
Therefore, there are infinitely many \(m\in\mathbb{N}\) such that (*) holds.
We recall that for \(m\in\mathbb{N}\) we consider \[d_m = \text{first digit of $2^m$}.\]
Fix an integer \(1 \le k \le 9\). We will find the frequency in which \(k\) appears as a first digit of \(2^m\), precisely, we would like to find \[\lim_{N \to \infty} \frac{\#\{ m \in \{1, \ldots, N\} : d_m = k \}}{N}.\]
As we mentioned above it is essential that the first digit of \(2^m\) is equal to \(k\) if and only if there is a nonnegative integer \(s\) such that \[k 10^s \le 2^m < (k + 1) 10^s.\]
Taking logarithms with base 10 we obtain \[s + \log_{10} k \le m \log_{10} 2 < s + \log_{10} (k+1).\]
Since \(0 \le \log_{10} k\) and \(\log_{10} (k+1) \le 1\), taking fractional parts we obtain that \[s = \lfloor m \log_{10} 2 \rfloor\] and that \[\log_{10} k \le m \log_{10} 2 - \lfloor m \log_{10} 2 \rfloor < \log_{10} (k+1).\]
Since the number \(\log_{10} 2\) is irrational, the sequence \[\big(\big\{ m \log_{10} 2\big\}\big)_{m\in\mathbb{N}}\] is equidistributed in \([0,1]\). Using \((c)\) from the previous theorem with \([a, b] = [\log_{10} k, \log_{10} (k+1)]\) we obtain that \[\begin{aligned} \lim_{N \to \infty} \frac{\#\{ m \in \{1, \ldots, N\} : d_m = k \}}{N} &= \log_{10} (k+1) - \log_{10} k\\ &= \log_{10} (1 + 1/k). \end{aligned}\]
This gives the frequency in which \(k\) appears as first digit of \(2^m\). Notice that \[\sum_{k=1}^9 \log_{10} (1 + 1/k) = 1,\] as expected.
Moreover, the digit with the highest frequency that appears as the first digit in the decimal expansion of the sequence \((2^m)_{m\in\mathbb{N}}\) is \(1\), while the one with the lowest frequency is \(9\).
A real number is called algebraic if it is a root of a polynomial with integer coefficients. Otherwise a real number is called transcendental.
Remark. Squaring the circle is a problem proposed by ancient geometers. It was the challenge of constructing a square with the same area as a given circle by using only a finite number of steps with compass and straightedge. In 1882, the task was proven to be impossible, as a consequence of the Lindemann–Weierstrass theorem which proves that \(\pi\) is a transcendental, rather than an algebraic irrational number. It had been known for some decades before then that the construction would be impossible if \(\pi\) were transcendental, but \(\pi\) was not proven transcendental until 1882. A bit simpler is to show that \(e\) is transcendental.
The number \[e=\sum_{k\ge0}\frac{1}{k!}\] is transcendental.
If \(e\) were an algebraic number, then we could find a polynomial \(P\) with rational coefficients such that \[P(x)=a_nx^n+\ldots+a_1x+a_0\] satisfying \(P(e)=0\). For every prime number \(p\in\mathbb{P}\) satisfying \(p>n\) and \(p>|a_0|\) we define an auxiliary polynomial by setting \[f_p(x)=\frac{x^{p-1}}{(p-1)!}\prod_{k=1}^n (k-x)^p.\]
We also set \[F_p(x)=f_p(x)+\sum_{j=1}^M f^{(j)}_p(x),\] where \(M=(n+1)p-1\) is the degree of the polynomial \(f_p\). Since \(f^{(M+1)}_p(x)=0\) we obtain \[F_p(x)-F_p'(x)=f_p(x),\] and consequently \[\big(e^{-x}F_p(x)\big)'=-e^{-x}F_p(x)+e^{-x}F_p'(x)=-e^{-x}f_p(x).\] By the mean-value theorem we get \[e^{-x}F_p(x)-F_p(0)=-xe^{-\theta_xx}f_p(\theta_xx)\] for some \(\theta_x\in[0, 1]\). Thus \[F_p(x)-e^xF_p(0)=-xe^{(1-\theta_x)x}f_p(\theta_xx).\]
If \(x\) is fixed and \(p\to\infty\), then \[\lim_{p\to\infty}\big(F_p(x)-e^xF_p(0)\big)=0,\] since for every \(y\in\mathbb{R}\) we have \(\lim_{n\to\infty}\frac{y^n}{n!}=0\). We also obtain \[\begin{aligned} \qquad\lim_{p\to\infty}\sum_{k=0}^na_kF_p(k) =\lim_{p\to\infty}\bigg(\sum_{k=0}^na_kF_p(k)-F_p(0)\sum_{k=0}^na_ke^k\bigg)=0. \qquad {\color{purple}(*)} \end{aligned}\] Since \(j!\) divides all coefficients of \(j\)-th derivative of an arbitrary polynomial we obtain for a suitable polynomials \(P_j\) with integer coefficients that \[f^{(j)}_p(x)=\frac{j!}{(p-1)!}P_j(x).\] Hence we have \[F_p(0)=\sum_{j=p-1}^Mf^{(j)}_p(0)=\frac{1}{(p-1)!}\sum_{j=p-1}^Mj!P_j(0)\equiv P_{p-1}(0)(\bmod{p}),\]
since \(f_p(0)=f_p'(0)=\ldots=f_p^{(p-2)}(0)=0\) and all \(\frac{1}{(p-1)!}\sum_{j=p}^Mj!P_j(0)\in\mathbb{Z}\) and are divisible by \(p\). Similarly, for \(f_p^{(i)}(k)=0\) for \(i\in\{1,\ldots,p-1\}\) and \(k\in\{1,\ldots,n\}\), thus \[F_p(k)=\sum_{j=p}^Mf^{(j)}_p(k)=\frac{1}{(p-1)!}\sum_{j=p}^Mj!P_j(k)\equiv 0(\bmod{p}).\] Finally, \[\sum_{k=0}^na_kF_p(k)\equiv a_0F_p(0)\equiv a_0P_{p-1}(0)\equiv a_0(n!)^p\not\equiv 0(\bmod{p}).\] This contradicts with (*), since a sequence of integers that converges to \(0\) must be constant for all but finitely many terms. This completes the proof of theorem. $$\tag*{$\blacksquare$}$$