Gunakan induksi matematik untuk membuktikan bahwa suatu himpunan dengan n

Berikut ini adalah pertanyaan dari regisiregar1401 pada mata pelajaran Matematika untuk jenjang Sekolah Menengah Atas

Gunakan induksi matematik untuk membuktikan bahwa suatu himpunan dengan n buah elemen (n ≥ 3) mempunyai n(n-1)(n-2)/6 himpunan bagian yang mengandung tepat 3 buah elemen. shultikan bahwa

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

Jawaban: (pada uraian di bawah ini)
 

Pembahasan

Induksi Matematika dan Himpunan

Pernyataan yang ingin dibuktikan:

“Suatu himpunan dengan n buah elemen (n ≥ 3) mempunyai n(n-1)(n-2)/6 himpunan bagian yang mengandung tepat 3 buah elemen.”

PEMBUKTIAN

Basis Induksi

Himpunan $S$ dengan 3 buah elemen mengandung 1 himpunan bagian yang mengandung tepat 3 buah elemen.

$\begin{aligned}\frac{3(2)(1)}{6}=1\implies\textsf{benar!}\end{aligned}$

Langkah Induksi

Hipotesis (Asumsi): Andaikan benar bahwa suatu himpunan dengan $n$ buah elemen ( $n$ ≥ 3) mempunyai $n(n-1)(n-2)/6$ himpunan bagian yang mengandung tepat 3 buah elemen.

Kita harus membuktikan bahwa suatu himpunan dengan $n+1$ buah elemen ( $n$ ≥ 3) mempunyai $(n+1)(n)(n-1)/6$ atau $n(n-1)(n+1)/6$ himpunan bagian yang mengandung tepat 3 buah elemen.

Misalkan himpunan $S$ memiliki $n$ buah elemen, dan $X$ merupakan himpunan baru hasil penambahan sebuah elemen $x$ pada $S$ , dengan $x \not\in S$ . Maka: $X = S\cup\{x\}$ , dan $|X|=n+1$ .

Misalkan pula $P_k(M)$ menyatakan himpunan yang berisi himpunan-himpunan bagian dari sebuah himpunan $M$ yang mengandung tepat $k$ buah elemen. Jadi, $P_3(S)$ adalah himpunan yang berisi semua himpunan bagian dari $S$ yang mengandung tepat 3 buah elemen, dan $P_3(X)$ adalah himpunan yang berisi semua himpunan bagian dari $X$ yang mengandung tepat 3 buah elemen.

Karena penambahan elemen tunggal $x$ pada $S$ , maka pada $X$ akan terbentuk himpunan-himpunan bagian baru yang mengandung tepat 3 buah elemenselain yang sudah adapada $P_3(S)$ , yaitu union/gabungandari setiap elemen $P_2(S)$ (himpunan yang berisi himpunan-himpunan bagian dari S yang mengandung tepat 2 elemen) dengan {x}.

Banyaknya himpunan-himpunan bagian yang baru ini sama dengan banyaknya himpunan bagian dari S yang mengandung tepat 2 elemen.

Oleh karena itu:
$\begin{aligned}\left|P_3(X)\right|=\left|P_3(S)\right|+\left|P_2(S)\right|\quad...(\star)\end{aligned}$

Banyaknya himpunan bagian dari $S$ yang mengandung tepat 2 buah elemen dinyatakan oleh:
$\begin{aligned}\left|P_2(S)\right|=\frac{n(n-1)}{2}\end{aligned}$

Sebagai contoh:

$\begin{aligned}&S = \{1, 2\}\\&\implies P_2(S)=\left \{ \{1,2\} \right \}\\&\implies \left | P_2(S) \right |=\frac{2(1)}{2}=1\\&S = \{1, 2, 3\}\\&\implies P_2(S)=\left \{ \{1,2\},\{1,3\},\{2,3\} \right \}\\&\implies \left | P_2(S) \right |=\frac{3(2)}{2}=3\\&\textsf{dan seterusnya...}\end{aligned}$

Maka, menyelesaikan persamaan $(\star)$ :

$\begin{aligned}\left|P_3(X)\right|&=\left|P_3(S)\right|+\left|P_2(S)\right|\\&=\!\!\!\!\!\!\!\overbrace{\frac{n(n-1)(n-2)}{6}}^{\begin{array}{c}\textsf{dari asumsi/hipotesis}\end{array}}\!\!\!\!\!\!+\ \frac{n(n-1)}{2}\\&=\frac{n(n-1)(n-2)+3n(n-1)}{6}\\&=\frac{n(n-1)(n-2+3)}{6}\\\therefore\ \left|P_3(X)\right|&=\boxed{\:\bf\frac{n(n-1)(n+1)}{6}\:}\\\end{aligned}$

⇒ Terbukti benarbahwa suatu himpunan dengan $n+1$ buah elemen ( $n$ ≥ 3) mempunyai $(n+1)(n)(n-1)/6$ atau $n(n-1)(n+1)/6$ himpunan bagian yang mengandung tepat 3 buah elemen.
 

KESIMPULAN

Langkah basis dan langkah induksi telah ditunjukkan benar (terbukti).
Oleh karena itu, terbukti benar bahwa suatu himpunan dengan n buah elemen (n ≥ 3) mempunyai n(n-1)(n-2)/6 himpunan bagian yang mengandung tepat 3 buah elemen.

$\blacksquare$