Deret Harmonik dan Pecahan Mesir

Pecahan berbentuk {\dfrac{1}{n}} dengan {n} bilangan asli kita sebut sebagai pecahan satuan. Apakah penjumlahan sejumlah pecahan satuan yang pertama dapat menghasilkan bilangan bulat? Dengan kata lain, adakah bilangan asli {N} sehingga

\displaystyle H_N:=\frac11+\frac12+\frac13+\frac14+\cdots +\frac{1}{N-1}+\frac{1}{N}

merupakan bilangan bulat?

Ternyata hasilnya negatif, seperti tertulis dalam teorma berikut.

Teorema 1 Untuk setiap bilangan asli {N} bilangan {H_N} tidak pernah merupakan bilangan bulat.

Proof: Andaikan {H_N} merupakan bilangan bulat untuk suatu bilangan asli {N}. Misalkan {k} adalah bilangan asli sehingga {2^k\leq N<2^{k+1}} (mengapa ada {k} yang demikian?). Kalikan {H_N} dengan {2^{k-1}} untuk mendapatkan

    \begin{align*} 2^{k-1}H_N&= 2^{k-1}\left(\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{2^k-1}+\frac{1}{2^k}+\frac{1}{2^k+1}+\cdots +\frac{1}{N}\right)\\ &=\frac{2^{k-1}}{1}+\frac{2^{k-2}}{1}+\frac{2^{k-1}}{3}+\cdots + \frac{2^{k-1}}{2^k-1}+\frac{1}{2}+\frac{2^{k-1}}{2^k+1}+\cdots +\frac{2^{k-1}}{N}. \end{align*}

Pindah ruaskan {2^{k-1}H_N} dan {\frac{1}{2}}, didapat

\displaystyle -\frac12=-\frac{2^{k-1}H_N}{1}+\left(\frac{2^{k-1}}{1}+\frac{2^{k-2}}{1}+\frac{2^{k-1}}{3}+\cdots + \frac{2^{k-1}}{2^k-1}\right)+\left(\frac{2^{k-1}}{2^k+1}+\cdots +\frac{2^{k-1}}{N}\right)

Masing-masing suku disebelah kanan merupakan bilangan rasional dalam bentuk yang paling sederhana dengan penyebut ganjil. Ketika mereka semua kita jumlahkan dan sederhanakan maka tetap diperoleh suatu bilangan rasional {\frac pq} dengan {q} ganjil. Akibatnya tidak mungkin {\frac{p}{q}=-\frac{1}{2}} (kontradiksi!). \Box

Pertanyaan berikutnya adalah bagaimana kalau kita tidak mensyaratkan pecahan satuannya harus berurutan? Apakah bisa kita menyatakan suatu bilangan bulat sebagai jumlahan pecahan-pecahan satuan yang berbeda?

Definisi 2 Suatu bilangan rasional disebut pecahan Mesir jika ia dapat dinyatakan sebagai jumlahan pecahan-pecahan satuan yang berbeda.

Ternyata dapat dibuktikan bahwa tidak hanya ada bilangan bulat yang merupakan pecahan Mesir, tapi lebih kuat dari itu, setiap bilangan rasional positif merupakan pecahan Mesir. Untuk membuktikannya pertama kita perlukan lema berikut.

Lema 3 Misalkan {\frac{p}{q}} bilangan rasional dengan {\frac{1}{s}\leq \frac{p}{q}< \frac{1}{s-1}} untuk suatu bilangan asli {s}. Maka {\frac{p}{q}} merupakan pecahan Mesir.

Proof: Perhatikan bahwa

\displaystyle \frac{p}{q}-\frac{1}{s}=\frac{ps-q}{qs}

Karena {\frac{p}{q}<\frac{1}{s-1}}, maka {p(s-1)<q\Leftrightarrow ps-q<p}. Tulis {p_1=p(s-1)} dan {q_1=qs}, maka {\frac{p}{q}-\frac{1}{s}=\frac{p_1}{q_1}} dengan {p_1<p}. Jika {p_1=0}, maka {\frac{p}{q}=\frac{1}{s}} dan kita selesai. Jika {p_1>0}, maka terdapat bilangan asli {s_1 >s} (mengapa?) sehingga {\frac{1}{s_1}<\frac{p_1}{q_1}<\frac{1}{s_1-1}}. Dengan cara serupa kita dapatkan {\frac{p_1}{q_1}-\frac{1}{s_1}=\frac{p_2}{q_2}} dengan {p>p_1>p_2}. Jika kita lakukan terus menerus maka akan diperoleh barisan bilangan asli yang turun {p>p_1>p_2>\ldots} yang tentunya pada suatu saat kita peroleh {p_{n+1}=0}. Ketika hal ini terjadi maka kita peroleh

\displaystyle \frac{p}{q}-\frac{1}{s}-\frac{1}{s_1}-\cdots -\frac{1}{s_{n}}=\frac{p_{n+1}}{q_{n+1}}=0.

Jadi {\frac{p}{q}} merupakan pecahan mesir. \Box

Sekarang kita siap membuktikan hasil utama kita.

Teorema 4 Setiap bilangan rasional positif merupakan pecahan Mesir.

Proof: Ambil sebarang bilangan rasional positif {\frac{u}{v}}. Ingat bahwa deret harmonik {\displaystyle \sum_{n=1}^\infty \frac{1}{n}} merupakan deret yang divergen. Jika {\displaystyle H_N=\sum_{n=1}^N \frac{1}{n}}, maka terdapat suatu {m} sehingga {H_m\leq \frac{u}{v}<H_{m+1}=H_m+\frac{1}{m+1}}. Akibatnya {0<\frac{u}{v}-H_m<\frac{1}{m+1}<1} dan tentunya terdapat {s>m+1} asli sehingga {\frac{1}{s}\leq \frac{u}{v}-H_m<\frac{1}{s-1}}. Dengan menggunakan lema di atas, kita peroleh

\displaystyle \frac{u}{v}-H_m=\frac{1}{s}+\frac{1}{s_1}+\cdots +\frac{1}{s_n}

dengan {m+1<s<s_1<\cdots<s_n}. Dengan demikian

\displaystyle \frac{u}{v}=H_m+\frac{1}{s}+\frac{1}{s_1}+\cdots+\frac{1}{s_n}

merupakan pecahan Mesir. \Box

PR Strukal dan Teorema Fueter-Polya

Pada PR Struktur Aljabar mahasiswa diminta untuk mengkonstruksi suatu bijeksi f:\mathbb{N}\times \mathbb{N}\to\mathbb{N}.

Mahasiswa diberikan petunjuk bahwa unsur-unsur di \mathbb{N}\times \mathbb{N} dapat disusun ke dalam piramida bilangan sebagai berikut

    \[{\footnotesize     \begin{tabular}{rccccccccc} Baris ke-$1$:\quad\quad&    &    &    &    &  (1,1)\\\noalign{\smallskip\smallskip} Baris ke-$2$:\quad\quad&    &    &    &  (1,2)&    &  (2,1)\\\noalign{\smallskip\smallskip} Baris ke-$3$:\quad\quad&    &    &  (1,3) &    &  (2,2) &    &  (3,1)\\\noalign{\smallskip\smallskip} Baris ke-$4$:\quad\quad&    &  (1,4) &    &  (2,3) &    &  (3,2) &    &  (4,1)\\\noalign{\smallskip\smallskip} Baris ke-$5$:\quad\quad&  (1,5) &    &  (2,4) &    &  (3,3) &    &  (4,2) &    &  (5,1)\\\noalign{\smallskip\smallskip} \end{tabular}  }   \]

dengan aturan bilangan pada baris ke-s berisi semua pasang bilangan (m,n) dengan m+n=s.
Kemudian unsur-unsur di piramidia bilangan tersebut dipetakan ke \mathbb{N} mulai dari baris yang paling atas dan bergerak dari kiri ke kanan. Sebagai contoh f(1,1)=1,f(1,2)=2, f(2,1)=3, f(1,3)=4 dan seterusnya. Mahasiswa diminta untuk menebak rumus eksplisit dari aturan tersebut dan kemudian membuktikan bahwa pemetaan tersebut bijektif.

Setelah saya periksa sepintas, semua pekerjaan mahasiswa yang saya lihat menebak formula pemetaan dengan benar, yaitu f(m,n)=\frac{(m+n-2)(m+n-1)}{2}+m. Kita akan buktikan bahwa f suatu bijeksi. Pertama-tama kita buktikan lema berikut.

Lemma
Notasikan g(k):=\frac{(k-1)k}{2}. Untuk setiap k\in \mathbb{N} berlaku g(k+1)-g(k)=k. Khususnya g(k) monoton naik.
Bukti.
g(k+1)-g(k)=\frac{k}{2}\left((k+1)-(k-1)\right)=k.

Perhatikan bahwa f(m,n)=g(m+n-1)+m dan akan kita tunjukkan bahwa f suatu bijeksi.
Akan kita tunjukkan bahwa f(m,n) injektif. Misalkan (m,n),(a,b)\in \mathbb{N}\times \mathbb{N} sedemikian sehingga f(m,n)=f(a,b). Maka g(m+n-1)+m=g(a+b-1)+a. Andaika m+n\neq a+b dan tanpa mengurangi keumuman misalkan m+n>a+b. Karena g monoton naik maka a-m=g(m+n-1)-g(a+b-1)\geq g(a+b)-g(a+b-1)=a+b-1 (menurut Lema). Ini mengakibatkan -m\geq b-1\geq 0 yang jelas tidak mungkin karena m\in \mathbb{N}. Dengan demikian haruslah m+n=a+b dan akibatnya a-m=g(m+n-1)-g(a+b-1)=0. Jadi a=m dan akibatnya b=n. Jadi f injektif.

Sekarang kita buktikan bahwa f surjektif. Ambil s\in \mathbb{N}. Maka terdapat k\in \mathbb{N} sehingga g(k) < s \leq g(k+1) (mengapa?). Perhatikan bahwa c:=s-g(k)\leq g(k+1)-g(k)=k. Karena c\leq k maka ada d\in \mathbb{N} sehingga c+d-1=k. Sekarang kita dapatkan s=g(k)+c=g(c+d-1)+c=f(c,d). Jadi f surjektif.

Selain polinom f(x,y) di atas, jika kita mendaftarkan unsur-unsur di piramida bilangan dengan urutan dari kanan ke kiri maka kita dapatkan polinom g(x,y)=\frac{1}{2}(x+y-2)(x+y-1)+y yang juga merupakan suatu bijeksi. Polinom f dan g ini dikenal sebagai polinom Cantor, dan Cantor menggunakannya untuk menunjukkan bahwa \mathbb{N}\times \mathbb{N} dan \mathbb{N} mempunyai kardinalitas yang sama.

Terkait dengan kedua polinom ini Cantor menanyakan apakah ada polinom yang lain yang memberikan bijeksi dari \mathbb{N}\times \mathbb{N} ke \mathbb{N}. Fueter dan Polya di tahun 1923 membuktikan teorema berikut.

Teorema Fueter-Polya
Tidak ada Polinom kuadratik lain selain Polinom Cantor yang merupakan bijeksi dari \mathbb{N}\times \mathbb{N}.

Fueter dan Polya membuktikan Teorema di atas dengan menggunakan teknik teori bilangan analitis. Pada tahun 2001 Vserminov memberikan bukti elementer dari Teorema Fueter-Polya di atas.

Paling tidak ada dua hal yang bisa kita pelajari dari Teorema ini. Kita lihat bahwa pembuktian bahwa f merupakan fungsi bijektif merupakan sesuatu yang terlalu sulit yang bahkan masih bisa kita berikan sebagai suatu pekerjaan rumah. Akan tetapi jika kita bersikap kritis dan menanyakan pertanyaan yang tepat, persoalan yang biasa-biasa bisa menjadi objek riset matematika. Dalam hal ini menanyakan apakah ada polinom lain yang memenuhi membuka kesempatan untuk melakukan suatu riset matematika.

Pelajaran kedua yang kita ambil adalah meskipun Fueter dan Polya sudah membuktikan Teorema di atas puluhan tahun yang lalu tidak berarti persoalannya selesai. Dalam matematika kita selalu punya kesempatan untuk memberikan bukti baru dari suatu teorema yang sudah terbukti. Kita bisa menawarkan bukti dari perspektif lain, bukti yang lebih singkat, bukti yang lebih elementer, bukti yang lebih elegan dan sebagainya.

Sedikit demi sedikit kita harus belajar menggeser peran. Kita tidak hanya sekadar menjadi penikmat matematika, dengan mencoba memahami pekerjaan orang lain, tapi juga ikut serta menciptakan matematika. Langkah pertamanya adalah dengan mengajukan banyak pertanyaan terhadap apa yang telah dilakukan orang lain dan berusaha menjawabnya.

Pertanyaan berikutnya yang berkaitan dengan Teorema Fueter-Polya yang alamiah adalah

Apakah ada polinom berderajat lebih dari dua yang merupakan bijeksi dari \mathbb{N}\times \mathbb{N} ke \mathbb{N}?

Para matematikawan meyakini bahwa hanya Polinom Cantor saja yang memenuhi, tapi saat ini belum ada yang bisa memberikan bukti dari konjektur tersebut. Mungkin anda berminat untuk membuktikannya?

Latihan berikut adalah jawaban dari pertanyaan apakah kita bisa mempunyai polinom bijektif seperti di atas untuk dimensi yang lebih tinggi.
Latihan
Berikan polinom yang merupakan bijeksi dari \mathbb{N}\times \mathbb{N}\times \mathbb{N} ke \mathbb{N} dan polinom yang merupakan bijeksi dari \mathbb{N}\times \mathbb{N}\times \mathbb{N} ke \mathbb{N}\times \mathbb{N}

Prima berbentuk p=a^2+b^2.

Dalam tulisan ini akan ditunjukkan jika {p} adalah bilangan prima berbentuk {p=4k+1} jika dan hanya jika {p} dapat dituliskan sebagai penjumlahan dua bilangan kuadrat. Pembuktian di artikel ini akan memanfaatkan sifat bahwa {\mathbb{Z}[i]} merupakan suatu Unique Factorization Domain (UFD).

Pertama kita akan memerlukan teorema Wilson

Theorem 1 (Wilson)

\displaystyle  (p-1)!\equiv -1 {\pmod p}.

Proof: Pertama akan kita tunjukkan bahwa unsur taknol di {\mathbb{Z}_p} yang inversnya adalah dirinya sendiri hanyalah {1} dan {-1}. Jika {x^2=1} di {\mathbb{Z}_p}, maka {(x+1)(x-1)=0} dan karena {\mathbb{Z}_p} lapangan maka {x=1} atau {x=-1}. Dengan demikian semua unsur {1,2,\ldots, p-1} di {\mathbb{Z}_p} dapat dipasang-pasangkan dengan inversnya kecuali 1 dan -1. Dengan demikian {(p-1)!=-1} di {\mathbb{Z}_p}. \Box

Lemma 2 Jika {p=4k+1} maka terdapat {m\in \mathbb{Z}} sehingga {p} membagi {m^2+1}.

Proof: Perhatikan bahwa

\displaystyle  -1=(p-1)!=1\cdot 2\cdots 2k\cdot (-2k)\cdots (-2)= (-1)^{2k}\left(1\cdot 2\cdots 2k\right)^2

di {\mathbb{Z}_p}. Dengan demikian untuk {m=(2k)!} kita peroleh bahwa {p} membagi {m^2+1}. \Box

Theorem 3 (Fermat) Bilangan prima ganjil {p} berbentuk {p=4k+1} jika dan hanya jika terdapat {a,b} sehingga {p=a^2+b^2}.

Proof: Dari lemma di atas kita punyai {p} membagi {m^2+1=(m+i)(m-i)\in \mathbb{Z}[i]}. Perhatikan bahwa {p} tidak membagi baik {m+i} ataupun {m-i} karena jika misalnya {p(c+di)=m+i} maka {pd=1} yang jelas mustahil. Dengan demikian {p} tidak membagi {m+i}. Dengan cara serupa {p} tidak membagi {m-i}. Ini menunjukkan bahwa {p} bukan unsur prima di {\mathbb{Z}[i]}. Karena unsur taktereduksi adalah unsur prima di UFD maka {p} juga bukat unsur taktereduksi. Artinya ada {a+bi, c+di \in \mathbb{Z}[i]} sehingga {(a+bi)(c+di)=p}. Sekarang {N(a+bi)N(c+di)=N(p)=p^2}. Karena {a+bi,c+di} bukan unit maka {N(a+bi)} dan {N(c+di)} tidak sama dengan 1. Jadi haruslah {N(a+bi)=N(c+di)=p}. Akibatnya {a^2+b^2=N(a+bi)=p}.

Sebaliknya misalkan {p=a^2+b^2} untuk suatu bilangan bulat {a,b}. Karena {p} ganjil maka {a,b} tidak mungkin keduanya genap dan juga tidak mungkin keduanya ganjil. Tanpa mengurangi keumuman misalkan {a=2k} dan {b=2l+1}. Akibatnya {p=4k^2+4l^2+4l+1=4(k^2+l^2+l)+1}. \Box