Materi
Induksi matematika adalah cara membuktikan bahwa pernyataan P(n) benar untuk setiap bilangan asli n mulai dari suatu nilai awal. Buktinya punya dua bagian. Kasus dasar: tunjukkan P benar untuk nilai awal, misalnya P(1). Langkah induksi: anggap P(k) benar untuk sembarang k (anggapan ini disebut hipotesis induksi), lalu tunjukkan bahwa P(k + 1) pasti ikut benar. Keduanya bersama-sama bekerja seperti relasi rekurensi: P(1) benar, maka P(2) benar, maka P(3) benar, dan seterusnya tanpa akhir. Kerangka logikanya adalah implikasi “jika P(k) maka P(k + 1)”, yang dibahas di kelas Penalaran Logis dan Analitis.
Contoh: buktikan 1 + 3 + 5 + … + (2n − 1) = n². Kasus dasar n = 1: ruas kiri 1, ruas kanan 1² = 1, sama. Langkah induksi: anggap 1 + 3 + … + (2k − 1) = k². Suku berikutnya adalah 2(k + 1) − 1 = 2k + 1, sehingga 1 + 3 + … + (2k − 1) + (2k + 1) = k² + 2k + 1 = (k + 1)², tepat P(k + 1). Karena kedua bagian terbukti, rumusnya benar untuk setiap n ≥ 1. Python dapat memeriksa rumus itu untuk ratusan nilai n, tetapi pemeriksaan sebanyak apa pun tetap bukan bukti untuk seluruh bilangan asli:
print(all(sum(range(1, 2 * n, 2)) == n * n for n in range(1, 501))) # True untuk 500 nilai