Untuk setiap bilangan asli. Misalkan n0 adalah bilangan

Pernyataan ini dapat dibuktikan menggunakan induksi matematika, dimulai dari basis n0 yang memenuhi kondisi awal dan membuktikan langkah induktif bahwa jika berlaku untuk k, maka berlaku juga untuk k+1.

Pembahasan

Untuk membuktikan bahwa n^2 ≤ 2^(n-1) berlaku untuk setiap n ≥ n0, di mana n0 adalah bilangan asli terkecil sehingga n0^2 ≤ 2^(n0-1), kita dapat menggunakan prinsip induksi matematika.

Langkah Dasar: Kita tahu bahwa n0 adalah bilangan asli terkecil yang memenuhi kondisi awal. Misalkan kita telah menemukan n0 = 1, karena 1^2 = 1 dan 2^(1-1) = 2^0 = 1, sehingga 1 ≤ 1 terpenuhi.

Langkah Induktif: Asumsikan bahwa pernyataan P(k): k^2 ≤ 2^(k-1) berlaku untuk suatu bilangan asli k ≥ n0.
Kita perlu membuktikan bahwa P(k+1): (k+1)^2 ≤ 2^k juga berlaku.

Dari asumsi induksi, kita punya k^2 ≤ 2^(k-1).
Kita tahu bahwa (k+1)^2 = k^2 + 2k + 1.
Kita juga tahu bahwa 2^k = 2 * 2^(k-1).

Karena k^2 ≤ 2^(k-1), maka 2^k ≥ 2k^2.
Kita perlu menunjukkan bahwa k^2 + 2k + 1 ≤ 2^k.

Karena k ≥ 1, maka k^2 + 2k + 1 ≤ k^2 + k^2 = 2k^2 (untuk k ≥ 1).
Jadi, jika k^2 ≤ 2^(k-1), maka k^2 + 2k + 1 ≤ 2k^2 ≤ 2^k.

Dengan demikian, berdasarkan prinsip induksi matematika, pernyataan n^2 ≤ 2^(n-1) berlaku untuk setiap n ≥ n0.