Induksi Matematika

MASTER MATEMATIKA
Pengantar Pemecahan Masalah
Pemecahan masalah atau problem solving adalah proses untuk menemukan solusi dari suatu masalah dengan menggunakan pengetahuan dan keterampilan yang sudah ada. Pemecahan masalah merupakan soft skill yang penting untuk menghadapi tantangan dalam kehidupan sehari – hari, terutama ketika harus menemukan solusi inovatif untuk masalah yang rumit
Kelas

Materi ini ditunjukan untuk siswa berbakat kelas 4, 5, 6, 7 dan 8

Presentasi

Unduh

Video Pengantar

 fira

Video Lanjutan

.

Pre Test

.

Post Test

.

Referensi Tambahan

Unduh

  • Definisi​
  • Variasi Induksi Matematika​
  • Contoh Soal

Definisi

Induksi Matematika adalah alat yang sangat ampuh untuk membuktikan banyak proposisi tak terhingga hanya dengan beberapa langkah. Khususnya, induksi ini dapat sering digunakan ketika proposisi tersebut melibatkan bilangan bulat nonnegatif $n$.

Teorema I. (Induksi Pertama) Misalkan $\{P_n\}, n ≥ m$ merupakan keluarga dengan tak terhingga banyaknya proposisi (atau pernyataan) yang melibatkan bilangan bulat $n$, dengan $m$ adalah bilangan bulat nonnegatif. Jika (i) $P_m$ dapat dibuktikan benar, dan (ii) $P_{k+1}$ pasti benar asalkan $P_k$ benar untuk setiap $k ≥ m$, maka $P_n$ benar untuk semua $n ≥ m$.

Teorema II. (Induksi Kedua) Misalkan $\{P_n\}, n ≥ m$ merupakan keluarga yang terdiri dari tak terhingga banyak proposisi (atau pernyataan) yang melibatkan bilangan bulat $n$, di mana $m$ adalah bilangan bulat nonnegatif. Jika (i) $P_m$ dapat dibuktikan benar, dan (ii) $P_{k+1}$ pasti benar asalkan $P_m, P_{m+1},…, P_k$ semuanya benar untuk setiap $k ≥ m$, maka $P_n$ benar untuk semua $n \ge m$.

          Perhatikan bahwa tampaknya lebih sulit untuk menggunakan induksi kedua, karena memerlukan lebih banyak kondisi. Namun, sebenarnya tidak demikian. Kita dapat menggunakan salah satunya dengan bebas jika diperlukan.

Variasi Induksi Matematika

  1. Untuk membuktikan setiap $P_n, n = 1, 2,…,$ kita dapat membuktikan $P_n,k = 1, 2,…$ pertama dengan induksi, dan kemudian membuktikan $P_n$ untuk setiap $n$.
  2. Untuk membuktikan $\{P_n, n ∈ \mathbb{N}\}$ dengan induksi, terkadang lebih mudah untuk membuktikan proposisi $P’_n$ yang lebih kuat.
  3. Untuk membuktikan $\{P_n, n ≥ n_0\}$ dengan induksi, terkadang lebih mudah untuk membuktikan $P_n$ dengan induksi yang dimulai dari $n = n_1 > n_0$.
  4. Induksi dapat dilakukan secara terbalik: (i) Buktikan terlebih dahulu setiap proposisi dalam subsekuen $\{P_{n_e},k ∈\mathbb{N}\}$, kemudian (ii) buktikan bahwa $P_k$ benar dengan syarat $P_{k+1}$ benar.
  5. Induksi Aktif Silang (atau Spiral): Untuk membuktikan proposisi $P_n,n=
    0, 1,2,…$ dan $Q_n, n = 0, 1, 2,…,$ cukup dengan menunjukkan bahwa (i) $P_o$ dan $Q_o$ benar; (ii) Jika $P_k, Q_k$ benar, maka $P_k ⇒ Q_{k+1} ⇒ P_{k+1}⇒P_{k+1}$.
  6. Induksi Berganda: Misalkan $\{P_{n,m},n,m ∈ \mathbb{N}\}$ adalah deret proposisi dengan dua parameter independen $n$ dan $m$. Jika (i) $P_{1,m}$ benar untuk semua $m \in\mathbb{N}$ dan $P_{n,1}$ benar untuk semua $n ∈ \mathbb{N}$; (ii) $P_{n+1,m+1}$ benar asalkan $P_{n,m+1}$ dan $P_{n+1,m}$ benar, maka $P_{n,m}$ benar untuk setiap $n, m ∈ \mathbb{N}$.

Contoh Soal

  1. Buktikan dengan induksi bahwa $1^3+2^3+…+n^3=\frac{n^2(n+1)^2}{4}$ untuk setiap $n\in \mathbb{N}$. Dengan demikian buktikan bahwa $1^3+3^3+5^3+…+(2n-1)^3=n^2(2n^2-1)$ untuk setiap $n\in \mathbb{N}$.
    Solusi: Misalkan $P_n$ menjadi pernyataan $$1^3+2^3+…+n^3=\frac{n^2(n+1)^2}{4},\text{ }\text{ }\text{ }n=1,2,….$$ Untuk $n=1$, sisi kiri $=1=\frac{1^2(1+1)^2}{4}=$ sisi kanan, $P_1$ terbukti.
    Asumsikan bahwa $P_k$ benar $(k\ge 1)$, yaitu $1^3+2^3+…+k^3=\frac{k^2(k+1)^2}{4}$, maka untuk $n=k+1$, $$1^3+2^3+…+(k+1)^3=1^3+2^3+…+k^3+(k+1)^3$$ $$=\frac{k^2(k+1)^2}{4}+(k+1)^3=\frac{(k+1)^2}{4}\cdot [k^2+4(k+1)]=\frac{(k+1)^2(k+2)^2}{4}.$$ Maka, $P_{k+1}$ adalah benar. Dengan induksi, $P_n$ benar untuk setiap $n\in\mathbb{N}$.
    Sekarang untuk bilangn positif integer $n$, $$1^3+3^3+…+ (2n – 1)^3 =1^3+2^3+…+ (2n)^3 -(2^3 + 4^3 + …+ (2n)^3)$$ $$=\left[\frac{(2n)(2n+1)}{2}\right]^2-2^3(1^3+2^3+…+n^3)=n^2(2n+1)^2-8\cdot \frac{n^2(n+1)^2}{4}$$ $$=n^2(2n+1)^2-2n^2(n+1)^2=n^2[(2n+1)^2-2(n+1)^2]=n^2(2n^2-1),$$ seperti yang diinginkan.
  2. $\{a_n\}$ adalah deret bilangan riil yang memenuhi $a_0 ≠ 0, 1, a_1 = 1-a_0, a_{n+1} = 1-a_n(1-a_n)$ untuk semua $n ∈ \mathbb{N}$. Buktikan bahwa untuk sembarang bilangan bulat positif $n$, $$a_0a_1\cdots a_n\left(\frac{1}{a_0}+\frac{1}{a_1}+…+\frac{1}{a_n}\right)=1.$$ 
    Solusi: Kondisi yang diberikan menghasilkan $1-a_{n+1}=a_n(1-a_n),n\in \mathbb{N}_0$, maka $1-a_{n+1}=a_na_n{n-1}(1-a_{n-1})=…=a_n\cdots a_1(1-a_1)=a_n\cdots a_1a_0$, yaitu $$a_{n+1}=1-a_0a_1\cdots a_n,\text{ }\text{ }\text{ }n=1,2,…..$$ Sekarang kita buktikan kesimpulan awal dengan induksi. 
    Untuk $n=1,a_0a_1\left(\frac{1}{a_0}+\frac{1}{a_1}\right)=a_0+a_1=1$, kesimpulan nya terbukti.
    Asumsikan bahwa proporsi nya benar untuk $n=k$, maka untuk $n=k+1$, $$a_0a_1\cdots a_{k+1}\left(\frac{1}{a_0}+\frac{1}{a_1}+…+\frac{1}{a_{k+1}}\right)$$ $$=a_0a_1\cdots a_k\left(\frac{1}{a_0}+\frac{1}{a_1}+…+\frac{1}{a_k}\right)a_{k+1}+a_0a_1\cdots a_k$$ $$=a_{k+1}+a_0a_1\cdots a_k=1.$$ Maka, proporsi benar untuk $n=k+1$ juga. Dengan induksi, kesimpulan nya benar untuk semua $n\in \mathbb{N}$.
  3. Urutan bilangan real $a_o, a_1, a_2,…$ didefinisikan secara rekursif oleh $$a_0=-1,\text{ }\text{ }\text{ }\sum_{k=0}^{n}\frac{a_{n-k}}{k+1}=0\text{ untuk }n\ge 1.$$ Tunjukkan bahwa $a_n>0$ untuk $n\ge 1$.
    Solusi: Pembuktiannya dilakukan secara induksi pada $n$. Untuk $n = 1$, rumus menghasilkan $a_1 = 1/2$. Misalkan $n ≥ 1$ dan asumsikan $a_1,…, a_n > 0$. Tulis rumus rekursif untuk $n$ dan $n + 1$ berturut-turut sebagai $$\sum_{k=0}^{n}\frac{a_k}{n-k+1}=0\text{ dan }\sum_{k=0}^{n+1}\frac{a_k}{n-k+2}=0.$$ Hasil pengurangan $$0=(n+2)\sum_{k=0}^{n+1}\frac{a_k}{n-k+2}-(n+1)\sum_{k=0}^{n}\frac{a_k}{n-k+1}$$ $$=(n+2)a_{n+1}+\sum_{k=0}^{n}\left( \frac{n+2}{n-k+2}-\frac{n+1}{n-k+1} \right)a_k.$$ Koefisien $a_o$ hilang, jadi $$a_{n+1}=-\frac{1}{n+2}\sum_{k=1}^{n}\left( \frac{n+2}{n-k+2}-\frac{n+1}{n-k+1} \right)a_k$$ $$=\frac{1}{n+2}\sum_{k=1}^{n}\frac{k}{(n-k+1)(n-k+2)}a_k.$$ Koefisien $a_1,…, a_n$ semuanya positif. Oleh karena itu, $a_1,…, a_n > 0$ menyiratkan $a_{n+1} > 0$.
  4. Jika $0 < x_1 ≤ x_2 ≤… ≤ x_s, 0 < y_1 \le y_2 ≤… ≤ y_s$ memenuhi syarat bahwa $$x_1^r+x_2^r+…+x_s^r=y_1+y_2^r+…+y_s^r,\text{ untuk semua }r\in \mathbb{N},$$ buktikan bahwa $x_i=y_i,i=1,2,…,s$.
    Solusi: Kita buktikan dengan induksi pada $s$. Misalkan $P_s, s = 1, 2,…$ adalah pernyataan yang harus dibuktikan.
    Untuk $s = 1$, dengan mengambil $r = 1$ menghasilkan $x_1 = y_1$. Asumsikan bahwa $P_s$ benar untuk $s = k
    (k ≥ 1)$ yaitu, $$x_1=y_1,x_2=y_2,…,x_k=y_k.$$ maka untuk $s = k +1$, jika $x_{k+1} ≠ y_{k+1}$, tanpa kehilangan keumuman, kita asumsikan bahwa $x_{k+1} < y_{k+1}$. Maka $$\left( \frac{x_1}{y_{k+1}} \right)^r+…+\left( \frac{x_{k+1}}{y_{k+1}} \right)^r=\left( \frac{y_1}{y_{k+1}} \right)^r+…+\left( \frac{y_k}{y_{k+1}} \right)^r+1\ge 1.$$ Namun di sisi lain, karena $0 <\frac{x_i}{y_{k+1}}< 1, i = 1, 2,…, k+1$, misalkan $r →+∞$ menghasilkan $0 ≥ 1$, sebuah kontradiksi. Oleh karena itu, $x_{k+1} = y{k+1}$, maka asumsi induktif menyiratkan bahwa $x_i = y_i,i= 1, 2,…, k$. Dengan demikian, $P_{k+1}$ juga benar. Dengan induksi, $P_s$ benar untuk setiap $s \in\mathbb{N}$.
  5. (Pertidaksamaan AM-GM) Untuk bilangan riil $a_1,a_2,…,a_n > 0$, buktikan bahwa $$a_1+a_2+…+a_n\ge n\cdot \sqrt[n]{a_1a_2\cdots a_n},\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(✱)$$ dan kesetaraan itu berlaku jika dan hanya jika $a_1 = a_2 =\cdots = a_n$.
    Solusi: Pertama-tama kita buktikan $(*)$ untuk $n = 2^t ∈\mathbb{N}$ dengan induksi pada $t$.
    Ketika $t = 1, (*)\Leftrightarrow (\sqrt{a_1}- \sqrt{a_2})^2 ≥ 0$, jadi itu benar.
    Misalkan $(*)$ benar untuk $t = k$, maka untuk $t = k + 1$, dengan asumsi induksi, $$\sum_{j=1}^{2^{k+1}}a_j=\sum_{j=1}^{2^{k}}a_j+\sum_{j=1}^{2^{k}}a_{j+2^k}\ge 2^k\text{ }\text{ }\sqrt[2^k]{\prod_{j=1}^{2^k}a_j+2^k}\cdot \text{ }\text{ }\sqrt[2^k]{\prod_{j=1}^{2^k}a_{j+2^k}}$$ $$\ge 2^k\cdot 2\cdot \text{ }\text{ }\text{ }\sqrt[2^{k+1}]{\prod_{j=1}^{2^{k+1}}a_j}\text{ }\text{ }\text{ }=2^{k+1}\cdot \text{ }\text{ }\sqrt[2^{k+1}]{\prod_{j=1}^{2^{k+1}}a_j}$$ Dengan demikian, proposisi tersebut terbukti untuk $t = k + 1$. Dengan induksi, $(*)$ terbukti untuk semua $n = 2^t ,t= 1, 2,….$
    Selanjutnya, kita buktikan $(*)$ untuk setiap $n \in \mathbb{N}$. Untuk setiap $n ∈ \mathbb{N}$ yang bukan berbentuk $2^t$ terdapat $s ∈\mathbb{N}$ sedemikian rupa sehingga $2^{s-1} < n < 2^s$. Karena $$a_1+a_2+…+a_{2^s}\ge 2^s\cdot \sqrt[2^s]{a_1a_2\cdots a_{2^s}},\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(**)$$ Misalkan $a_{n+1}=a_{n+2}=\cdots =a_{2^s}=\sqrt[n]{a_1a_2\cdots a_n}$ pada $(**),(**)$ menghasilkan $$a_1+a_2+…+a_N+(2^s-n)\sqrt[n]{a_1a_2\cdots a_n}$$ $$\ge 2^s\cdot \text{ }\text{ }\text{ }\sqrt[2^s]{(a_1a_2\cdots a_n)(a_1a_2\cdots a_n)\frac{2^s-n}{n}}=2^s\cdot \text{ }\text{ }\text{ }\sqrt[n]{a_1a_2\cdots a_n},$$ $$∴a_1 +a_2+…+ a_n ≥n\cdot \text{ }\text{ }\sqrt[n]{a_1a_2\cdots a_n},$$ maka $(*)$ terbukti untuk $n\in \mathbb{N}$ umum.
  6. Untuk setiap bilangan bulat positif $n > 1$, buktikan bahwa $$\frac{2n}{3n+1}<\frac{1}{n+1}+\frac{1}{n+2}+…+\frac{1}{n+n}<\frac{25}{36}.$$ 
    Solusi: Untuk membuktikan ketidaksetaraan kiri, definisikan $$f(n)=\frac{1}{n+1}+\frac{1}{n+2}+…+\frac{1}{n+n}-\frac{2n}{3n+1},\text{ }\text{ }\text{ }n\in\mathbb{N}.$$ Maka $$f(n+1)=\frac{1}{n+2}+\frac{1}{n+3}+…+\frac{1}{2n+2}-\frac{2n+2}{3n+4},$$ jadi $$f(n+1)-f(n)=\left(\frac{1}{2n+1}-\frac{1}{2n+2}\right)+\left(\frac{2n}{3n+1}-\frac{2n+2}{3n+4}\right)$$ $$=\frac{1}{(2n+1)(2n+2)}-\frac{2}{(3n+1)(3n+4)}$$ $$=\frac{n(n+3)}{(2n+1)(2n+2)(3n+1)(3n+4)}>0,$$ yaitu, $f(n)$ adalah fungsi yang meningkat dari $n$. Jadi, untuk $n ≥ 2$, $$f(n)\ge f(2)=\frac{1}{3}+\frac{1}{4}-\frac{4}{7}=\frac{1}{84}>0,$$ ketidaksetaraan kiri terbukti.
    Di bawah ini kita akan membuktikan pertidaksamaan yang tepat dengan membuktikan pertidaksamaan yang lebih kuat melalui induksi. Misalkan proposisi $P_n, n ≥ 2$ adalah $$\frac{1}{n+1}+\frac{1}{n+2}+…+\frac{1}{n+n}<\frac{25}{36}-\frac{1}{4n+1}.$$ Ketika $n=2$, sisi kiri pada $P_2$ adalah $\frac{1}{3}+\frac{1}{4}=\frac{7}{12}$, dan sisi kanan nya adalah $\frac{25}{36}-\frac{1}{9}=\frac{7}{12}$, maka $P_2$ benar. Asumsikan $P_n$ adalah benar untuk $n=k(k\ge 2)$ yaitu, $$\frac{1}{k+1}+\frac{1}{k+2}+…+\frac{1}{k+k}<\frac{25}{36}-\frac{1}{4k+1}.$$ Maka untuk $n=k+1$, sisi kiri pada $P_{k+1}$ adalah $$\frac{1}{k+2}+…+\frac{1}{2k+2}=\frac{1}{k+1}+…+\frac{1}{2k+1}-\frac{1}{2k+2}$$ $$\le \frac{25}{36}-\frac{1}{4k+1}+\frac{1}{2k+1}-\frac{1}{2k+2}$$ $$=\frac{25}{36}-\frac{1}{4k+5}+\frac{1}{4k+5}-\frac{1}{4k+1}+\frac{1}{2k+1}-\frac{1}{2k+2}.$$ Karena $$\frac{1}{4k+5}-\frac{1}{4k+1}+\frac{1}{2k+1}-\frac{1}{2k+2}=-\frac{3}{(2k+1)(2k+2)(4k+1)(4k+5)}<0,$$ oleh karena itu $$\frac{1}{k+2}+…+\frac{1}{2k+2}<\frac{25}{36}-\frac{1}{4k+5}.$$ Maka, $P_{k+1}$ benar. Pembuktian induktif telah selesai.
  7. Misalkan $a_1, a_2,…, a_n,…$ adalah bilangan real dengan $0 ≤ a_i; ≤1$ untuk $i = 1, 2,…$ Buktikan bahwa untuk setiap $n ≥ 2$, $$\sum_{i=1}^{n}\frac{1}{1+a_i}\le \frac{n}{1+\sqrt[n]{a_1a_2\cdots a_n}}\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(*)$$ 
    Solusi: Sebagai langkah pertama, kita buktikan kesimpulan untuk semua $n$ dengan bentuk $2^m$ dengan induksi pada $m$. Untuk $m = 1$, pertidaksamaan $(*)$ menjadi $$\frac{1}{1-a_1}+\frac{1}{1+a_2}\le \frac{2}{1+\sqrt{a_1a_2}}$$ atau setara: $$2(1+ a_1)(1 + a_2) ≥ (2+ a_1 + a_2)(\sqrt{a_1a_2} +1),$$ $$a_1 +a_2+2a_1a_2 ≥ (2 + a_1 + a_2)\sqrt{а_1а_2},$$ $$(a_1 + a_2)(1- \sqrt{а_1а_2}) -2\sqrt{a_1a_2}(1- \sqrt{a_1a_2}) ≥0,$$ $$(\sqrt{a_1}-\sqrt{a_2})^2(1-\sqrt{a_1a_2})\ge 0.$$ Oleh karena itu, kesimpulannya benar. Asumsikan bahwa untuk $m = k (k > 1)$, kesimpulannya benar, yaitu: $$\sum_{i=1}^{2^k}\frac{1}{1+a_1}\le \frac{2^k}{1+\sqrt[2^k]{a_1a_2\cdots a_{2^k}}}$$ Maka, untuk $m=k+1$ $$\sum_{i=1}^{2^{k+1}}\frac{1}{1+a_i}=\sum_{i=1}^{2^k}\left( \frac{1}{1+a_{2i-1}}+\frac{1}{1+a_{2i}} \right)\le 2\sum_{i=1}^{2^k}\frac{1}{1+\sqrt{a_{2i-1}a_{2i}}}$$ $$\le 2\cdot \frac{2^k}{1+\sqrt[2^k]{\sqrt{a_1a_2}\sqrt{a_3a_4}\cdots \sqrt{a_{2^{k+1}-1}a_{2^{k+1}}}}}$$ $$=\frac{2^{k+1}}{1+\sqrt[2^{k+1}]{a_1a_2\cdots a_{2^{k+1}}}}.$$ Oleh karena itu kesimpulannya benar untuk semua $n = 2^m m\in \mathbb{N}$.
    Selanjutnya, untuk menunjukkan bahwa $(*)$ benar untuk semua $n ∈ \mathbb{N}$, cukup dengan menunjukkan bahwa $(*)$
    benar untuk $n = k – 1 (k ≥ 2)$ jika $(*)$ benar untuk $n = k$. Faktanya, dengan membiarkan $a_k = \sqrt[k-1]{a_1a_2\cdots a_{k-1}}$, kita memperoleh $$\sum_{i=1}^{k-1}\frac{1}{1+a_1}+\frac{1}{1+\sqrt[k-1]{a_1a_2\cdots a_{k-1}}}$$ $$\le \frac{k}{1+\sqrt[k]{a_1a_2\cdots a_{k-1}\cdot \sqrt[k-1]{a_1a_2\cdots a_{k-1}}}}=\frac{k}{1+\sqrt[k-1]{a_1a_2\cdots a_{k-1}}} \text{ },$$ oleh karena itu kita punya $$\sum_{i=1}^{k-1}\frac{1}{1+a_i}\le \frac{k-1}{1+\sqrt[k-1]{a_1a_2\cdots a_{k-1}}}\text{ }.$$ Dengan induksi mundur, $(*)$ berlaku untuk setiap $n\in\mathbb{N}$.
  8. Misalkan $\{F_n\}, n ∈ \mathbb{N}$ adalah deret Fibonacci. Buktikan bahwa $F_{n-1}^2+F_n^2=
    F_{2n+1}$ untuk setiap $n ∈ \mathbb{N}$.
    Solusi: Misalkan $P_n:F_{n+1}^2+F_n^2=F_{2n+1}, Q_n:2F_{n+1}F_n+F_{n+1}^2=F_{2n+2}$ untuk $n=1,2,…$
    Ketika $n=1$, maka $P_1,Q_1$ jelas karena itu $F_1=F_2=1$.
    Ketika $P_k,Q_k$ adalah benar untuk $n=k(k\ge 1)$, yaitu $F_{k+1}^2+F_k^2=2F_{2k+1}$ dan $2F_{k+1}F_k+F_{k+1}^2=F_{2k+2}$, maka $$F_{k+2}^2+F_{k+1}^2=(F_{k+1}+F_k)^2+F_{k+1}^2$$ $$=(F_{k+1}^2+2F_{k+1}F_k)+(F_k^2+F_{k+1}^2)$$ $$=F_{2k+2}+F_{2k+1}=F_{2k+3}=F_{2(k+1)+1},$$ yaitu, $P_{k+1}$ benar. Lebih jauh, $P_{k+1}$ dan $Q_k$ benar menghasilkan $$2F_{k+2}F_{k+1}+F_{k+2}^2=2(F_{k+1}+F_k)F_{k+1}+F_{k+2}^2$$ $$=(F_{k+1}^2+F_{k+2}^2)+(F_{k+1}^2+2F_{k+1}F_k)$$ $$F_{2k+3}+F_{2k+2}=F_{2k+4}=F_{2(k+1)+2},$$ yaitu $Q_{k+1}$ benar. Dengan induksi aktif silang, $P_r, Q_n$ berlaku untuk setiap $n\in\mathbb{N}$.

  9. $m$ kotak disusun dalam satu baris. Buktikan bahwa ada $\frac{(n+m-1)!}{n!(m-1)!}$ cara berbeda untuk memasukkan $n$ bola identik ke dalam kotak-kotak ini.
    Solusi: Dengan $F(n, m)$ kita menyatakan banyaknya cara memasukkan $n$ bola identik ke dalam $m$ kotak. Proposisi yang harus dibuktikan adalah $$F(n,m)=\frac{(n+m-1)!}{n!(m-1)!}$$ untuk $n,m\in\mathbb{N}$.
    Untuk $n=1$, kita memiliki $F(1,m)=m=\frac{m!}{(m-1)!}$, oleh karena itu, kesimpulannya benar untuk $n = 1$ dan semua $m ∈ \mathbb{N}$. Untuk $m = 1$ dan setiap $n∈\mathbb{N}$, kita memiliki $F(n, 1) = 1 =\frac{n!}{n!}$, oleh karena itu, kesimpulannya benar untuk $m = 1$ dan semua $n∈\mathbb{N}$.
    Misalkan $F(n+1,m)=\frac{(n+m)!}{(n+1)!(m-1)!}$ dan $F(n,m+1)=\frac{(n+m)!}{n!m!}$. Untuk mengevaluasi $F(n+1, m+1)$, dengan mempertimbangkan apakah jumlah bola di kotak $m+1$ adalah $0$ atau lebih besar dari $0$, kita memiliki $$F(n+1,m+1)$$ $$=F(n+1,m)+F(n,m+1)=\frac{(n+m)!}{(n+1)!(m-1)!}+\frac{(n+m)!}{n!m!}$$ $$=\frac{(n+m)!(m+n+1)}{(n+1)!m!}=\frac{(m+n+1)!}{(n+1)!(m!)}=\frac{[(n+1)+(m+1)-1]!}{(n+1)!(m+1-1)!}.$$ Pembuktian induktif telah selesai.

Solusi dari setiap Permasalahan diberikan pada kelas online

“I have not failed. I’ve just found 10,000 ways that won’t work.”

Thomas A. Edison

Thomas A. Edison

Keranjang Belanja
Scroll to Top