Pembuktian dalam teori bilangan

Contoh pembuktian dalam teori bilangan yaitu:

Diketahui C(0) = 3,  C(1) = 7 dan
.
Tunjukkan bahwa C(n) = -1 + 4 (2^n) untuk semua n bilangan bulat ≥ 0.

Solusi :

C(0) = 3
C(1) = 7
C(n) = 3C(n-1) - 2C(n-2)
.
.
.
.
Untuk n =2 maka C(2) = 3C(1) - 2C(0)
                                     = 3.7 - 2.3
                                     = 21 - 6 = 15
untuk n = 3 maka C(3) = 3C(2) - 2C(1)
                                     = 3.15 - 2.7
                                     = 45 - 14 = 31
Pembuktian menggunakan prinsip induksi matematis maka kita harus menunjukkan
C(n) = 3C(n-1) - 2C(n-2) = C(n) = -1 + 4 (2^n) berlaku benar untuk n = k dan n = k+1.
.
.
C(k) = -1 + 4 (2^k)
.
.
C(k+1) = 3C(k) - 2C(k-1)
            = 3.(-1 + 4 (2^k)) - 2.(-1 + 4 (2^k-1))
            = -3 + 3.4(2^k) + 2 - 2.4(2^k-1)
            = -1 + 3.4(2^k) - 2.4(2^k-1)
            = -1 + 3.4(2^k) - 2.4(2^k/2)
            = -1 + 3.4(2^k) - 4(2^k)
            = -1 + 2.4(2^k)
            = -1 + 4.(2.2^k)
            = -1 + 4.(2^k+1)

Dengan demikian C(k+1) = -1 + 4.(2^k+1) terbukti benar