Misalkan diketahui barisan bilangan a 1 ​ , a 2 ​ , a 3 ​ , ..., dengan a 1 ​ = 2 , a 2 ​ = 5 , a 3 ​ = 8 , dan a n ​ = a n − 1 ​ + a n − 2 ​ + a n − 3 ​ . Buktikan bahwa a n ​ ≤ 2 n .

Pembahasan

Langkah 1. Akan dibuktikan benar untuk Oleh karenabernilai benar, maka benar untuk . Langkah 2. Andaikan benar untuk yaitu a 1 ​ ≤ 2 1 , a 2 ​ ≤ 2 2 , a 3 ​ ≤ 2 3 , ⋅ ⋅ ⋅ , a k –2 ​ ≤ 2 k –2 , a k –1 ​ ≤ 2 k –1 . Akan dibuktikan benar untuk , yaitu . Bukti: Dengan demikian terbukti . Oleh karena Langkah 1 dan Langkah 2 keduanya bernilai benar, maka terbukti bahwa .