Induksi Matematika

Pada tulisan ini saya ingin sedikit mengenalkan tentang salah satu metode pembuktian pada matematika yaitu induksi matematika. Metode pembuktian ini dapat diterapkan juga dalam bidang informatika, salah satu contohnya ialah untuk membuktikan kebenaran dari suatu algoritma.

1. Introduction

Himpunan bilangan asli $$\mathbb{N} = \{1, 2, 3, \cdots \}$$ memiliki dua operasi, penjumlahan dan perkalian, serta memiliki hubungan keterurutan. Himpunan bilangan asli memiliki banyak properti dasar yang berlaku. Pada tulisan ini, salah satu sifat dasar yang akan digunakan ialah Well Ordering Principle.

1.1 (Well Ordering Principle of $\mathbb{N}$) Setiap himpunan bagian tak kosong dari $\mathbb{N}$ memiliki anggota terkecil.

Lebih jelasnya, jika $S$ ialah himpunan bagian dari $\mathbb{N}$ dan $S$ bukan himpunan kosong maka terdapat $m \in S$ sehingga $m \leq k$ untuk setiap $k \in S$.

2. Induksi Matematika

2.1 Prinsip Induksi Matematika

Induksi matematika merupakan salah satu metode pembuktian yang sangat sering digunakan untuk membuktikan kebenaran dari sebuah proposisi yang berkaitan dengan bilangan asli.

2.1.1 (Induksi Matematika) Misalkan $S$ himpunan bagian dari $\mathbb{N}$ yang memiliki kedua sifat berikut

1. $1 \in S$

      2. Untuk setiap $k \in \mathbb{N}$, jika $k \in S$ maka $k+1 \in S$
Maka $S = \mathbb{N}$

Bukti Asumsikan yang terjadi ialah $S \neq \mathbb{N}$, hal ini berarti himpunan $\mathbb{N}\setminus S$ merupakan himpunan tak kosong. Berdasarkan Well Ordering Principle himpunan $\mathbb{N} \setminus S$ memiliki anggota terkecil $m$. Karena $1 \in S$, maka $m > 1$ yang berarti $m - 1$ merupakan bilangan asli. Karena $m - 1 < m$ dan $m$ merupakan anggota terkecil dari himpunan $\mathbb{N} \setminus S$, dapat disimpulkan $m - 1 \in S$. Berikutnya dapat dilihat dari sifat kedua, dengan mengambil $k = m$ diperoleh $k + 1 = (m - 1) + 1 = m$ merupakan anggota dari $S$. Hal ini kontradiksi dengan fakta bahwa $m \notin S$. Jadi asumsi awal salah, yang berarti terbukti bahwa haruslah $S = \mathbb{N}$.

$\blacksquare$

Definisikan $P(n)$ merupakan sebuah pernyataan dengan $n\in\mathbb{N}$ sehingga $P(n)$ dapat bernilai benar untuk beberapa nilai $n$ dan salah untuk beberapa lainnya. Sebagai contoh, jika $P(n)$ merupakan sebuah pernyataan "$n^2 = n$", artinya $P(1)$ benar dan $P(n)$ salah untuk semua $n > 1, n\in\mathbb{N}$. Dalam metode pembuktian, Induksi matematika juga dapat dirumuskan sebagai berikut.

2.1.2 (Induksi Matematika) Untuk setiap $n \in \mathbb{N}$, misalkan $P(n)$ merupakan sebuah pernyataan tentang $n$. Jika berlaku 

      1'. $P(1)$ benar 

      2'. Untuk setiap $k \in \mathbb{N}$, jika $P(k)$ benar, maka $P(k+1)$ benar.

Maka $P(n)$ benar untuk semua $n \in \mathbb{N}$.

Hubungan antara prinsip Induksi Matematika 2.1.1 dengan 2.1.2 dapat dijelaskan dengan memisalkan $S := \{ n \in \mathbb{N} : P(n) \ \text{benar} \}$.

2.2 Langkah - Langkah Pembuktian

Dalam menggunakan Induksi Matematika terdapat dua langkah yang perlu dikerjakan. Langkah pertama disebut basis induksi dan langkah kedua disebut langkah induksi. Langkah induksi berisi andaian (asumsi) yang menyatakan bahwa $P(n)$ benar. Asumsi tersebut dinamakan hipotesis induksi. Dengan menunjukan basis induksi dan langkah induksi, maka sudah terbukti bahwa $P(n)$ benar untuk semua bilangan bulat postitf $n$. Perhatikan contoh berikut

(Contoh) Buktikan bahwa jumlah $n$ bilangan bulat positif pertama adalah $\frac{n(n + 1)}{2}$.

(Solusi) Misalkan $P(n)$ menyatakan proposisi bahwa jumlah $n$ bilangan bulat pertama adalah $\frac{n(n + 1)}{2}$, yaitu $1 + 2  + 3 + \cdots + n = \frac{n(n + 1)}{2}$.

Basis Induksi : Buktikan $P(1)$ benar, karena untuk $n = 1$ diperoleh

$$\begin{aligned} 1 &= \frac{1(1 + 1)}{2} \\ &= \frac{2}{2} \\ &= 1 \end{aligned}$$

Langkah Induksi : Misalkan berlaku bahwa $P(k)$ benar yaitu mengasumsikan bahwa $$1 + 2 + 3 + \cdots k = \frac{k(k + 1)}{2}$$ adalah benar (hipotesis induksi). Harus diperlihatkan bahwa $P(k + 1)$ juga benar yaitu $$1 + 2 + 3 + \cdots k + (k + 1) = \frac{(k + 1)(k + 2)}{2}$$ Perhatikan bahwa $$\begin{aligned}1 + 2 + 3 + \cdots k + (k + 1) &= (1 + 2 + 3 + \cdots + k) + (k + 1) \\ &= \frac{k(k + 1)}{2} + (k + 1) \\ &= \frac{k^2 + k}{2} + (k + 1) \\ &= \frac{k^2 + 3k + 2}{2} \\ &= \frac{(k+1)(k+2)}{2} \end{aligned}$$ Karena basis induksi dan langkah induksi telah dibuktikan benar, maka untuk semua bilangan bulat positif $n$, terbukti bahwa $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$

$\blacksquare$

2.3 Jenis - Jenis Induksi

2.3.1 Induksi Matematika yang Dirampatkan

Misalkan $P(n)$ adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa $P(n)$ benar untuk semua bilangan bulat $n \geq n_0$. Untuk membuktikan hal tersebut, kita hanya perlu menunjukan bahwa : 

1. $P(n_0)$ benar 

2. Jika $P(k)$ benar maka $P(k + 1)$ juga benar, untuk setiap bilangan bulat $k \geq n_0$

(Contoh) Buktikan bahwa ketaksamaan berikut benar untuk bilangan bulat $n \geq 3$ $$2^n > 2n + 1$$

(Solusi) Basis Induksi : Untuk $n = 3$ berlaku $2^3 > 2 \times 3 + 1$ karena $8 > 7$

Langkah Induksi : Asumsikan pernyataan $2^k > 2k + 1$ benar. Dengan mengalikan 2 kepada kedua ruas maka diperoleh $$2^{k+1} > 2(2k+1) = 4k + 2 = 2k + (2k+2) > 2k + 3 = 2(k+1) + 1$$ karena $2k + 2 > 3$ untuk setiap $k \geq 3$. Artinya basis induksi dan langkah induksi terbukti benar. Jadi benar bahwa ketaksamaan $2^n > 2n + 1$ untuk semua bilangan bulat $n \geq 3$

$\blacksquare$

2.3.2 Induksi Kuat

Misalkan $P(n)$ adalah pernyataan perihal bilangan bulat. Kita ingin membuktikan bahwa $P(n)$ benar untuk semua bilangan bulat $n \geq n_0$. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa :

1. $P(n_0)$ benar, dan 

2, Jika $P(n_0)$, $P(n_0 + 1)$, $\cdots$, $P(k)$ benar maka $P(k+1)$ juga benar untuk setiap bilangan bulat $k \geq n_0$

(Contoh) Bilangan bulat postif disebut prima jika dan hanya jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri. Kita ingin membuktikan bahwa setiap bilangan bulat positif $n$ $(n \geq 2)$ dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.

(Solusi) Basis Induksi : Untuk $n = 2$, maka 2 sendiri adalah bilangan prima dan 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri.

Langkah Induksi : Misalkan pernyataan pada soal benar bahwa bilangan $2, 3, \cdots, k$ dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima adalah benar (hipotesis induksi). Perlu ditunjukkan bahwa $k + 1$ juga dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima. Ada dua kemungkinan yang dapat terjadi yaitu

(a) Jika $k + 1$ merupakan bilangan prima, maka jelas $k+1$ dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.

(b) Jika $k + 1$ bukan bilangan prima, maka terdapat bilangan bulat positif $a$ dan $b$ dengan $2 \leq a \leq b \leq k$ sehingga $k + 1 = ab$. Menurut hipotesis induksi, $a$ dan $b$ dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Hal ini menandakan bahwa $k+1$ dapat dinyatakan sebagai perkalian bilangan prima karena $k+1 = ab$.

Karena basis induksi dan langkah iduksi sudah ditunjukkan benar maka terbukti bahwa setiap bilangan bulat positif $n$ $(n \geq 2)$ dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.

$\blacksquare$

Selain kedua jenis diatas, masih terdapat banyak jenis - jenis induksi yang bisa digunakan dalam membuktikan kebenaran sebuah pernyataan perihal bilangan bulat.

3. Aplikasi Induksi Matematika untuk Membuktikan Kebenaran Program

function Exp (a : integer, m : integer)
{Fungsi untuk menghitung $a^m$}
Deklarasi
        $k,r$ : integer

Algoritma
        $r$ $\leftarrow$ $1$
        $k$ $\leftarrow$ $m$
        while ($k > 0$)
                $r$ $\leftarrow$ $r*a$
                $k$ $\leftarrow$ $k-1$
        end
        return r

Algoritma di atas dapat dibuktikan benar dengan induksi matematika, yaitu di akhir algoritma fungsi mengembalikan nilai $a^m$.  Misalkan $r_n$ dan $k_n$ adalah nilai dari $r$ dan $k$ berturut - turut setelah melewati loop while sebanyak $n$ kali ($n \geq 0$). Misalkan $P(n)$ adalah proposisi : $r_n \times k_n = a^m$, $n \geq 0$. Akan ditunjukkan bahwa $P(n)$ benar dengan induksi matematika.

Basis induksi : Untuk $n = 0$, maka $r_0 = 1$ dan $k_0 = m$. Maka $P(0)$ benar sebab $$r_0 \times a^{k_0} = a^m \Leftrightarrow  1 \times a^m = a^m$$

Langkah induksi : Asumsikan $P(n)$ benar untuk $n \geq 0$, yaitu setelah melewati while loop $n$ kali, yaitu $r_n \times a^{k_n} = a^m$. Kita harus menunjukan bahwa $P(n+1)$ benar, yaitu $r_{n+1} \times a^{k_{n+1}} = a^m$ Perhatikan bahwa $$ r_{n+1} = r_n \times a$$ $$k_{n+1} = k_n - 1$$ maka $$\begin{aligned} r_{n+1} \times a^{k_{n+1}} &= (r_n \times a) \times a^{k_n - 1} \\ &= r_n \times a^{k_n} \\ &= a^m \end{aligned}$$ Jadi $P(n+1)$ benar.

Karena kedua langkah telah ditunjukkan benar maka $P(n)$ benar untuk setiap $n \geq 0$. Algoritma fungsi diatas mengembalikan nilai dari $r_n$ disaat $k_n = 0$, yang berarti $r_n \times 1 = a^m$, dengan kata lain algoritma fungsi diatas mengembalikan nilai $a^m$.

$\blacksquare$

Referensi :

1. Introduction to Real Analysis (Fourth Edition) - Robert G. Bartle & Donald R. Sherbert
2. Slide Mata Kuliah Matematika Diskret ITB - Induksi Matematik - Rinaldi Munir

Tes IV Pelatnas I IMO 2016

1. Diberikan barisan bilangan real $\{a_n\}_{n \geq 1}$ yang memenuhi $$4a_{n+1}a_{n} + a_{n+1}+ 3a_{n} + 1= 0$$ dan $a_{n} \leq a_{2015}$ untuk setiap bilangan asli $n$. Tentukan semua nilai $a_{1}$ yang mungkin.

2. Tunjukan bahwa terdapat himpunan bagian $A$ dari $\{1, 2, 3, ... , 2014\}$ yang memiliki 12 unsur sedemikian hingga setiap pewarnaan bilangan bilangan di $A$ dengan merah atau putih selalu ditemukan beberapa bilangan sewarna di $A$ yang hasil penjumlahannya adalah $2015$.

3. Diketahui $a$ adalah akar positive dari $x^2 + x = 5$. Dimisalkan n bilangan asli dan $k_0, k_1, ... , k_n$ adalah bilangan bulat tak negatif yang memenuhi $$k_0 + k_1a +k_2a^2 + ... + k_na^n = 2015$$
(a) Buktikan bahwa $k_0 + k_1 + ... + k_n \equiv 2 (\text{mod} \ 3)$
(b) Tentukan nilai terkecil $k_0 + k_1 + ... + k_n$

4. Pada segitiga tak sama kaki $ABC$, titik $D$ dan $E$ berturut turut terletak pada garis $AB$ dan $AC$ sedemikian hingga lingkaran luar $ACD$ dan $ABE$ menyinggung garis $BC$. Misalkan $F$ adalah perpotongan dari $BC$ dan $DE$. Buktikan bahwa $AF$ tegak lurus dengan garis Euler dari segitiga $ABC$.

 Waktu : 4 Jam

Tes 3 Pelatnas 1 IMO 2016

1. 7 orang akan bertanding, setiap dua orang bertanding tepat satu kali. Skor untuk menang, seri, dan kalah berturut - turut adalah 3, 1, dan 0. Dapatkah skor terakir berupa bilangan berurutan $a, a+1, ... , a+6$ ? Jika dapat tentukan semua nilai $a$ yang mungkin.

2. Buktikan bahwa ketaksamaan
$$ \frac{x-y}{xy + 2y + 1} + \frac{y-z}{yz + 2z +1} + \frac{z-x}{zx + 2x + 1} \geq 0$$
berlaku untuk sebarang bilangan real tak negatif $x, y, z$

3. Diberikan segiempat talibusur $ABCD$, dimana $AD = BD$. Misalkan $M$ titik potong antara segmen $AC$ dengan segmen $BD$. Misalkan pula $I$ pusat lingkaran dalam segitiga $BCM$. Misalkan $N$ titik potong kedua kalinya antara $AC$ dengan lingkaran luar segitiga $BMI$. Buktikan bahwa $AN . NC = CD . BN$

4. Tentukan semua pasangan bilangan bulat $(a,b)$ yang memenuhi persamaan $$a^3 + b^3 + 3ab = 1$$

Tes 2 Pelatnas 1 IMO 2016

1. Gambar dibawah menunjukan persegi panjang yang dibagi menjadi delapan petak ( persegi panjang yang lebih kecil ). Dua petak dikatakan berdampingan jika mempunyai lebih dari satu titik persekutuan. Semua bilangan $1,2,3,4,5,6,7,$ dan $8$ akan ditempatkan pada delapan petak tersebut, masing-masing petak berisi satu bilangan, sehingga tidak ada dua petak berdampingan yang berisi dua bilangan dengan selisih 4. Ada berapa cara penempatan tersebut ?

2. Pada segiempat talibusur $ABCD$, titik $F$ adalah perpotongan kedua diagonal. Misalkan $P,Q,$ dan $M$ berturut - turut adalah titik tengah $BF,CF,$ dan $BC$. Misalkan $E$ adalah perpotongan sinar $BA$ dan $CD$ serta $N$ adalah titik tengah $EF$. Buktikan bahwa segiempat $AEDF$ sebangun dengan segiempat $QNPM$.

3.Tentuka n semua fungsi $f : \mathbb{R} \rightarrow \mathbb{R}$ yang memenuhi
$$f(xf(y) + 4f(x)) = f(yf(x)) + x $$
untuk setiap $x,y \in \mathbb{R}$

4. Untuk sebarang bilangan asli $n$ definisikan $H_n$ adalah bilangan bulat terbesar yang membagi habis $a^n + (a+1)^n + (a+2)^n$ untuk setiap bilangan asli $a$.

(a). Tunjukan bahwa untuk semua bilangan asli $n$, bilangan $H_n$ berbentuk $3^k$ untuk suatu bilangan bulat $k \geq 0 $
(b). Tunjukkan bahwa untuk setiap bilangan bulat $k \geq 0$ terdapat bilangan asli $n$ yang memenuhi $H_n = 3^k$.

Tes 1 Pelatnas 1 IMO 2016

1. Tentukan semua bilangan asli $n$ sehingga $$\frac{10^n}{n^3 + n ^2 + n + 1}$$ merupakan bilangan asli.

2. Diberikan jajargenjang $ABCD$ dengan $AB$ sebagai alasnya. Misalkan titik $S$ adalah titik potong antara kedua diagonalnya dan titik $I$ adalah pusat lingkaran dalam segitiga $ABD$, serta titik $T$ adalah titik singgung lingkaran dalam segitiga $ABD$ dengan diagonal $BD$. Buktikan $IS$ sejajar dengan $CT$.

3. Misalkan $x_1, x_2, ... , x_n$ bilangan real yang lebih dari atau sama dengan 1. Buktikan bahwa
$$( \frac{x_1}{x_1 + 1} + \frac{x_2}{x_2 + 1} + ... + \frac{x_n}{x_n + 1})(\sqrt[n]{x_1x_2...x_n} + 1) \leq n\sqrt[n]{x_1x_2...x_n}$$

4. Suatu bahasa memiliki $n$ huruf. Suatu kata dalam bahasa ini dikatakan puitis jika untuk setiap dua huruf yang sama yang muncul dalam kata tersebut tidak terdapat dua huruf yang sama diantara keduanya.

(a). Tentukan panjang maksimal yang mungkin dimiliki kata puitis.
(b). Tentukan banyaknya kata puitis yang mungkin dengan panjang maksimal

Tes II Pelatnas tahap 1 IMO Indonesia 2015

1. Tentukan semua pasangan bilangan bulat positif $(a,b)$ sehingga $$ab+a+b \ | \ a^2 + b^2 + 1$$

2. Tentukan bilangan asli terbesar $z$ sehingga $z$ terbagi habis oleh semua bilangan bulat yang tidak lebih besar dari $\sqrt[3]{z}$

3. Tentukan semua pasangan bilangan bulat $(a,b)$ yang memenuhi
$$\frac{a^2+1}{2b^2-3} = \frac{a-1}{2b-1}$$

4. Diketahui $a$ dan $b$ bilangan asli yang relatif prima. Diberikan $a_n$ dan $b_n$ berisan barisan bilangan asli yang memenuhi $$(a+b\sqrt{2})^{2n} = a_n + b_n\sqrt{2}$$
Tentukan semua bilangan prima $p$ sehingga dapat ditemukan bilangan asli $n \leq p$ yang memenuhi $b_n \equiv 0 (\text{mod} \ p)$


Waktu : 240 menit

IMO 2015 Problems

Day 1

1. We say that finite set $\mathcal{S}$ of points in the plane is balanced if, for any two different points $A$ and $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC = BC$. We say that $\mathcal{S}$ is centre-free if for any three different points $A,B$ and $C$ in $\mathcal{S}$, there is no points $P$ in $\mathcal{S}$ such that $PA = PB = PC$.

(a) Show that for all integers $n \geq 3$, there exists a balanced set consisting of $n$ points.

(b) Determine all integers $n \geq 3$ for which there exsits a balanced centre-free set consisting of $n$ points.

2. Find all positive integers $(a,b,c)$ such that $$ab - c, \ bc - a, \ ca - b$$ are all powers of $2$.

3. Let $ABC$ be an acute triangle with $AB > BC$. Let $\Gamma$ be its circumcircle, $H$ its orthocenter, and $F$ the foot of the altitude from $A$. Let $M$ be the midpoint of $BC$. Let $Q$ be the point on $\Gamma$ such that $\angle HQA = 90^{\circ}$ and let $K$ be the point on $\Gamma$ such that $\angle HKQ = 90 ^{\circ}$. Assume that the points $A, B, C, K$ and $Q$ are all different and lie on $\Gamma$ in this order.

Prove that the circumcircles of triangles $KHQ$ and $FKM$ are tangent to each other.

Day 2

4. Triangle $ABC$ has circumcircle $\Omega$ and circumcenter $O$. A circle $\Gamma$ with center $A$ intersects the segment $BC$ at points $D$ and $E$, such that $B, D, E$ and $C$ are all different and lie on line $BC$ in this order. Let $F$ and $G$ be the points of intersection of $\Gamma$ and $\Omega$, such that $A, F, B, C$ and $G$ lie on $\Omega$ in this order. Let $K$ be the second point of intersection of the cicumcircle of triangle $BDF$ and the segment $AB$. Let $L$ be the second point of intersection of the circumcircle of triangle $CGE$ and the segment $CA$.

Suppose that the lines $FK$ and $GL$ are all different and intersect at the point $X$. Prove that $X$ lies on the line $AO$.

5. Let $\mathbb{R}$ be the set of real numbers. Determine all functions $f : \mathbb{R} \rightarrow \mathbb{R}$ that satisfy the equation $$ f(x + f(x+y)) +f(xy) = x + f(x+y) + yf(x)$$
for all real numbers $x$ and $y$.

6. The sequnce $a_{1}, a_{2}, . . . $ of integers satisfies the conditions :
(i) $1 \leq a_{j} \leq 2015$ for all $j \geq 1$,
(ii) $k + a_{k} \neq l + a_{l}$ for all $1 \leq k < l$.

Prove that there exist two positive integers $b$ and $N$ for which $$ \left | \sum_{j = m + 1}^{n}(a_{j} - b) \right | \leq 1007^{2}$$ for all integers $m$ and $n$ such that $ n > m \geq N$.