Contoh 3.6.6.
Buktikan identitas
\begin{equation*}
1 n + 2(n-1) + 3 (n-2) + \cdots + (n-1) 2 + n 1 = \binom{n+2}{3}\text{.}
\end{equation*}
Penyelesaian.
Untuk memberikan pembuktian kombinatorial, kita perlu memikirkan pertanyaan yang dapat dijawab dengan dua cara: satu cara harus menghasilkan ruas kiri identitas, sedangkan cara lainnya harus menghasilkan ruas kanannya. Petunjuk untuk menentukan pertanyaan berasal dari ruas kanan: \(\binom{n+2}{3}\) menghitung banyaknya cara memilih 3 benda dari kelompok \(n+2\) benda. Mari namai benda-benda itu \(1, 2, 3, \ldots, n+2\text{.}\) Dengan kata lain, kita ingin menemukan subhimpunan 3-elemen dari bilangan-bilangan tersebut (karena urutan tidak penting, subhimpunan merupakan objek yang tepat untuk dipertimbangkan). Kita perlu sedikit cerdik untuk menjelaskan mengapa ruas kiri juga memberikan banyaknya subhimpunan ini. Berikut pembuktiannya.
Bukti.
Perhatikan pertanyaan “Ada berapa subhimpunan 3-elemen dari himpunan \(\{1,2,3,\ldots, n+2\}\text{?}\)” Kita menjawabnya dengan dua cara:
Jawaban 1: Kita harus memilih 3 elemen dari koleksi \(n+2\) elemen. Hal ini dapat dilakukan dalam \(\binom{n+2}{3}\) cara.
Jawaban 2: Bagi masalah ini menjadi kasus-kasus berdasarkan bilangan tengah dalam subhimpunan. Misalkan setiap subhimpunan ditulis sebagai \(\{a,b,c\}\) dalam urutan menaik. Kita menghitung banyaknya subhimpunan untuk setiap nilai \(b\) yang berbeda. Nilai terkecil yang mungkin bagi \(b\) adalah \(2\text{,}\) sedangkan yang terbesar adalah \(n+1\text{.}\)
Ketika \(b = 2\text{,}\) terdapat \(1 \cdot n\) subhimpunan: 1 pilihan untuk \(a\) dan \(n\) pilihan (3 hingga \(n+2\)) untuk \(c\text{.}\)
Ketika \(b = 3\text{,}\) terdapat \(2 \cdot (n-1)\) subhimpunan: 2 pilihan untuk \(a\) dan \(n-1\) pilihan untuk \(c\text{.}\)
Ketika \(b = 4\text{,}\) terdapat \(3 \cdot (n-2)\) subhimpunan: 3 pilihan untuk \(a\) dan \(n-2\) pilihan untuk \(c\text{.}\)
Demikian seterusnya. Ketika \(b = n+1\text{,}\) terdapat \(n\) pilihan untuk \(a\) dan hanya 1 pilihan untuk \(c\text{,}\) sehingga terdapat \(n \cdot 1\) subhimpunan.
Oleh karena itu, jumlah seluruh subhimpunan adalah
\begin{equation*}
1 n + 2 (n-1) + 3 (n-2) + \cdots + (n-1)2 + n 1\text{.}
\end{equation*}
Karena Jawaban 1 dan Jawaban 2 menjawab pertanyaan yang sama, keduanya harus sama. Oleh karena itu,
\begin{equation*}
1 n + 2 (n-1) + 3 (n-2) + \cdots + (n-1) 2 + n 1 = \binom{n+2}{3}\text{.}
\end{equation*}