Catatan si Jay

November 7, 2010

Algoritma Logaritma

Filed under: Algoritma, Logaritma, Matematika — Hendra Jaya @ 12:17 pm

Referensi

Binary Logarithm

Pra-Pembahasan

Artikel ini akan membahas implementasi teknis tentang algoritma menghitung logaritma. Dimulai dari logaritma basis 2 (binary logarithm) sampai ke basis yang lain. Artikel ini mengasumsikan pembaca sudah memahami sifat-sifat dasar logaritma seperti :

\begin{array}{lll}log_a(a)&=&1\\log_a(a^n)&=&n\\log_a(x^y)&=&y.log_a(x)\\log_a(xy)&=&log_a(x)+log_a(y)\\log_a(\frac{x}{y})&=&log_a(x)-log_a(y)\end{array}

Logaritma dalam basis 2 secara matematis dinyatakan sebagai log_2(x) atau ada pula yang menuliskan lb(x)

Pembahasan

Setiap bilangan real positif x selalu dapat ditulis dalam basis 2 (biner), maka berlaku 2^n\leq x<2^{n+1} dimana n\in\mathbb{Z}.
Perhatikan bahwa persamaan 2^n=x hanya terjadi jika dan hanya jika x adalah bilangan kelipatan 2 (power of two).

Sebagai contoh :

\begin{array}{llcllcrlllr}2^0&\leq&1&<&2^1&\text{artinya}&0&\leq&log_2(1)&<&1\\2^1&\leq&2&<&2^2&\text{artinya}&1&\leq&log_2(2)&<&2\\2^2&\leq&4&<&2^3&\text{artinya}&2&\leq&log_2(4)&<&3\\2^-1&\leq&0.5&<&2^0&\text{artinya}&-1&\leq&log_2(0.5)&<&0\\2^0&\leq&1.414&<&2^1&\text{artinya}&0&\leq&log_2(1.414)&<&1\\2^2&\leq&6.5796&<&2^3&\text{artinya}&2&\leq&log_2(6.5796)&<&3\\2^6&\leq&64&<&2^7&\text{artinya}&6&\leq&log_2(64)&<&7\\2^{-4}&\leq&\frac{1}{16}&<&2^{-3}&\text{artinya}&-4&\leq&log_2(\frac{1}{16})&<&-3\\2^3&\leq&10&<&2^4&\text{artinya}&3&\leq&log_2(10)&<&4\end{array}

Secara sekilas dapat kita lihat bahwa log_2(x) tidak selalu berupa bilangan bulat. Nilai log_2(x) hanya akan bulat, yaitu n, jika dan hanya jika x adalah bilangan kelipatan 2 (power of two). Hal ini senada dengan paragraf sebelumnya.

Namun, untuk log_2(x) yang tidak bulat, maka nilainya pasti berada di rentang n dan n+1.
Atau secara matematis log_2(x)=n+\text{suatu nilai yang tidak bulat}

Contoh lagi :

\begin{array}{lllll}log_2(1)&=&0\\log_2(2)&=&1\\log_2(4)&=&2\\log_2(0.5)&=&-1\\log_2(1.414)&=&0.4997&=&0+0.4997\\log_2(6.5796)&=&2.7179&=&2+0.7179\\log_2(64)&=&6\\log_2(\frac{1}{16})&=&-4\\log_2(10)&=&3.3219&=&3+0.3219\end{array}

Sekarang, melalui aljabar sederhana, kita bisa memperoleh :

\begin{array}{rlclll}2^n&\leq&x&<&2^{n+1}\\1&\leq&2^{-n}.x&<&2&\mbox{Kalikan ketiga bagian dengan }2^{-n}\\log_2(1)&\leq&log_2(2^{-n}.x)&<&log_2(2)&\mbox{Kenakan fungsi }log_2(x)\mbox{ pada ketiga bagian pertidaksamaan}\\ 0&\leq&log_2(2^{-n})+log_2(x)&<&1\\ 0&\leq&-n+log_2(x)&<&1\\ 0&\leq&log_2(y)&<&1&\mbox{Misalkan }log_2(y)=log_2(x)-n\\1&\leq&y&<&2\end{array}

Di dalam bagian terakhir pertidaksamaan kita peroleh 1\leq y<2 dimana log_2(x)=log_2(y)+n

Dari bentuk log_2(x)=log_2(y)+n, pembaca seharusnya dapat memaklumi bahwa n adalah bagian bulat (integer part) dari log_2(x) sedangkan log_2(y) adalah bagian tidak bulat (fractional part). Seperti sudah dijelaskan di beberapa paragraf sebelum ini.

Untuk menghitung bagian yang bulat dapat dilakukan dengan mudah. Yaitu cukup dengan mengalikan/membagi x dengan 2 secara terus menerus sampai diperoleh 1\leq x<2.

Mengingat nilai log_2(1) adalah 0 dan nilai dari log_2(2) adalah 1, maka nilai dari log_2(x) sekarang pasti berupa 0.abcd\ldots Nilai inilah yang dimaksud dengan “bagian tidak bulat”.

Lantas, bagaimana menghitung bagian yang tidak bulat-nya?

Untuk menghitung bagian yang tidak bulat akan kita lakukan trik “mengkuadratkan terus menerus”.

Karena 1\leq y<2, kuadratkan bagian tengah menjadi 1\leq y^2<2

Karena 1\leq y^2<2, kuadratkan bagian tengah menjadi 1\leq y^4<2

Karena 1\leq y^4<2, kuadratkan bagian tengah menjadi 1\leq y^8<2

Berhenti ketika 2\leq y^{2^m}<4.

Triknya cukup mudah dimengerti. Yaitu kuadratkan terus sampai bagian tengah lebih besar atau sama dengan 2.

Intermezzo

Mengapa trik ini dapat dipakai?

Suatu bilangan 1.abcd\ldots jika dikuadratkan berkali-kali pasti akan “berkembang” sehingga pada akhirnya menembus angka 2. Kita tidak tahu berapa kali “pengkuadratan” yang diperlukan. Yang pasti, cepat atau lambat pasti bilangan tersebut akan menembus angka 2.

Sebagai contoh angka 1.001 baru akan menembus 2 pada saat dipangkatkan dengan 694, yakni 1.001^{694}\geq 2.
Di lain pihak, angka 1.2 sudah menempus angka 2 saat dipangkatkan dengan 4, yakni 1.2^4\geq 2.

Mungkinkah bilangan tersebut – ketika menembus angka 2 – juga menembus angka 4?

Ketika menembus angka 2 yang pertama kalinya, bilangan tersebut tidak akan menembus angka 4 karena :

\begin{array}{llllll}1&\leq&x&<&2&\text{Saat ini }x<2\\1^2&\leq&x^2&<&2^2\\1&\leq&x^2&<&4&\text{Saat ini }x^2\geq2\end{array}

Saatnya kembali ke pembahasan algoritma logaritma.

Sekarang, jika kita misalkan z=y^{2^m}, tentu saja berlaku 2\leq z<4. Dengan membagi ketiga bagian pertidaksamaan dengan 2 kita peroleh 1\leq \frac{z}{2}<2

Karena 2\leq y^{2^m}<4 dan z=y^{2^m}, maka :

\begin{array}{rlll}z&=&y^{2^m}\\log_2(z)&=&log_2(y^{2^m})&\text{Kenakan fungsi }log_2(x)\text{ pada kedua sisi}\\log_2(z)&=&2^m.log_2(y)\\log_2(2.\frac{z}{2})&=&2^m.log_2(y)&\text{Identitas perkalian}\\log_2(2)+log_2(\frac{z}{2})&=&2^m.log_2(y)\\1+log_2(\frac{z}{2})&=&2^m.log_2(y)\\2^{-m}.(1+log_2(\frac{z}{2}))&=&log_2(y)&\text{Kalikan kedua sisi dengan } 2^{-m}\\2^{-m}+2^{-m}.log_2(\frac{z}{2})&=&log_2(y)\end{array}

Kita peroleh log_2(y)=2^{-m}+2^{-m}.log_2(\frac{z}{2}). Ingat bahwa sebelumya kita telah mengetahui bahwa 1\leq \frac{z}{2}<2, sehingga trik yang sama dapat kita lakukan :

Dengan meng-kuadratkan \frac{z}{2} secukupnya, kita peroleh 2\leq \frac{z}{2}^{2^n}<4

Misalkan w=\frac{z}{2}^{2^n}, maka 2\leq w<4 atau 1\leq \frac{w}{2}<2

\begin{array}{rll}w&=&\frac{z}{2}^{2^n}\\log_2(w)&=&log_2(\frac{z}{2}^{2^n})\\log_2(w)&=&2^n.log_2(\frac{z}{2})\\log_2(2.\frac{w}{2})&=&2^n.log_2(\frac{z}{2})\\log_2(2)+log_2(\frac{w}{2})&=&2^n.log_2(\frac{z}{2})\\1+log_2(\frac{w}{2})&=&2^n.log_2(\frac{z}{2})\\2^{-n}.(1+log_2(\frac{w}{2}))&=&log_2(\frac{z}{2})\\2^{-n}+2^{-n}.log_2(\frac{w}{2})&=&log_2(\frac{z}{2})\end{array}

Dengan men-substitusikan log_2(\frac{z}{2}), kita peroleh :

log_2(y)=2^{-m}+2^{-m}.(2^{-n}+2^{-n}.log_2(\frac{w}{2}))

Dengan teknik yang sama, kita peroleh log_2(\frac{w}{2})=2^{-o}+2^{-o}.log_2(\frac{v}{2}).

Lalu di-substitusikan menjadi :

log_2(y)=2^{-m}+2^{-m}.(2^{-n}+2^{-n}.(2^{-o}+2^{-o}.log_2(\frac{v}{2})))

Dan seterusnya…

Sehingga bentuk umum-nya dapat dituliskan sebagai : log_2(y)=2^{-m}+2^{-m}.(2^{-n}+2^{-n}.(2^{-o}+2^{-o}(\ldots)))

atau ekivalen dengan : log_2(y)=2^{-m}+2^{-m-n}+2^{-m-n-o}+\ldots

atau jika ditulis ke dalam bentuk yang lebih seragam : log_2(y)=2^{-m_1}+2^{-m_1-m_2}+2^{-m_1-m_2-m_3}+\ldots

Sampai disini kita telah dapat menghitung bagian tidak bulat (fractional part) dari log_2(x).
Dengan menggabungkan bagian bulatnya kita peroleh log_2(x)=n+2^{-m_1}+2^{-m_1-m_2}+2^{-m_1-m_2-m_3}+\ldots

Dimana :

x adalah sembarang bilangan real positif, x>0 dan x\in\mathbb{R}
n adalah bagian bulat dari log_2(x)
2^{-m_1}+2^{-m_1-m_2}+2^{-m_1-m_2-m_3}+\ldots adalah bagian tidak bulat dari log_2(x)
Galat dari algoritma ini sangat kecil. Yaitu kurang dari 2^{-(m_1+m_2+m_3+\ldots+m_i)}

Untuk mencari logaritma dalam basis lain dapat menggunakan invarian log_a(b)=\frac{log_2(b)}{log_2(a)}

Pseudo-Code Algoritma log_2(x) :

  1. Asumsikan bahwa kondisi x>0 terpenuhi
  2. Tentukan batas toleransi kesalahan, err, secukupnya.
  3. Bagian bulat :
    1. Ambil a=0
    2. Periksa salah satu rentang nilai yang memenuhi x :
      1. Jika x memenuhi x<1 : lanjut ke langkah 3.3
      2. Jika x memenuhi 1\leq x<2 : lompat ke langkah 4
      3. Jika x memenuhi x\geq 2 : lanjut ke langkah 3.4
    3. Lakukan :
      1. Kali x dengan 2
      2. Kurangi a dengan 1
      3. Periksa apakah kondisi x<1 masih terpenuhi.
        1. Jika masih terpenuhi, kembali ke langkah 3.3
        2. Jika sudah tidak terpenuhi, lompat ke langkah 4
    4. Lakukan :
      1. Bagi x dengan 2
      2. Tambahkan a dengan 1
      3. Periksa apakah kondisi x\geq 2 masih terpenuhi.
        1. Jika masih terpenuhi, kembali ke langkah 3.4
        2. Jika sudah tidak terpenuhi, lompat ke langkah 4
  4. Bagian tidak bulat :
    1. Ambil b=1
    2. Periksa apakah kondisi b>err terpenuhi.
      1. Jika terpenuhi : lanjut ke langkah 4.3
      2. Jika tidak terpenuhi : lompat ke langkah 5
    3. Periksa apakah kondisi 1\leq x<2 terpenuhi.
      1. Jika terpenuhi :
        1. Kuadratkan x
        2. Bagi b oleh 2
        3. Kembali ke langkah 4.2
      2. Jika tidak terpenuhi :
        1. Bagi x oleh 2
        2. Tambahkan a dengan b
        3. Kembali ke langkah 4.2
  5. Hasil akhir algoritma adalah a

Berikut penulis sajikan pseudo-code yang lebih formal :

Pseudo Code Binary Logarithm

Implementasi

Java : Ideone, PDF
C++ : Sabar subur
Python : Logarithm Function

Contoh eksekusi algoritma :

1. Contoh menghitung log_2(0.3)

Nilai x=0.3

Ambil err=10^{-2}=0.01

Periksa rentang :

\begin{array}{rr}\mbox{[TRUE]}&0<0.3<1\\\mbox{[FALSE]}&1\leq 0.3<2\\\mbox{[FALSE]}&2\leq 0.3\end{array}

Menghitung bagian bulat

Nilai a=0

\begin{array}{rrrllll}\mbox{[TRUE]}&0<0.3<1&x&=&2.(0.3)&=&0.6\\&&a&=&0-1&=&-1\\\\\mbox{[TRUE]}&0<0.6<1&x&=&2.(0.6)&=&1.2\\&&a&=&-1-1&=&-2\\\\\mbox{[FALSE]}&0<1.2<1\end{array}

Menghitung bagian tidak bulat

Nilai b=1

\begin{array}{rrrllll}\mbox{[FALSE]}&2\leq 1<4\\\mbox{[TRUE]}&1>0.01&x&=&1.2^2&=&1.44\\&&b&=&\frac{1}{2}&=&0.5\\\\\mbox{[FALSE]}&2\leq 1.44<4\\\mbox{[TRUE]}&0.5>0.01&x&=&1.44^2&=&2.0736\\&&b&=&\frac{0.5}{2}&=&0.25\\\\\mbox{[TRUE]}&2\leq 2.0736<4&x&=&\frac{2.0736}{2}&=&1.0368\\&&a&=&-2+0.25&=&-1.75\\\mbox{[TRUE]}&0.25>0.01&x&=&1.0368^2&=&1.0749542\\&&b&=&\frac{0.25}{2}&=&0.125\\\\\mbox{[FALSE]}&2\leq 1.0749542<4\\\mbox{[TRUE]}&0.125>0.01&x&=&1.0749542^2&=&1.1555266\\&&b&=&\frac{0.125}{2}&=&0.0625\\\\\mbox{[FALSE]}&2\leq 1.1555266<4\\\mbox{[TRUE]}&0.0625>0.01&x&=&1.1555266^2&=&1.3352417\\&&b&=&\frac{0.0625}{2}&=&0.03125\\\\\mbox{[FALSE]}&2\leq 1.3352417<4\\\mbox{[TRUE]}&0.03125>0.01&x&=&1.3352417^2&=&1.7828705\\&&b&=&\frac{0.0625}{2}&=&0.015625\\\\\mbox{[FALSE]}&2\leq 1.7828705<4\\\mbox{[TRUE]}&0.015625>0.01&x&=&1.7828705^2&=&3.1786274\\&&b&=&\frac{0.015625}{2}&=&0.0078125\\\\\mbox{[TRUE]}&2\leq 3.1786274<4&x&=&\frac{3.1786274}{2}&=&1.5893137\\&&a&=&-1.75+0.0078125&=&-1.7421875\\\mbox{[FALSE][STOP]}&0.0078125>0.01\end{array}

Hasil akhir

Dengan demikian log_2(0.3)\approx -1.7421875

2. Contoh menghitung log_2(1.4)

Nilai x=1.4

Ambil err=10^{-2}=0.01

Periksa rentang :

\begin{array}{rr}\text{[FALSE]}&0<1.4<1\\\text{[TRUE]}&1\leq 1.4<2\\\text{[FALSE]}&2\leq 1.4\end{array}

Menghitung bagian bulat

Nilai a=0

Menghitung bagian tidak bulat

Nilai b=1

\begin{array}{rrrllll}\text{[FALSE]}&2\leq 1<4\\\text{[TRUE]}&1>0.01&x&=&1.4^2&=&1.96\\&&b&=&\frac{1}{2}&=&0.5\\\\\text{[FALSE]}&2\leq 1.96<4\\\text{[TRUE]}&0.5>0.01&x&=&1.96^2&=&3.8416\\&&b&=&\frac{0.5}{2}&=&0.25\\\\\text{[TRUE]}&2\leq 3.8416<4&x&=&\frac{3.8416}{2}&=&1.9208\\&&a&=&0+0.25&=&0.25\\\text{[TRUE]}&0.25>0.01&x&=&1.9208^2&=&3.6894726\\&&b&=&\frac{0.25}{2}&=&0.125\\\\\text{[TRUE]}&2\leq 3.6894726<4&x&=&\frac{3.6894726}{2}&=&1.8447363\\&&a&=&0.25+0.125&=&0.375\\\text{[TRUE]}&0.125>0.01&x&=&1.8447363^2&=&3.403052\\&&b&=&\frac{0.125}{2}&=&0.0625\\\\\text{[TRUE]}&2\leq 3.403052<4&x&=&\frac{3.403052}{2}&=&1.701526\\&&a&=&0.375+0.0625&=&0.4375\\\text{[TRUE]}&0.0625>0.01&x&=&1.701526^2&=&2.8951908\\&&b&=&\frac{0.0625}{2}&=&0.03125\\\\\text{[TRUE]}&2\leq 2.8951908<4&x&=&\frac{2.8951908}{2}&=&1.4475954\\&&a&=&0.4375+0.03125&=&0.46875\\\text{[TRUE]}&0.03125>0.01&x&=&1.4475954^2&=&2.0955325\\&&b&=&\frac{0.0625}{2}&=&0.015625\\\\\text{[TRUE]}&2\leq 2.0955325<4&x&=&\frac{2.0955325}{2}&=&1.0477662\\&&a&=&0.46875+0.015625&=&0.484375\\\text{[TRUE]}&0.015625>0.01&x&=&1.0477662^2&=&1.0978141\\&&b&=&\frac{0.015625}{2}&=&0.0078125\\\\\text{[FALSE]}&2\leq 1.0978141<4\\\text{[FALSE][STOP]}&0.0078125>0.01\end{array}

Hasil akhir

Dengan demikian log_2(1.4)\approx 0.484375

3. Contoh menghitung log_2(11)

Nilai x=11

Ambil err=10^{-2}=0.01

Periksa rentang :

\begin{array}{rr}\text{[FALSE]}&0<11<1\\\text{[FALSE]}&1\leq 11<2\\\text{[TRUE]}&2\leq 11\end{array}

Menghitung bagian bulat :

Nilai a=0

\begin{array}{rrrllll}\text{[TRUE]}&11\geq 2&x&=&\frac{11}{2}&=&5.5\\&&a&=&0+1&=&1\\\\\text{[TRUE]}&5.5\geq 2&x&=&\frac{5.5}{2}&=&2.75\\&&a&=&1+1&=&2\\\\\text{[TRUE]}&2.75\geq 2&x&=&\frac{2.75}{2}&=&1.375\\&&a&=&2+1&=&3\\\\\text{[FALSE]}&1.375\geq 2\end{array}

Menghitung bagian tidak bulat :

Nilai b=1

\begin{array}{rrrllll}\text{[FALSE]}&2\leq 1<4\\\text{[TRUE]}&1>0.01&x&=&1.375^2&=&1.890625\\&&b&=&\frac{1}{2}&=&0.5\\\\\text{[FALSE]}&2\leq 1.890625<4\\\text{[TRUE]}&0.5>0.01&x&=&1.890625^2&=&3.5744628\\&&b&=&\frac{0.5}{2}&=&0.25\\\\\text{[TRUE]}&2\leq 3.5744628<4&x&=&\frac{3.5744628}{2}&=&1.7872314\\&&a&=&3+0.25&=&3.25\\\text{[TRUE]}&0.25>0.01&x&=&1.7872314^2&=&3.1941962\\&&b&=&\frac{0.25}{2}&=&0.125\\\\\text{[TRUE]}&2\leq 3.1941962<4&x&=&\frac{3.1941962}{2}&=&1.5970981\\&&a&=&3.25+0.125&=&3.375\\\text{[TRUE]}&0.125>0.01&x&=&1.5970981^2&=&2.5507224\\&&b&=&\frac{0.125}{2}&=&0.0625\\\\\text{[TRUE]}&2\leq 2.5507224<4&x&=&\frac{2.5507224}{2}&=&1.2753612\\&&a&=&3.375+0.0625&=&3.4375\\\text{[TRUE]}&0.0625>0.01&x&=&1.2753612^2&=&1.6265461\\&&b&=&\frac{0.0625}{2}&=&0.03125\\\\\text{[FALSE]}&2\leq 1.6265461<4\\\text{[TRUE]}&0.03125>0.01&x&=&1.6265461^2&=&2.6456525\\&&b&=&\frac{0.0625}{2}&=&0.015625\\\\\text{[TRUE]}&2\leq 2.6456525<4&x&=&\frac{2.6456525}{2}&=&1.3228262\\&&a&=&3.4375+0.015625&=&3.453125\\\text{[TRUE]}&0.015625>0.01&x&=&1.3228262^2&=&1.7498693\\&&b&=&\frac{0.015625}{2}&=&0.0078125\\\\\text{[FALSE]}&2\leq 1.7498693<4\\\text{[FALSE][STOP]}&0.0078125>0.01\end{array}

Hasil akhir :

Dengan demikian log_2(11)\approx 3.453125

Atas nama kerapihan, angka-angka pada perhitungan di atas telah “dipotong” dari angka yang sebenarnya. Pembaca mungkin akan mendapatkan angka yang berbeda jika meng-implementasi dan menjalnkan algoritma ini di dalam komputer ataupun kalkulator.

Hasil perhitungan-perhitungan di atas menggunakan ketelitian 0.01 dari hasil sebenarnya, sehingga ketika di-cross check akan memberikan angka yang tidak terlalu tepat.

Sebagai masukan, penulis biasanya menggunakan ketelitian 10^{-20} agar mendapatkan hasil yang cukup dekat dengan hasil yang sebenarnya. Selain itu, ketelitian tersebut masih sangat mungkin dilakukan pada tipe data “floating point” pada komputer 32 bit yang sehari-harinya penulis gunakan. Di dalam artikel ini, penulis secara sengaja menggunakan ketelitian 10^{-2} agar contoh eksekusi algoritma tidak terlalu panjang.

Sekali lagi, untuk mencari logaritma dalam basis lain dapat menggunakan invarian log_a(b)=\frac{log_2(b)}{log_2(a)}. Selamat mencoba.

Real Programmers Code in Binary

September 14, 2010

Permasalahan 100 dan 99

Filed under: Brain Teaser, Logaritma, Matematika — Hendra Jaya @ 7:42 am

Problem

Mana yang lebih besar? {100}^{99} atau {99}^{100}

Pembahasan (via Logaritma)

Pendekatan yang paling mudah adalah pendekatan melalui logaritma. Sekedar napak tilas untuk menyegarkan ingatan, penulis akan menyajikan ulang dua buah identitas pada logaritma :

  1. \log a^b=b.\log a
  2. Untuk bilangan bulat positif a dan b, jika diketahui a\geq b, maka \log a\geq\log b

Sekarang, kita asumsikan bahwa {100}^{99}>{99}^{100}, sehingga diharapkan \log {100}^{99}>\log {100}^{99}

Sesuai dengan rumus logaritma, kita memperoleh bahwa \log {100}^{99}=99\log 100=198 dan sebaliknya, kita juga memperoleh \log {99}^{100}=100\log 99

Sekarang, pertanyaannya berubah menjadi “Apakah \log 99<1.98 ?” Kita tidak tahu dengan pasti berapa nilai dari \log 99, tetapi kita tahu dengan pasti bahwa \log 100 adalah 2.

Seharusnya – hanya feeling – , \log 99 nilainya sekitar 1.99xxx.

Yap. \log 99 nilainya 1.9956351945975499153 di kalkulator.

Sehingga pertidaksamaan \log 99<1.98 bernilai salah dan dengan demikian asumsi awal yang dibuat pun salah. Suatu kontradiksi yang mengakibatkan pernyataan yang benar adalah {99}^{100}>{100}^{99}

Logarithm Under My Bed

Pembahasan (via Bilangan Euler)

Jika kita misalkan A=100^{99} dan B=99^{99} maka kita peroleh

\begin{array}{lll}\frac{A}{B}&=&\frac{100^{99}}{99^{99}}\\\\\frac{A}{B}&=&(\frac{100}{99})^{99}\\\\\frac{A}{B}&=&(1+\frac{1}{99})^{99}\end{array}

Bentuk \frac{A}{B} di atas sangat mirip dengan bentuk legendaris e=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n.

Dengan memerhatikan bahwa f(n)=(1+\frac{1}{n})^n adalah sebuah fungsi yang monoton naik dan konvergen, yakni

  • Monoton naik karena f(n+1)>f(n)
  • Konvergen karena f(n+1)-f(n)>f(n+2)-f(n+1). Tes konvergensi via perbandingan rasio

Selanjutnya, walaupun 99 tidak bisa dikatakan “tak terhingga”, namun bentuk di atas dapat memberi kita keyakinan bahwa

(1+\frac{1}{99})^{99}<e<99

atau sederhananya

(1+\frac{1}{99})^{99}<99

Dengan demikian \frac{100^{99}}{99^{99}}<99

Sebagai akibatnya 100^{99}<99^{100}

Secara umum, kita dapat mengatakan bahwa (n+1)^n<n^{n+1} berlaku untuk n\geq 3\text{ , }n\in\mathbb{Z} atau dalam kelompok bilangan lain (real) pertidaksamaan berlaku dengan syarat n>e\text{ , }n\in\mathbb{R} dimana e adalah bilangan Euler.

Simplified Version

Pembahasan (via Binomial Newton)

Jika diketahui 0\leq a<k\leq n dimana n,k,a\in\mathbb{Z}

Kita peroleh pertidaksamaan 1:

\begin{array}{rcll}k&>&a\\k-a&>&0\\k-a&\geq&1&\text{ karena }k-a\text{ adalah bilangan bulat}\\\frac{1}{k-a}&\leq&1\\\end{array}

Lalu, karena a\geq 0, kita peroleh pertidaksamaan 2:

\begin{array}{rcl}a&\geq&0\\-a&\leq&0\\n-a&\leq&n\end{array}

Dengan menggabungkan kedua pertidaksamaan, kita peroleh \frac{n-a}{k-a}\leq n

Selanjutnya

\begin{array}{rcl}\frac{n-0}{k-0}&\leq&n\\\frac{n-1}{k-1}&\leq&n\\\frac{n-2}{k-2}&\leq&n\\&\ldots\\\frac{n-(k-2)}{k-(k-2)}&\leq&n\\\frac{n-(k-1)}{k-(k-1)}&\leq&n\end{array}

Sehingga

\begin{array}{rcll}\frac{n-0}{k-0}.\frac{n-1}{k-1}.\frac{n-2}{k-2}\ldots\frac{n-(k-2)}{k-(k-2)}.\frac{n-(k-1)}{k-(k-1)}&\leq&n^k\\\\\frac{n}{k}.\frac{n-1}{k-1}.\frac{n-2}{k-2}\ldots\frac{n-k+2}{2}.\frac{n-k+1}{1}&\leq&n^k\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1)}{k.(k-1).(k-2)\ldots 2.1}&\leq&n^k\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1)}{k!}&\leq&n^k&\text{Definisi faktorial, yaitu }k!=k.(k-1).(k-2)\ldots 3.2.1\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1)}{1}.\frac{1}{k!}&\leq&n^k\\\\\frac{n.(n-1).(n-2)\ldots(n-k+2).(n-k+1).(n-k).(n-k-1).(n-k-2)\ldots 2.1}{(n-k).(n-k-1).(n-k-2)\ldots 2.1}.\frac{1}{k!}&\leq&n^k&\text{Kalikan pembilang dan penyebut dengan }(n-k).(n-k-1).(n-k-2)\ldots 2.1\\\\\frac{n!}{(n-k)!}.\frac{1}{k!}&\leq&n^k&\text{Definisi faktorial}\\\\\frac{n!}{k!(n-k)!}&\leq&n^k\\\\\binom{n}{k}&\leq&n^k&\text{Definisi kombinasi }\binom{n}{k}=\frac{n!}{k!(n-k)!}\end{array}

Dari definisi binomial Newton kita tahu bahwa (x+1)^n=\sum_{k=0}^n\binom{n}{k}x^k

Selanjutnya, dengan mengambil x=n, kita peroleh (n+1)^n=\sum_{k=0}^n\binom{n}{k}n^k

Setelah dijabarkan kita peroleh (n+1)^n=\binom{n}{0}n^0+\binom{n}{1}n^1+\binom{n}{2}n^2+\cdots+\binom{n}{n-1}n^{n-1}+\binom{n}{n}n^n

\begin{array}{rlrlrlrlrlclrlr}(n+1)^n&=&\binom{n}{0}n^0&+&\binom{n}{1}n^1&+&\binom{n}{2}n^2&+&\binom{n}{3}n^3&+&\cdots&+&\binom{n}{n-1}n^{n-1}&+&\binom{n}{n}n^n\\\\(n+1)^n&=&1&+&n^2&+&\binom{n}{2}n^2&+&\binom{n}{3}n^3&+&\cdots&+&\binom{n}{n-1}n^{n-1}&+&\binom{n}{n}n^n\\\\(n+1)^n&\leq&1&+&n^2&+&n^n&+&n^n&+&\cdots&+&n^n&+&n^n\end{array}

Dengan mengambil asumsi berani, yaitu :

n^2+1<n^n

Kita peroleh :

\begin{array}{llllr}(n+1)^n&\leq&(n^2+1)+(n-1).n^n&<&n^n+(n-1).n^n\\\\(n+1)^n&&&<&(1+n-1).n^n\\\\(n+1)^n&&&<&n.n^n\\\\(n+1)^n&&&<&n^{n+1}\end{array}

Satu-satunya yang mengganjal pada aljabar pertidaksamaan di atas adalah asumsi berani kita, yaitu n^2+1<n^n.

Secara intuitif jelas sekali bahwa kecepatan “terbang” fungsi kuadratik n^2 akan kalah jauh dibanding n^n. Hal ini wajar karena “pangkat” dari fungsi kuadratik adalah konstan, yaitu 2. Hal ini mirip dengan notasi Big-O pada ilmu komputasi. Pembaca yang berlatar belakang pemrograman tentu sudah menyadari hal ini.

Lantas, pada n berapa, pertidaksamaan n^2+1<n^n berlaku? Pada saat n=2, sisi kiri masih lebih besar dari sisi kanan, yaitu 2^2+1>2^2. Akan tetapi pada saat n=3, sisi kiri sudah kalah (dan akan terus kalah) dari sisi kanan, yaitu 3^2+1<3^3.

Sehingga pertidaksamaan (n+1)^n<n^{n+1} berlaku untuk n\geq 3\text{ , }n\in\mathbb{Z}

Pretty Heavy Stuff

Blog di WordPress.com.