generalized_fibonacci_closed-form_2.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 21 December 2016
# https://github.com/trizen

# A closed-form for generalized Fibonacci numbers:
#   a(0) = 0
#   a(1) = 1
#   a(n) = x * a(n-1) + y * a(n-2)

# Solution:
#   a(n) = (2^(-n) * ((sqrt(x^2 + 4*y) + x)^n - (x - sqrt(x^2 + 4*y))^n)) / sqrt(x^2 + 4*y)

func f(x, y, n) {
    (pow(sqrt(x*x + 4*y) + x, n) - pow(x - sqrt(x*x + 4*y), n)) / 2**n / sqrt(x*x + 4*y)
}

for x,y in (1..5 ~X 1..5) {
    say ("f(#{x},#{y}) = ", 10.of { |n| f(x, y, n).round })
}

__END__
f(1,1) = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
f(1,2) = [1, 1, 3, 5, 11, 21, 43, 85, 171, 341]
f(1,3) = [1, 1, 4, 7, 19, 40, 97, 217, 508, 1159]
f(1,4) = [1, 1, 5, 9, 29, 65, 181, 441, 1165, 2929]
f(1,5) = [1, 1, 6, 11, 41, 96, 301, 781, 2286, 6191]
f(2,1) = [1, 2, 5, 12, 29, 70, 169, 408, 985, 2378]
f(2,2) = [1, 2, 6, 16, 44, 120, 328, 896, 2448, 6688]
f(2,3) = [1, 2, 7, 20, 61, 182, 547, 1640, 4921, 14762]
f(2,4) = [1, 2, 8, 24, 80, 256, 832, 2688, 8704, 28160]
f(2,5) = [1, 2, 9, 28, 101, 342, 1189, 4088, 14121, 48682]
f(3,1) = [1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837]
f(3,2) = [1, 3, 11, 39, 139, 495, 1763, 6279, 22363, 79647]
f(3,3) = [1, 3, 12, 45, 171, 648, 2457, 9315, 35316, 133893]
f(3,4) = [1, 3, 13, 51, 205, 819, 3277, 13107, 52429, 209715]
f(3,5) = [1, 3, 14, 57, 241, 1008, 4229, 17727, 74326, 311613]
f(4,1) = [1, 4, 17, 72, 305, 1292, 5473, 23184, 98209, 416020]
f(4,2) = [1, 4, 18, 80, 356, 1584, 7048, 31360, 139536, 620864]
f(4,3) = [1, 4, 19, 88, 409, 1900, 8827, 41008, 190513, 885076]
f(4,4) = [1, 4, 20, 96, 464, 2240, 10816, 52224, 252160, 1217536]
f(4,5) = [1, 4, 21, 104, 521, 2604, 13021, 65104, 325521, 1627604]
f(5,1) = [1, 5, 26, 135, 701, 3640, 18901, 98145, 509626, 2646275]
f(5,2) = [1, 5, 27, 145, 779, 4185, 22483, 120785, 648891, 3486025]
f(5,3) = [1, 5, 28, 155, 859, 4760, 26377, 146165, 809956, 4488275]
f(5,4) = [1, 5, 29, 165, 941, 5365, 30589, 174405, 994381, 5669525]
f(5,5) = [1, 5, 30, 175, 1025, 6000, 35125, 205625, 1203750, 7046875]