Proposisi 3.12.
Untuk setiap bilangan bulat positif \(n\text{,}\) jumlah \(n\) bilangan bulat positif pertama adalah \(n(n+1)/2\text{,}\) i.e.,
\begin{equation*}
\sum_{i=1}^n i=\frac{n(n+1)}{2}.
\end{equation*}
Subbab 3.8 Pembuktian dengan Induksi
Pembahasan tentang rekursi dan induksi belum lengkap tanpa beberapa contoh wajib mengenai pembuktian dengan induksi. Kita mulai dengan contoh “Hello World”.
Dalam versi pertama bukti Proposisi 3.12, kita secara jelas mengidentifikasi pernyataan terbuka \(S_n\) dan menguraikan bukti dengan cermat menggunakan \(S_n\text{.}\) Seiring bertambahnya pengalaman Anda dalam menulis bukti dengan induksi, penguraian sejelas ini akan semakin tidak diperlukan, seperti yang akan Anda lihat dalam versi kedua bukti tersebut.
Bukti.
Misalkan \(n\) adalah bilangan bulat positif, dan misalkan \(S_n\) adalah pernyataan terbuka
\begin{equation*}
\sum_{i=1}^n i = \frac{n(n+1)}{2}.
\end{equation*}
Dengan induksi, kita akan membuktikan bahwa \(S_n\) benar untuk semua bilangan bulat positif. Pada kasus dasar, kita harus membuktikan bahwa \(S_1\) benar. Ketika \(n=1\text{,}\) ruas kiri \(S_n\) hanyalah \(1\text{,}\) sedangkan ruas kanannya bernilai \(1(1+1)/2=1\text{.}\) Oleh karena itu, \(S_1\) benar.
Selanjutnya, kita mengasumsikan bahwa untuk suatu bilangan bulat positif \(k\text{,}\) \(S_k\) benar. Artinya, kita mengasumsikan
\begin{equation*}
\sum_{i=1}^k i=\frac{k(k+1)}{2}.
\end{equation*}
Sekarang kita hendak membuktikan bahwa \(S_{k+1}\) benar, dimulai dengan meninjau ruas kiri \(S_{k+1}\text{.}\) Perhatikan bahwa
\begin{equation*}
\sum_{i=1}^{k+1}i=\left(\sum_{i=1}^k i\right) +(k+1)=
\frac{k(k+1)}{2}+(k+1),
\end{equation*}
karena hipotesis induksi bahwa \(S_k\) benar memberi kita rumus yang lebih sederhana untuk penjumlahan tersebut. Dengan melanjutkan sedikit perhitungan aljabar, kita memperoleh
\begin{equation*}
\frac{k(k+1)}{2}+(k+1)=\frac{k^2+3k+2}{2}=\frac{(k+1)(k+2)}{2}.
\end{equation*}
Oleh karena itu, \(S_{k+1}\) benar. Karena kita telah menunjukkan bahwa \(S_1\) benar dan bahwa untuk setiap bilangan bulat positif \(k\text{,}\) jika \(S_k\) benar, maka \(S_{k+1}\) benar, kita menyimpulkan bahwa \(S_n\) benar untuk semua bilangan bulat positif \(n\) berdasarkan Prinsip Induksi Matematika.
Sebelum melihat versi bukti yang lebih ringkas, mari kita bahas sejenak langkah-langkah utama dalam setiap bukti dengan induksi. Langkah pertama adalah kasus dasar, yaitu menunjukkan bahwa pernyataan terbuka \(S_1\) benar. (Perlu dicatat bahwa tidak ada yang istimewa pada \(1\) di sini. Jika kita hanya ingin membuktikan bahwa \(S_n\) benar untuk semua bilangan bulat \(n\geq 5\text{,}\) maka membuktikan bahwa \(S_5\) benar merupakan kasus dasar.) Ketika membuktikan kasus dasar, jika \(S_n\) berupa persamaan, kita tidak cukup hanya menuliskan \(S_1\) lalu beralih ke langkah berikutnya. Kita perlu membuktikan bahwa \(S_1\) benar. Perhatikan bahwa dalam bukti di atas, kita membahas ruas kiri \(S_1\) dan ruas kanan \(S_1\text{,}\) lalu menyimpulkan bahwa keduanya sama.
Setelah kasus dasar, terdapat langkah induksi. Pada langkah ini, kita mengasumsikan bahwa \(S_k\) benar untuk suatu bilangan bulat positif \(k\) dan membuktikan bahwa \(S_{k+1}\) benar. Dalam proses ini, \(S_k\) disebut hipotesis induksi. Pada langkah induksi, kesalahan yang paling sering dilakukan mahasiswa adalah memulai dengan keseluruhan \(S_{k+1}\) lalu memanipulasinya hingga memperoleh pernyataan yang benar. Cara ini berbahaya karena kita dapat memulai dengan sesuatu yang salah dan, melalui langkah-langkah aljabar yang sah, memperoleh pernyataan yang benar. Pilihan terbaik adalah bekerja seperti pada kasus dasar: jika \(S_{k+1}\) berupa persamaan atau pertidaksamaan, olah salah satu ruas hingga menemukan tempat untuk menerapkan hipotesis induksi, kemudian lanjutkan hingga memperoleh ruas lainnya. Jika perhitungan aljabarnya menjadi rumit, Anda juga dapat mengolah ruas kiri \(S_{k+1}\) dan, secara terpisah, ruas kanan \(S_{k+1}\text{.}\) Jika Anda berhasil mengubah kedua ruas menjadi bentuk yang sama, berarti Anda telah menunjukkan bahwa keduanya sama dan \(S_{k+1}\) benar.
Sekarang mari kita lihat bukti Proposisi 3.12 yang lebih ringkas. Mulai saat ini, kita akan menggunakan gaya ini ketika menyajikan bukti dengan induksi. Ketika Anda baru mulai mempelajari bukti induksi, mungkin akan lebih membantu jika langkah-langkahnya ditulis lebih terperinci seperti dalam bukti pertama di atas.
Bukti.
Pertama, kita membuktikan pernyataan tersebut ketika \(n=1\text{.}\) Untuk nilai \(n\) ini, ruas kiri hanyalah \(1\text{,}\) sedangkan ruas kanan bernilai \(1(1+1)/2=1\text{.}\)
Sekarang asumsikan bahwa untuk suatu bilangan bulat positif \(k\text{,}\) rumus tersebut berlaku ketika \(n=k\text{,}\) i.e., asumsikan bahwa
\begin{equation*}
\sum_{i=1}^k i=\frac{k(k+1)}{2}.
\end{equation*}
Dengan demikian, diperoleh
\begin{equation*}
\sum_{i=1}^{k+1}i=\left(\sum_{i=1}^k i\right) +(k+1)=
\frac{k(k+1)}{2}+(k+1)=\frac{k^2+3k+2}{2}=\frac{(k+1)(k+2)}{2}.
\end{equation*}
Jadi, rumus tersebut juga berlaku ketika \(n=k+1\text{.}\) Berdasarkan Prinsip Induksi Matematika, rumus tersebut berlaku untuk semua bilangan bulat positif \(n\text{.}\)
Argumen-argumen sebelumnya 100% benar… tetapi sebagian matematikawan kombinatorial mungkin berpendapat bahwa argumen tersebut justru menyembunyikan apa yang sebenarnya terjadi. Mereka jauh lebih menyukai bukti kombinatorial, seperti yang diberikan dalam Subbab 2.4. Menurut kami, Anda sebaiknya memilih bukti kombinatorial—jika dapat menemukannya. Namun, jika diperlukan, Anda harus mampu memberikan bukti formal dengan induksi matematika.
Berikut contoh kedua, yang juga sangat klasik. Ingat kembali bahwa kita telah memberikan bukti kombinatorial pada bab sebelumnya. Saat membaca bukti ini, pastikan Anda dapat mengidentifikasi pernyataan terbuka \(S_n\text{,}\) kasus dasar, dan langkah induksi.
Proposisi 3.13.
Untuk setiap bilangan bulat positif \(n\text{,}\) jumlah \(n\) bilangan bulat positif ganjil pertama adalah \(n^2\text{,}\) i.e.,
\begin{equation*}
\sum_{i=1}^n (2i-1)= n^2.
\end{equation*}
Bukti.
Kita akan membuktikannya dengan induksi. Pertama, perhatikan bahwa rumus tersebut berlaku ketika \(n=1\text{.}\) Sekarang, misalkan \(k\) adalah bilangan bulat positif dan rumus tersebut berlaku ketika \(n=k\text{,}\) i.e., asumsikan
\begin{equation*}
\sum_{i=1}^k (2i-1)= k^2.
\end{equation*}
Maka
\begin{equation*}
\sum_{i=1}^{k+1}(2i-1)=\left(\sum_{i=1}^k (2i-1)\right)+2k+1=
k^2+(2k+1)=(k+1)^2.
\end{equation*}
Oleh karena itu, proposisi tersebut terbukti berdasarkan Prinsip Induksi Matematika.
Berikut versi yang lebih umum dari hasil pertama dalam bagian ini. Sekali lagi, perlu diingat bahwa kita telah memberikan bukti kombinatorial dalam Subbab 2.4.
Proposisi 3.14.
Misalkan \(n\) dan \(k\) adalah bilangan bulat tak negatif dengan \(n\ge k\text{.}\) Maka
\begin{equation*}
\sum_{i=k}^n \binom{i}{k}=\binom{n+1}{k+1}.
\end{equation*}
Bukti.
Tetapkan \(k\) sebagai bilangan bulat tak negatif. Selanjutnya, kita membuktikan rumus tersebut dengan induksi terhadap \(n\text{.}\) Jika \(n=k\text{,}\) perhatikan bahwa ruas kiri hanyalah \(\binom{k}{k}=1\text{,}\) sedangkan ruas kanan adalah \(\binom{k+1}{k+1}\text{,}\) yang juga bernilai \(1\text{.}\) Sekarang, asumsikan bahwa \(m\) adalah bilangan bulat tak negatif dengan \(m\ge k\text{,}\) dan rumus tersebut berlaku ketika \(n=m\text{,}\) i.e., asumsikan bahwa
\begin{equation*}
\sum_{i=k}^m \binom{i}{k}=\binom{m+1}{k+1}.
\end{equation*}
Maka
\begin{align*}
\sum_{i=k}^{m+1}\binom{i}{k} \amp = \sum_{i=k}^{m}\binom{i}{k} +\binom{m+1}{k}\\
\amp =\binom{m+1}{k+1}+\binom{m+1}{k}\\
\amp =\binom{m+2}{k+1}.
\end{align*}
Oleh karena itu, proposisi tersebut terbukti berdasarkan Prinsip Induksi Matematika.
