Buktikan dengan prinsip induksi matematika bahwa semua bilangan asli n selalu berlaku: P n ​ ≡ n ≤ 2 n − 1 , untuk n ≥ 1

Pembahasan

Pembuktian menggunakan induksi matematika Akan di buktikan n = 1 adalah benar : P n ​ P 1 ​ ​ ≡ ≡ ≡ ≡ ​ n ≤ 2 n − 1 1 ≤ 2 1 − 1 1 ≤ 2 0 1 ≤ 1 → [ terbukti benar ] ​ Asumsikan n = k adalah pernyataan yang benar P n ​ P k ​ ​ ≡ ≡ ​ n ≤ 2 n − 1 k ≤ 2 k − 1 , k ≥ 1 → [ benar ] ​ Akan dibuktikann = k+1 adalah benar maka P n ​ P k + 1 ​ P k + 1 ​ ​ ≡ ≡ ≡ ​ n ≤ 2 n − 1 k + 1 ≤ 2 k − 1 + 1 k + 1 ≤ 2 k ​ Akan dibuktikan bermula dari pernyataan yang di asumsikan benar k ≤ 2 k − 1 k + 1 ≤ 2 k − 1 + 1 ≤ 2 k − 1 + k ≤ 2 k − 1 + 2 k − 1 ≤ 2 ⋅ 2 k − 1 ≤ 2 1 + k − 1 ≤ 2 k Jadi, k + 1 ≤ 2 k ​ karena k + 1 ​ ≤ ​ 2 k ​ sehinggan = k+1 terbukti benar. Jadi, terbukti bahwa semua bilangan asli n selalu berlaku : P n ​ ≡ n ≤ 2 n − 1 , untuk n ≥ 1