OFFSET
0,8
COMMENTS
The definition declares the Fibonacci numbers for all integers n and k. An alternative version is A353595.
The identity F(n, k) = (-1)^k*F(1 - n, -k) holds for all integers n, k. Proof:
F(n, k)*(2+phi) = (phi^k*(n*phi + 1) - (-phi)^(-k)*((n-1)*phi - 1))
= (-1)^k*(phi^(-k)*((1-n)*phi+1) - (-phi)^k*(-n*phi-1))
= (-1)^k*F(1-n, -k)*(2+phi).
This identity can be seen as an extension of Cassini's theorem of 1680 and of an identity given by Graham, Knuth and Patashnik in 'Concrete Mathematics' (6.106 and 6.107). The beginning of the full array with arguments in Z x Z can be found in the linked note.
The enumeration is the result of the simple form of the chosen definition. The classical positive Fibonacci numbers starting with 1, 1, 2, 3,... are in row n = 1 with offset 0. The nonnegative Fibonacci numbers starting 0, 1, 1, 2, 3,... are in row 0 with offset 1. They prolong towards -infinity with an index shifted by 1 compared to the enumeration used by Knuth. A characteristic of our enumeration is F(n, 0) = 1 for all integer n.
Fibonacci numbers vanish only for (n,k) in {(-1,2), (0,1), (1,-1), (2,-2)}. The zeros correspond to the identities (phi + 1)*psi^2 = (psi + 1)*phi^2, psi*phi = phi*psi, (phi - 1)*phi = (psi - 1)*psi and (phi - 2)*phi^2 = (psi - 2)*psi^2.
For divisibility properties see A352747.
For any fixed k, the sequence F(n, k) is a linear function of n. In other words, an arithmetic progression. This implies that F(n+1, k) = 2*F(n, k) - F(n-1, k) for all n in Z. Special case of this is Fibonacci(n+1) = 2 *Fibonacci(n) - Fibonacci(n-2). - Michael Somos, May 08 2022
REFERENCES
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, sec. 6.6.
Donald Ervin Knuth, The Art of Computer Programming, Third Edition, Vol. 1, Fundamental Algorithms. Chapter 1.2.8 Fibonacci Numbers. Addison-Wesley, Reading, MA, 1997.
LINKS
Alexander Bogomolny, Cassini's Identity.
Edsger W. Dijkstra, In honour of Fibonacci, in: F. L. Bauer, M. Broy, & E. W. Dijkstra (editors), Program Construction, 1979, Lecture Notes in Computer Science, Vol. 69.
Peter Luschny, The Fibonacci Function.
FORMULA
F(n, k) = F(n, k-1) + F(n, k-2) for k >= 2, otherwise 1, n for k = 0, 1.
F(n, k) = (n-1)*f(k-1) + f(k) where f(n) = A000045(n+1), the Fibonacci numbers starting with f(0) = 1.
F(n, k) = ((phi^k*(n*phi + 1) - (-phi)^(-k)*((n - 1)*phi - 1)))/(2 + phi).
F(n, k) = [x^k] (1 + (n - 1)*x)/(1 - x - x^2) for k >= 0.
F(k, n) = [x^k] (F(0, n) + F(0, n-1)*x)/(1 - x)^2 for k >= 0.
F(n, k) = (k!/sqrt(5))*[x^k] ((n-psi)*exp(phi*x) - (n-phi)*exp(psi*x)) for k >= 0.
F(n, k) - F(n-1, k) = sign(k)^(n-1)*f(k) for all n, k in Z, where A000045 is extended to negative integers by f(-n) = (-1)^(n-1)*f(n) (CMath 6.107). - Peter Luschny, May 09 2022
F(n, k) = 2*((n-1)*i*sin(k*c) + sin((k+1)*c))/(i^k*sqrt(5)) where c = Pi/2 - i*arcsinh(1/2), for all n, k in Z. Based on a remark from Bill Gosper. - Peter Luschny, May 10 2022
EXAMPLE
Array starts:
n\k 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
---------------------------------------------------------
[0] 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, ... A212804
[1] 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... A000045 (shifted once)
[2] 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... A000045 (shifted twice)
[3] 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ... A000032 (shifted once)
[4] 1, 4, 5, 9, 14, 23, 37, 60, 97, 157, ... A000285
[5] 1, 5, 6, 11, 17, 28, 45, 73, 118, 191, ... A022095
[6] 1, 6, 7, 13, 20, 33, 53, 86, 139, 225, ... A022096
[7] 1, 7, 8, 15, 23, 38, 61, 99, 160, 259, ... A022097
[8] 1, 8, 9, 17, 26, 43, 69, 112, 181, 293, ... A022098
[9] 1, 9, 10, 19, 29, 48, 77, 125, 202, 327, ... A022099
MAPLE
f := n -> combinat:-fibonacci(n + 1): F := (n, k) -> (n-1)*f(k-1) + f(k):
seq(seq(F(n-k, k), k = 0..n), n = 0..9);
# The next implementation is for illustration only but is not recommended
# as it relies on floating point arithmetic.
phi := (1 + sqrt(5))/2: psi := (1 - sqrt(5))/2:
F := (n, k) -> (psi^k*(phi - n) - phi^k*(psi - n)) / (phi - psi):
for n from -6 to 6 do lprint(seq(simplify(F(n, k)), k = -6..6)) od;
MATHEMATICA
Table[LinearRecurrence[{1, 1}, {1, n}, 10], {n, 0, 9}] // TableForm
F[ n_, k_] := (MatrixPower[{{0, 1}, {1, 1}}, k].{{1}, {n}})[[1, 1]]; (* Michael Somos, May 08 2022 *)
c := Pi/2 - I*ArcSinh[1/2]; (* Based on a remark from Bill Gosper. *)
F[n_, k_] := 2 (I (n-1) Sin[k c] + Sin[(k+1) c]) / (I^k Sqrt[5]);
Table[Simplify[F[n, k]], {n, -6, 6}, {k, -6, 6}] // TableForm (* Peter Luschny, May 10 2022 *)
PROG
(Julia) # Time complexity is O(lg n).
function fibrec(n::Int)
n == 0 && return (BigInt(0), BigInt(1))
a, b = fibrec(div(n, 2))
c = a * (b * 2 - a)
d = a * a + b * b
iseven(n) ? (c, d) : (d, c + d)
end
function Fibonacci(n::Int, k::Int)
k == 0 && return BigInt(1)
k < 0 && return (-1)^k*Fibonacci(1 - n, -k)
a, b = fibrec(k - 1)
a + b*n
end
for n in -6:6
println([Fibonacci(n, k) for k in -6:6])
end
(PARI) F(n, k) = ([0, 1; 1, 1]^k*[1; n])[1, 1]
(PARI) {F(n, k) = n*fibonacci(k) + fibonacci(k-1)}; /* Michael Somos, May 08 2022 */
CROSSREFS
KEYWORD
AUTHOR
Peter Luschny, Apr 01 2022
STATUS
approved