Asumsi:
Yang dimaksud dengan “menentukan sebuah deret Fibonacci”adalah menentukan bilangan Fibonacci pertama beserta jumlahnya, dengan masukan/input ∈ bilangan asli.
Misalkan: n = 5, maka algoritma menghasilkan 1, 1, 2, 3, 5 dengan jumlah deret = 12.
______________

Pseudocode

Algoritma Deret Fibonacci (Iteratif)
Input: Bilangan bulat positif.
Output: n bilangan Fibonacci pertama, dan jumlahnya.

read n
jumlah ← 0
if n < 1 then
   print “n harus lebih dari atau sama dengan 1”
else if n = 1 then
   print 1   # bilangan Fibonacci
   print 1   # jumlah deret bilangan Fibonacci
else
   fib ← [1, 1]
   jumlah ← 2
   for i ← 3 to n, do
       fib[i] ← fib[i–1] + fib[i–2]
       jumlah ← jumlah + fib[i]
   print fib  # mencetak isi array fib
   print jumlah
______________

Pembuktian dengan Induksi Matematika

Sebelum membuktikan, kita perhatikan definisi barisan/deret bilangan Fibonacci.

Sepengetahuan saya, ada 2 versi dalam penjabaran bilangan Fibonacci, yaitu:

• Versi 1: dimulai dengan indeks 0, barisan = 0, 1, 1, 2, 3, 5, ...
• Versi 2: dimulai dengan indeks 1, barisan = 1, 1, 2, 3, 5, ...

Di sini saya gunakan versi 2, di mana bilangan Fibonacci ke-n dinyatakan oleh yang memenuhi definisi:

Maka, pembuktian terhadap blangan Fibonacci ke-n tidak perlu dilakukan, karena merupakan bagian dari definisinya.

Menurut saya, yang perlu dibuktikan adalah jumlah deret bilangan Fibonacci.

Penelusuran algoritma di atas dengan input n = 5 (tanpa eksekusi print) adalah sebagai berikut.

• fib = [1, 1], jumlah = 2
• i = 3: fib = [1, 1, 2], jumlah = 2+2 = 4
• i = 4: fib = [1, 1, 2, 3], jumlah = 4+3 = 7
• i = 5: fib = [1, 1, 2, 3, 5], jumlah = 7+5 = 12

Jika kita teruskan iterasinya tanpa menghitung jumlahnya, maka diperoleh:

• i = 6: fib = [1, 1, 2, 3, 5, 8]
• i = 7: fib = [1, 1, 2, 3, 5, 8, 13]

Jadi, jumlah 5 bilangan Fibonacci pertama, yaitu 12, sama dengan , atau dengan kata lain, sama dengan .

Jadi, pernyataan yang ingin dibuktikan adalah:

Jumlah deret n bilangan Fibonacci pertama dinyatakan oleh:

untuk ∈ bilangan asli.

Basis Induksi

Untuk :

Sesuai definisi, . Maka basis induksi terbukti benar.

Asumsi/Hipotesis

Untuk , diasumsikan benar bahwa:

Langkah Induksi

Berdasarkan asumsi tersebut dan definisi bilangan Fibonacci di atas, perlu dibuktikan bahwa untuk , berlaku:

Pembuktian Langkah Induksi:

⇒ Langkah induksi terbukti benar.

Kesimpulan

∴  Dengan induksi matematika, pernyataan bahwa jumlah deret bilangan Fibonacci pertama dinyatakan oleh:

untuk ∈ bilangan asli, terbukti benar.