Induksi Matematika

Bismillah

Salah satu cara pembuktian dalam matematika adalah pembuktian dengan cara induksi matematika. Post author kali ini akan membahas history, prinsip induksi matematika, langkah-langkah pembuktian dengan cara induksi, dan contoh soal yang akan dibuktikan menggunakan induksi.

Induksi matematika merupakan teknik pembuktian yang baku dalam matematika. Melalui induksi matematika, kita dapat mengurangi langkah pembuktian yang sangat rumit untuk menemukan suatu kebenaran dari pernyataan matematis hanya dengan sejumlah langkah terbatas yang cukup mudah. Prinsip induksi matematika memiliki efek domino (jika domino disusun berjajar dengan jarak tertentu, saat satu ujung domino dijatuhkan ke arah domino lain, maka semua domino akan jatuh satu per satu).

Coba perhatikan gambar dibawah ini!

Historis

Pertama mengetahui penggunaaninduksi matematika adalah dalam karya matematis abad ke-16 Francesco Maurolico (1494-1575). Maurolico menulis secara ekstensif pada karya-karya matematika klasik dan membuat banayk kontribusi kepada geometri dan optik. Dalam bukunya Arithmeticorum Libri Duo, Maurolico menyajikan berbagia sifat-sifat ini. Untuk bukti beberapa sifat ini Maurolico mengemukakan metode induksi matematis. Penggunaan induksi matematis pertamanya dalam buku ini adalah untuk membuktikan bahwa jumlah dari n bilangan bulat positif ganjil pertama sama dengan n^2.

Ingat, dengan induksi matematika dapat melakukan pembuktian kebenaran suatu pernyataan matematika yang berhubungan dengan bilangan asli, bukan untuk menemukan formula.

Prinsip Induksi Matematika

Misalkan P(n) adalah pernyataan yang akan dibuktikan untuk setiap bilangan asli. PernyataanP(n) benar jika memenuhi langkah berikut ini:

  • Langkah Awal (Basic Step) : P(1) benar
  • Langkah Induksi (Induction Step) : Jika P(k) benar, maka P(k+1) benar, untuk setiap k bilangan asli.

Pada proses pembuktian dengan prinsip Induksi Matematika, untuk langkah awal tidak selalu dipilih untuk n=1, n=2, atau n=3, tetapi dapat dipilih sebarang nilai n sedemikian sehingga dapat mempermudah supaya proses langkah awal dipenuhi. Selanjutnya, yang ditemukan pada langkah awal merupakan modal untuk langkah induksi. Artinya, jika P(1) benar, maka P(2) benar; jika P(2) benar, maka P(3) benar, dan seterusnya, sehigga disimpulkan P(k) benar. Dengan menggunakan P(k) benar, makaakan ditunjukkan P(k+1) benar. Jika P(n) memenuhi kedua prinsip induksi matematika, maka formula P(n) terbukti benar. Jika salah satu dari kedua prinsip tidak dipenuhi, maka formula P(n) salah.

Induksi matematika berisi tentang pembuktian terkait bilangan bulat (\mathbb{Z}) dan bilangan asli (\mathbb{N}).
Langkah-langkah pembuktian dengan induksi matematika diadopsi dari prinsip dari induksi matematika itu sendiri, yaitu

  • Misalkan P(n) adalah pernyataan yang akan dibuktikan untuk setiap bilangan asli
  • Langkah (1) : Ditunjukkan bahwa P(1) benar
  • Langkah (2) : Diasumsikan bahwa P(n) benar untuk setiap n\in \mathbb{N}, dan akan ditunjukkan bahwa P(n+1) benar

atau

  • Misalkan P(n) adalah pernyataan yang akan dibuktikan berlaku benar untuk setiap n>m, n, m \in \mathbb{N}
  • Langkah (1) : Ditunjukkan bahwa P(m) benar
  • Langkah (2) : Diasumsikan bahwa P(k) benar untuk setiap k>m, dan akan ditunjukkan bahwa P(k+1) benar

Langkah (1) merupakan langkah dasar, sedangkan langkah (2) merupakan langkah induktif

Itulah tadi langkah-langkah pembuktian dengan induksi matematika
simpel kan? 🙂

Selanjutnya, kita beralih ke contoh soal yang dibuktikan dengan cara induksi matematika

  1. Buktikan bahwa 1+2+3+\cdots+n=\frac{n(n+1)}{2}, \forall n\in \mathbb{N}
    Bukti:
    Akan dibuktikan 1+2+3+\cdots+n=\frac{n(n+1)}{2}, \forall n\in \mathbb{N} dengan induksi
    Misalkan P(n):1+2+3+\cdots+n=\frac{n(n+1)}{2}
    Langkah (1) : Akan ditunjukkan bahwa P(1) benar yaitu P(1)=\frac{1(1+1)}{2}=1
    Langkah (2) : Diasumsikan bahwa P(n) benar, dan akan ditunjukkan bahwa P(n+1) benar yaitu

        \begin{align*} P(n+1)&= 1+2+3+\cdots+n+(n+1)\\ &=\frac{n(n+1)}{2}+(n+1)\\ &=\frac{n^2+n}{2}+(n+1)\\ &=\frac{n^2+n}{2}+\frac{2n+2}{2}\\ &=\frac{n^2+3n+2}{2}\\ &=\frac{(n+2)(n+1)}{2}\\ &=\frac{((n+1)+1)(n+1)}{2} \end{align*}

    Jadi, P(n+1) benar
    Kesimpulan P(n):1+2+3+\cdots+n=\frac{n(n+1)}{2} benar \forall n \in \mathbb{N}

  2. Buktikan bahwa n^2\leq 2^n, \forall n \in \mathbb{N}, n\geq 4
    Bukti:
    Akan dibuktikan n^2\leq 2^n dengan induksi
    Misalkan P(n): n^2\leq 2^n \forall n\in \mathbbN, n\geq 4
    Langkah (1) : Akan ditunjukkan bahwa P(4) benar yaitu

        \begin{align*} P(4)&=4^2\leq 2^4\\ &=16\leq 16 \end{align*}

    Langkah (2) : Diasumsikan bahwa P(n) benar, dan akan ditunjukkan bahwa P(n+1) benar yaitu

        \begin{align*} P(n+1)&=(n+1)^2\\ &=n^2+2n+1\\ &\leq 2^n+2n+1\\ &\leq 2^n+2^n\\ &=2^n\cdot 2\\ &=2^{n+1} \end{align*}

    atau

        \begin{align*} P(n+1)&= 2^{n+1}\\ &=2^n\cdot 2\\ &\geq n^2\cdot 2\\ &=n^2+n^2\\ &=n^2+2n+1\\ &=(n+1)^2 \end{align*}

    Jadi, P(n+1) benar
    Kesimpulan P(n): n^2\leq 2^n benar \forall n\in \mathbb{N}, n\leq 4

  3. Buktikan bahwa 1\cdot 2\cdot 3+2\cdot 3\cdot 4+\cdots +n\cdot (n+1)\cdot (n+2)=3!{{n+3}\choose 4}\forall n\in \mathbb{N}
    Bukti:
    Akan dibuktikan bahwa 1\cdot 2\cdot 3+2\cdot 3\cdot 4+\cdots +n\cdot (n+1)\cdot (n+2)= 3!{{n+3}\choose 4} dengan induksi
    Misalkan P(n):1\cdot 2\cdot 3+2\cdot 3\cdot 4+\cdots +n\cdot (n+1)\cdot (n+2)= 3!{{n+3}\choose 4}
    Langkah (1) : Akan ditunjukkan bahwa P(1) benar yaitu

        \begin{align*} P(1)&= 3!{{1+3}\choose 4}\\ &=3!{ 4 \choose 4}\\ &=3!\\ &=6 \end{align*}

    Langkah (2) : Diasumsikan bahwa P(n) benar, dan akan ditunjukkan bahwa P(n+1) benar yaitu

        \begin{align*} P(n+1)&= 1\cdot 2\cdot 3+2\cdot 3\cdot 4+\cdots +n\cdot (n+1)\cdot (n+2)+ (n+1)\cdot (n+1+1)\cdot (n+1+2)\\ &=1\cdot 2\cdot 3+2\cdot 3\cdot 4+\cdots +n\cdot (n+1)\cdot (n+2)+ (n+1)\cdot (n+2)\cdot (n+3)\\ &=3!{{n+3}\choose 4}+(n+1)\cdot (n+2)\cdot (n+3)\\ &=3!{{n+3}\choose 4}+(n^2+3n+2)\cdot (n+3)\\ &=3!\frac{(n+3)!}{4!(n+3-4)}+(n^3+6n^2+11n+6)\\ &=3!\frac{(n+3)!}{4!(n-1)}+(n^3+6n^2+11n+6)\\ &=3!\frac{(n+3)(n+2)(n+1)(n)(n-1)!}{4\cdot 3!(n-1)!}+(n^3+6n^2+11n+6)\\ &=\frac{n^4+6n^3+11n^2+6n}{4}+\frac{4n^3+24n^2+44n+24}{4}\\ &=\frac{n^4+10n^3+35n^2+50n+24}{4}\\ &=\frac{(n^2+7n+12)(n^2+3n+2)}{4}\\ &=\frac{(n+4)(n+3)(n+2)(n+1)}{4}\\ &=3!\frac{(n+4)(n+3)(n+2)(n+1)(n)!}{4\cdot 3!\cdot n!}\\ &=3!\frac{(n+4)!}{4!\cdot (n+4-4)!}\\ &=3!{{n+4}\choose 4}\\ &=3!{{n+1+3}\choose 4} \end{align*}

    Jadi, P(n+1) benar
    Kesimpulan P(n): 1\cdot 2\cdot 3+2\cdot 3\cdot 4+\cdots +n\cdot (n+1)\cdot (n+2)=3!{{n+3}\choose 4}\forall n\in \mathbb{N}

  4. Buktikan dengan induksi bahwa untuk setiap bilangan asli n, berlaku \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots +\frac{1}{\sqrt{n}}\le 2\sqrt{n}-1
    Bukti:
    Akan dibuktikan bahwa \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots +\frac{1}{\sqrt{n}}\le 2\sqrt{n}-1,\forall n\in \mathbb{N}
    Perhatikan bahwa
    Akan ditunjukkan bahwa untuk n=1 benar, yaitu

        \begin{align*} \frac{1}{\sqrt{1}}&\le \frac{1}{1}\\ &\le 1\\ &\le 2-1\\ &\le 2(1)-1\\ &\le 2\sqrt{1}-1 \end{align*}

    Maka, n=1 benar
    Asumsikan untuk n=k benar, yaitu
    \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots +\frac{1}{\sqrt{k}}\le 2\sqrt{k}-1
    dan akan ditunjukkan bahwa untuk n=k+1 benar, yaitu

        \begin{align*} \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots +\frac{1}{\sqrt{k}}+\frac{1}{\sqrt{k+1}}&\le 2\sqrt{k}-1+\frac{1}{\sqrt{k+1}}\\ &\le \frac{(2\sqrt{k}-1)(\sqrt{k+1})}{\sqrt{k+1}}+\frac{1}{\sqrt{k+1}}\\ &\le \frac{2\sqrt{k(k+1)}-\sqrt{k+1}+1}{\sqrt{k+1}}\\ &\le \frac{2\sqrt{k^2+k}-\sqrt{k+1}+1}{\sqrt{k+1}}\\ &\le \frac{2\sqrt{k^2+2k+1}-\sqrt{k+1}}{\sqrt{k+1}} &[\frac{2\sqrt{k^2+k}-\sqrt{k+1}+1}{\sqrt{k+1}}\le \frac{2\sqrt{k^2+2k+1}-\sqrt{k+1}}{\sqrt{k+1}}]\\ &\le \frac{2\sqrt{(k+1)^2}-\sqrt{k+1}}{\sqrt{k+1}}\\ &\le \frac{2(k+1)-\sqrt{k+1}}{\sqrt{k+1}}\\ &\le \frac{2(k+1)}{\sqrt{k+1}}-\frac{\sqrt{k+1}}{\sqrt{k+1}}\\ &\le 2\sqrt{k+1}-1 \end{align*}

    Maka, n=k+1 benar
    Kesimpulan: \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\cdots +\frac{1}{\sqrt{n}}\le 2\sqrt{n}-1 benar, \forall n\in \mathbb{N}

Bagi readers yang ingin mencoba menyelesaikan soal pembuktian Induksi Matematika, author menyediakan beberapa soal untuk dijadikan sebagai latihan 🙂

  1. Buktikan dengan induksi matematika bahwa jumlah n bilangan ganjil positif yang pertama sama dengan n^2
  2. Gunakan induksi matematika untuk membuktikan bahwa:
    1+2+2^2+2^3+\cdots +2^n=2^{n+1}-1
    Untuk setiap n bilangan bulat positif!
  3. Untuk setiap bilangan asli, dengan n\geq 1 berlaku:
    \frac{1}{1(2)}+\frac{1}{2(3)}+\frac{1}{3(4)}+\cdots +\frac{1}{n(n+1)}=\frac{n}{n+1}
    Buktikan dengan induksi matematika!

Mudah-mudahan bermanfaat 🙂

Kurang lebihnya mohon dimaafkan

Wassalam

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *