Latihan 21.
Gunakan induksi untuk membuktikan \({4 \choose 0} + {5 \choose 1} + {6 \choose 2} + \cdots + {4+n \choose n} = {5+n \choose n}\text{.}\) (Ini merupakan salah satu contoh teorema tongkat hoki.)
Petunjuk.
Untuk memahami mengapa ini benar, cobalah pada salinan segitiga Pascal. Kita menjumlahkan entri-entri sepanjang sebuah diagonal, dimulai dari 1 di sisi kiri baris ke-4. Misalkan kita menjumlahkan 5 entri pertama pada diagonal ini. Klaimnya adalah bahwa jumlah tersebut sama dengan entri di bawah dan di sebelah kiri entri terakhir dari kelima entri itu. Perhatikan bahwa jika klaim ini benar dan kemudian kita menjumlahkan 6 entri pertama, kita perlu menambahkan entri yang terletak satu posisi di sebelah kanan jumlah sebelumnya. Namun, kedua entri ini jika dijumlahkan menghasilkan entri di bawah keduanya, yang terletak di bawah dan di sebelah kiri entri terakhir dari keenam entri pada diagonal tersebut. Jika Anda mengikuti penjelasan itu, Anda dapat melihat apa yang terjadi. Namun, penjelasan tersebut belum merupakan pembuktian yang baik. Diperlukan pembuktian induksi formal.