Finite Difference, Discrete MacLaurin, dan Integer-Valued Polynomials
[Pelatihan Tim IMO 2019 Indonesia , Soto Bang Sawit]
Sebuah monomial $M_k(z)=z^k$ dapat kita gunakan dalam expansi Maclaurin-Taylor dari fungsi $f$ sebagai berikut:
\[f(z) = \sum_{k=0}^{\infty} a_k M_k(z) \]
dimana $a_k = \frac{d^k (M_k(z))}{dz}\big\lvert_{z=0}$, yakni merupakan turunan ke-$k$ dari $M_k(z)$ yang dievaluasi di $z=0$.
Sekarang definisikan barisan suku-banyak sebagai berikut:
\[P_0(z)=1 \qquad P_{1}(z)=z \qquad P_2(z)=z(z-1) \qquad P_3(z)=z(z-1)(z-2) \cdots\]
Secara umum definisinya adalah sebagai berikut
\[P_k(z)=z(z-1)\cdots (z-k+1)\]
Untuk "turunan"-nya , kita akan menggunakan finite difference dari fungsi $f$, yakni
\[\Delta f(z) = f(z+1)-f(z) \]
Perhatikan bahwa operator $\Delta (g(z))$ bersifat linear, yakni $\Delta(C \cdot g(z)) = C \cdot \Delta (g(z))$ dan $\Delta (g_1(z)+g_2(z)) = \Delta (g_1(z)) + \Delta (g_2(z))$.
Dengan melakukan finite difference pada suku-banyak $P_k(z)$, kita dapat memperoleh:
\[\Delta P_k(z) = k P_{k-1}(z).\]
Relasi diatas cukup similar dengan rumus turunan $\frac{d}{dz}(M_k(z)) = k M_{k-1}(z)$.
Dengan bekal properti diatas, kita akan mencoba untuk mendapatkan sebuah expansi dari suatu fungsi $f$, yang "analog" dengan expansi Maclaurin-Taylor. (bahkan penurunannya juga mirip.)
Expansi berikut disebut Newton Series:
\[f(z)=\sum_{k=0}^{\infty} a_k P_k(z) = a_0 + a_1 z +a_2 (z)(z-1) + a_3 z(z-1)(z-2)+ \cdots\]
Perhatikan bahwa
\begin{align*}\Delta^2 f(z) &= \Delta ( \Delta f(z) ) \\ &= \Delta ( f(z+1)-f(z)) = (f(z+2)-f(z+1)) - (f(z+1)-f(z)) \\ &= f(z+2) -2f(z+1)+f(z) \end{align*}
\begin{align*}\Delta^3 f(z) &= \Delta (f(z+2) -2f(z+1)-f(z))\\ &= f(z+3)-2f(z+2)+f(z+1) - f(z+2)+2f(z+1)-f(z) \\ &=f(z+3)-2f(z+2)+3f(z+1)-f(z) \end{align*}
Pola koefisien diatas menurut pada koefisien binomial, dan hal ini cukup mudah untuk dibuktikan dengan induksi, yakni
\[\Delta^n (f(z)) = \sum_{k=0}^n (-1)^{n-k}{n \choose k}f(z+k) \]
Untuk $z=0$, kita peroleh
\begin{equation}\Delta^n (f(0)) =\sum_{k=0}^n(-1)^{n-k} {n\choose k} f(k) \qquad \qquad (1) \end{equation}
Sekarang kembali lagi ke Newton Series $f(z)=\sum_{k=0}^n a_k P_k(z)$. Perhatikan bahwa karena $P_k(0)=0$ untuk $k\geq 1$, maka $f(0)=a_0$. Lalu dengan melakukan finite difference ke fungsi $f(z)$, diperoleh
\[\Delta (f(z)) = \sum_{k=0}^{\infty} a_k \Delta P_k(z) = \sum_{k=0}^n a_k \cdot k \cdot P_{k-1}(z) = \sum_{k=1}^{\infty} k a_ k P_{k-1}(z)\]
Sehingga $\Delta (f(0)) = a_1$.
Lebih lanjut diperoleh
\[\Delta^2 (f(z)) = \sum_{k=1}^{\infty} ka_k (k-1) P_{k-2}(z) = \sum_{k=2}^{\infty} ka_k (k-1) P_{k-2}(z).\]
Sehingga $\Delta^2 (f(0)) = 2 a_2$.
Dengan menggunakan induksi dan cara diatas, dapat diperoleh bahwa $\Delta^n(f(0)) = n! a_n$, sehingga
\[f(z)= \sum_{n=0}^{\infty} \frac{\Delta^n(f(0))}{n!} P_n(z) \]
jadi
\[f(z)=\sum_{n=0}^{\infty} \frac{\Delta^n(f(0))}{n!} z(z-1) \cdots (z-n+1) \qquad \qquad (2)\]
voilà!
Untuk kasus khusus ketika $f(z)=c_m z^m + c_{m-1} z^{m-1} + \cdots +c_0$, yang merupakan suku-banyak dengan derajat $m$, maka suku-suku pada expansi diatas harus berhenti, yakni pada pangkat tertinggi dari $f(z)$, sehingga diperoleh
\[f(z)= \sum_{n=0}^m \frac{\Delta^n(f(0))}{n!} z(z-1) \cdots (z-k+1) \]
Dengan menyamakan koefisien dan persamaan (1), kita peroleh
\[m! c_m = \Delta^m (f(0)) = \sum_{k=0}^m (-1)^{m-k} {m \choose k} f(k) \]
dimana $c_m$ adalah koefisien tertinggi dari suku-banyak $f(z)$.
Perlu diketahui juga bahwa himpunan suku-banyak $\{P_k(X)\}_{k \geq 0}$ merupakan himpunan yang bebas linear di $\mathbb{Q}$. Karena jika
\[\alpha_1 P_{k_1}(X)+\cdots + \alpha_m P_{k_m}(X)=0\]
dimana asumsikan $k_1 > k_2 > \cdots > k_n$ dan $\alpha_i \in \mathbb{Q}$, kita peroleh dengan substitusi $t=k_n$, maka diperoleh $P_{k_{j}}(t) = 0$ untuk $j < n$, dan $P_{k_n}(k_n)= (k_n)! \neq 0$, sehingga
\[\alpha_n (k_n)! = 0 \Rightarrow \alpha_n =0\]
apabila dilanjutkan dengan $t=k_{n-1}$, dan seterusnya, maka diperoleh semua $\alpha_i = 0$. Jadi $\{P_k(X)\}_{k \geq 0}$ bebas linear.
Expansi diatas juga dapat memberikan syarat cukup dan perlu untuk sebuat suku banyak $P(X)$ dengan koefisien rational yang memenuhi $P(n) \in \mathbb{Z}$ untuk setiap $n \in \mathbb{Z}$, atau biasa disebut integer-valued polynomials. Contoh $P(n)=\frac{n(n+1)}{2}$.
Sebuah suku-banyak $P(X) \in \mathbb{Q}[X]$ dimana $deg(P(x))=n$ merupakan suku-banyak integer-valued jika dan hanya jika $\Delta^k P(x) \in \mathbb{Z}$ untuk setiap bilangan bulat $k=0,2,..,n$. Jika dan hanya jika \[P(X) = \sum_{j=0}^n a_j {X \choose j} \quad \qquad \text{dimana }a_j \in \mathbb{Z}\]
Buktinya cukup mudah, Jika $P(x)$ integer valued, maka dari rumus $\Delta^n (P(0)) =\sum_{k=0}^n(-1)^{n-k} {n\choose k} P(k)$, kita peroleh $\Delta^n (P(0))$ selalu bilangan bulat. Sebaliknya jika $\Delta^k P(x) \in \mathbb{Z}$ untuk setiap bilangan bulat $k=0,2,..,n$, maka karena ${X \choose j}$ selalu bilangan bulat untuk setiap $j$, diperoleh $P(X) = \sum_{j=0}^n a_j {X \choose j} \quad \qquad \text{dimana }a_j \in \mathbb{Z}$, dengan $a_j = \Delta^j (P(0))$.
Berikut ini adalah salah satu penggunaan identitas (2) pada soal USA TST 2019
Misalkan $\mathbb{Z}/n\mathbb{Z}$ menyatakan himpunan bilangan bulat dalam modulo $n$ (jadi mempunyai $n$ anggota). Tentukan semua bilangan asli $n$ sedemikian sehingga terdapat fungsi bijektif $g: \mathbb{Z}/n \mathbb{z} \rightarrow \mathbb{Z}/n \mathbb{Z}$ sedemikians sehingga 101 buah fungsi
\[g(x) , \quad g(x)+x , \quad g(x)+2x , \quad , \cdots, \quad , g(x)+100x\]
juga merupakan fungsi bijektif.
Solusi berikut merupakan solusi dari Evan Chen. Tapi soal ini sebenarnya tidak begitu susah apabila kita sudah mengetahui rumus penjumlahan $\sum_{k=1}^m k^j$, yang melibatkan bilangan Stirling, dan juga dapat diturunkan dari rumus Newton Series di atas.
Intinya, seperti biasa , dalam mengerjakan soal, kita coba lihat untuk kasus kecil dulu, yakni ketika $l=101$ diganti, misalkan $l=2$ atau $l=3$.
Pada kasus $l=2$ kita ingin fungsi $g(x)$ dan $g(x)+x$ merupakan fungsi bijektif, atau permutasi dari $(1,2,...,n)$. Jadi apabila kita tambahkan diperoleh
\[\sum_{k=1}^n g(k) = \frac{n(n+1)}{2} \qquad \sum_{k=1}^n g(x)+x = \frac{n(n+1)}{2}\]
sehingga diperoleh $\frac{n(n+1)}{2} + \frac{n(n-1)}{2} \equiv \frac{n(n+1)}{2} \pmod n$.
jadi $\frac{n(n+1)}{2} \equiv 0 \pmod n$, sehingga $n$ bilangan ganjil.
Untuk tiga buah fungsi $g(x)$, $g(x)+x$, dan $g(x)+2x$ kita bisa buat menjadi
\[g(x)^2 - 2(g(x)+x)^2 + (g(x)+2x)^2 = 2x^2\]
Sehingga
\begin{align*}\sum_{k=1}^n 2k^2 &= \sum_{k=1}^n g(k)^2 - 2 \sum_{k=1}^n (g(k)+2k)^2 + \sum_{k=1}^n (g(k)+2k)^2\\ &= \sum_{k=1}^nk^2 - 2 \sum_{k=1}^n k^2 + \sum_{k=1}^n k^2 \\ &=0 \end{align*}
Jadi $\frac{(n)(n+1)(2n+1)}{3} \equiv 0 \pmod n$, sehingga disimpulkan $3\nmid n$.
Sebenarnya dapat dilihat bahwa pola yang dibutuhkan adalah membentuk $g(x)$, $g(x)+x$, $g(x)+2x$, ..., $g(x)+kx$ menjadi $k!x^k$. Dan pola ini berdasarkan dua kasus kecil diatas, seperti baris pada segitiga pascal (ganti tanda) yakni: $(1,-1)$ dan $(1,-2,1)$.
Untuk membuktikan pola ini, kita dapat menggunakan rumus (2) diatas pada fungsi $w(k)=x\cdot k + g(x)$, yaitu merupakan fungsi linear dalam variabel $k$. Pertatikan bahwa $w(k)^m$ merupakan suku-banyak dalam $k$ dan berderajat $m$, dengan koefisien tertinggi sama-dengan $x^m$. Jadi apabila kita pakai rumus diatas diperoleh
\[m! x^m = \Delta^m (w(0)^m) = \sum_{k=0}^m (-1)^{m-k} {m \choose k} w(k)^m = \sum_{k=0}^m (-1)^{m-k} {m \choose k} (g(x)+k\cdot x)^m \]
Jadi
\[m! \sum_{x \in \mathbb{Z}/n\mathbb{Z}} x^m \equiv \sum_{k=0}^m (-1)^{m-k} {m \choose k} \left( \sum_{x \in \mathbb{Z}/n\mathbb{Z}}(g(x)+k\cdot x)^m\right) \]
Sedangkan dari hipotesa $(g(x)+k\cdot x)^m$ bijektif kita peroleh
\[\sum_{x \in \mathbb{Z}/n\mathbb{Z}}(g(x)+k\cdot x)^m \equiv 0^m + 1^m + \cdots+ (n-1)^m \equiv l_{n-1}\]
untuk setiap $k$.
Jadi diperoleh
\[m! \sum_{x \in \mathbb{Z}/n\mathbb{Z}} x^m \equiv l_{n-1}\left( \sum_{k=0}^m (-1)^{m-k}{m \choose k}\right) \equiv l_n \cdot 0= 0 \pmod n \]
Relasi diatas berlaku untuk $m=1,2,..., 100$, dapat diperiksa bahwa untuk $k=0$, rumus juga berlaku.
Kita akan buktikan bahwa hal ini menyebabkan $p \nmid n$ untuk setiap bilangan prima $p \leq 101$.
Jika ada bilangan prima $3 \leq p \leq 101$ (karena $p=2$ sudah diperoleh diatas) sehingga $p \lvert n$, asumsikan $p$ prima terkecil yang demikian, dan $v_p(n)=a$. Dengan menggunakan $m=p-1$, diperoleh
\[(p-1)! \sum_{x \in \mathbb{Z}/n\mathbb{Z}} x^{p-1} \equiv 0 \pmod n\]
sehingga dari $(p-1)! \neq 0 \pmod {p^a}$ dan $p^a \lvert n$ diperoleh:
\[p^a \big \lvert \sum_{x \in \mathbb{Z}/n\mathbb{Z}} x^{p-1} \]
Misalkan $S_p \equiv \sum_{x=1}^{p^a} x^{p-1} \pmod {p^a} $, maka
\[\sum_{k=1}^{p^a} (p^a+k)^{p-1} \equiv \sum_{k=1}^{p^a} (2p^a+k)^{p-1} \equiv \cdots \equiv \sum_{k=1}^{p^a} ((n/p^a-1) p^a+k)^{p-1} \equiv S_p \pmod {p^a}\]
Jadi
\[0 \equiv \sum_{x \in \mathbb{Z}/n\mathbb{Z}} x^{p-1} \equiv \frac{n}{p^a} \times S_p \pmod {p^{a}}\]
dan karena $p^a \nmid \frac{n}{p^a}$, diperoleh
\[p^a \big\lvert \sum_{k=1}^{p^a} k^{p-1}\]
Kita akan buktikan ini tidak mungkin untuk $a \geq 1$, yakni dengan menggunakan induksi matematika, kita akan buktikan bahwa $v_{p}\left( \sum_{k=1}^{p^a} k^{p-1}\right)=a-1$.
Jika $a=1$, maka diperoleh $k^{p-1} \equiv 1 \pmod p$, untuk $k \neq p$, sehingga
\[\sum_{k=1}^{p} k^{p-1} \equiv p-1 \not \equiv 0 \pmod p.\]
jadi $v_p\left(\sum_{k=1}^{p} k^{p-1}\right)=0$.
Sekarang misalkan benar untuk suatu $a \geq 1$, kita bisa tulis
\[\sum_{k=1}^{p^a} k^{p-1} = \sum_{(k,p^a) = 1} k^{p-1} + \sum_{k=1}^{p^{a-1}} (k \cdot p)^{p-1}\]
Sekarang misalkan $g$ adalah primitive root dari $\mathbb{Z}/p^a\mathbb{Z}$, kita peroleh $\{x \, : (x,p^a)=1\} = \{1,g, g^2, ..., g^{p^{a-1}(p-1)-1}\}$. Sehingga
\[\sum_{(k,p^a) = 1} k^{p-1} \equiv 1+g^{p-1} + g^{2(p-1)} + \cdots +g^{(p^a(p-1)-1)(p-1)} \equiv \frac{(g^{p-1})^{p^{a-1}(p-1)}-1 }{g^{p-1}-1} \pmod {p^a} \]
Sedangkan karena $p \lvert g^{p-1}-1$, dengan Lifting The Exponent diperoleh
\[v_p((g^{p-1})^{p^{a-1}(p-1)}-1) = v_p(g^{p-1}-1 ) + v_p(p^{a-1}(p-1)) =v_p(g^{p-1}-1 ) + a-1 \]
Jadi
\[v_p \left(\frac{(g^{p-1})^{p^{a-1}(p-1)}-1 }{g^{p-1}-1} \right) = a-1 < a \]
sehingga
\[\sum_{(k,p^a) = 1} k^{p-1} = d_1 \cdot p^{a-1} \]
untuk suatu bilangan $d_1$ yang relatif prima dengan $p$.
Jadi dengan hipotesa induksi
\[\begin{align*}\sum_{k=1}^{p^a} k^{p-1} &= p^{a-1} d_1 + p^{p-1}\left( \sum_{k=1}^{p^{a-1}} k^{p-1} \right) \\ &= p^{a-1} d_1 + p^{p-1} \left(d_2 p^{a-2} \right) \\&= p^{a-1} (d_1 + p^{p-2} d_2)\end{align*}\]
karena $p \nmid d_1 + p^{p-2} d_2$, induksi selesai.
Dengan demikian dapat disimpulkan bahwa tidak ada bilangan prima $p \leq 101$ yang memenuhi $p \lvert n$.
Jadi diperoleh semua bilangan prima yang $\leq 101$ harus tidak membagi $n$. Untuk contoh fungsi yang memenuhi ini, cukup ambil $g(x)=x$. Maka $g(x)+kx$ harus bijective untuk $1 \leq k \leq 100$. Karena jika $x$ dan $y$ memenuhi $g(x)+kx \equiv g(y)+ky \pmod n$, maka diperoleh $(x-y)(k+1) \equiv 0 \pmod n$, yang karena $(k+1,n)=1$, diperoleh $x \equiv y \pmod n$. Selesai.
Soal berikut ini (yang juga ada pada pelatihan) dapat dikerjakan dengan menggunakan syarat cukup dan perlu untuk suku-banyak bernilai bilangan bulat.
Tunjukkan bahwa barisan $(\epsilon_n)_{n \in\mathbb{N}}$ yang bernilai plus-minus satu bersifat periodik dengan periode bilangan $2$ berpangkat, jika dan hanya jika $\epsilon_n = (-1)^{P(n)}$ dimana $P(n)$ adalah suku-banyak dengan koefisien bilangan rasional dan bernilai bilangan bulat untuk setiap bilangan bulat.