generalized_fibonacci_closed-form.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) = 1
#   a(1) = 1
#   a(n) = x * a(n-1) + y * a(n-2)

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

func f(x, y, n) {
    ((pow(2, -n - 1) * (pow(x - sqrt(x**2 + 4*y), n)*(x-2) + sqrt(x**2 + 4*y)*pow(x - sqrt(x**2 + 4*y), n) - pow(sqrt(x**2 + 4*y) + x, n)*(x-2) + sqrt(x**2 + 4*y)*pow(sqrt(x**2 + 4*y) + x, n))) / sqrt(x**2 + 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, 2, 3, 5, 8, 13, 21, 34, 55, 89]
f(1,2) = [1, 3, 5, 11, 21, 43, 85, 171, 341, 683]
f(1,3) = [1, 4, 7, 19, 40, 97, 217, 508, 1159, 2683]
f(1,4) = [1, 5, 9, 29, 65, 181, 441, 1165, 2929, 7589]
f(1,5) = [1, 6, 11, 41, 96, 301, 781, 2286, 6191, 17621]
f(2,1) = [1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363]
f(2,2) = [1, 4, 10, 28, 76, 208, 568, 1552, 4240, 11584]
f(2,3) = [1, 5, 13, 41, 121, 365, 1093, 3281, 9841, 29525]
f(2,4) = [1, 6, 16, 56, 176, 576, 1856, 6016, 19456, 62976]
f(2,5) = [1, 7, 19, 73, 241, 847, 2899, 10033, 34561, 119287]
f(3,1) = [1, 4, 13, 43, 142, 469, 1549, 5116, 16897, 55807]
f(3,2) = [1, 5, 17, 61, 217, 773, 2753, 9805, 34921, 124373]
f(3,3) = [1, 6, 21, 81, 306, 1161, 4401, 16686, 63261, 239841]
f(3,4) = [1, 7, 25, 103, 409, 1639, 6553, 26215, 104857, 419431]
f(3,5) = [1, 8, 29, 127, 526, 2213, 9269, 38872, 162961, 683243]
f(4,1) = [1, 5, 21, 89, 377, 1597, 6765, 28657, 121393, 514229]
f(4,2) = [1, 6, 26, 116, 516, 2296, 10216, 45456, 202256, 899936]
f(4,3) = [1, 7, 31, 145, 673, 3127, 14527, 67489, 313537, 1456615]
f(4,4) = [1, 8, 36, 176, 848, 4096, 19776, 95488, 461056, 2226176]
f(4,5) = [1, 9, 41, 209, 1041, 5209, 26041, 130209, 651041, 3255209]
f(5,1) = [1, 6, 31, 161, 836, 4341, 22541, 117046, 607771, 3155901]
f(5,2) = [1, 7, 37, 199, 1069, 5743, 30853, 165751, 890461, 4783807]
f(5,3) = [1, 8, 43, 239, 1324, 7337, 40657, 225296, 1248451, 6918143]
f(5,4) = [1, 9, 49, 281, 1601, 9129, 52049, 296761, 1692001, 9647049]
f(5,5) = [1, 10, 55, 325, 1900, 11125, 65125, 381250, 2231875, 13065625]