Contoh 3.6.5.
Buktikan identitas binomial \(\binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \cdots + \binom{n}{n} = 2^n\text{.}\)
Penyelesaian.
Mari kita kembali melakukan “pembuktian pizza”. Kita perlu menemukan pertanyaan tentang taburan pizza yang jawabannya \(2^n\text{.}\) Bagaimana dengan pertanyaan ini: jika sebuah kedai pizza menawarkan \(n\) taburan, ada berapa pizza yang dapat Anda buat dengan menggunakan sembarang banyak taburan, mulai dari tanpa taburan hingga semua taburan, dan menggunakan setiap taburan paling banyak sekali?
Di satu pihak, jawabannya adalah \(2^n\text{.}\) Untuk setiap taburan, Anda dapat mengatakan “ya” atau “tidak”, sehingga Anda memiliki dua pilihan untuk setiap taburan.
Di pihak lain, bagi semua pizza yang mungkin menjadi kelompok-kelompok saling lepas: pizza tanpa taburan, pizza dengan satu taburan, pizza dengan dua taburan, dan seterusnya. Jika kita tidak menginginkan taburan, hanya ada satu pizza seperti itu (pizza kosong, boleh dikatakan demikian), tetapi bilangan itu lebih baik dipandang sebagai \(\binom{n}{0}\) karena kita memilih 0 dari \(n\) taburan. Ada berapa pizza yang memiliki 1 taburan? Kita perlu memilih 1 dari \(n\) taburan, sehingga banyaknya adalah \(\binom{n}{1}\text{.}\) Kita memperoleh:
-
Pizza dengan 0 taburan: \(\binom{n}{0}\)
-
Pizza dengan 1 taburan: \(\binom{n}{1}\)
-
Pizza dengan 2 taburan: \(\binom{n}{2}\)
-
\(\displaystyle \vdots\)
-
Pizza dengan \(n\) taburan: \(\binom{n}{n}\text{.}\)
Jumlah seluruh pizza yang mungkin adalah penjumlahan bilangan-bilangan ini, yang tepat sama dengan ruas kiri identitas yang sedang kita buktikan.
Sekali lagi, kita dapat membuktikan identitas ini dengan menggunakan subhimpunan, string bit, atau lintasan kisi (meskipun argumen lintasan kisi sedikit rumit).