A035513 Wythoff array read by falling antidiagonals.
1, 2, 4, 3, 7, 6, 5, 11, 10, 9, 8, 18, 16, 15, 12, 13, 29, 26, 24, 20, 14, 21, 47, 42, 39, 32, 23, 17, 34, 76, 68, 63, 52, 37, 28, 19, 55, 123, 110, 102, 84, 60, 45, 31, 22, 89, 199, 178, 165, 136, 97, 73, 50, 36, 25, 144, 322, 288, 267, 220, 157, 118, 81, 58, 41, 27, 233, 521
Offset: 1
A101220 a(n) = Sum_{k=0..n} Fibonacci(n-k)*n^k.
0, 1, 3, 14, 91, 820, 9650, 140601, 2440317, 49109632, 1123595495, 28792920872, 816742025772, 25402428294801, 859492240650847, 31427791175659690, 1234928473553777403, 51893300561135516404, 2322083099525697299278
Offset: 0
Comments
In what follows a(i,j,k) denotes a three-dimensional array, the terms a(n) are defined as a(n,n,n) in that array. - Joerg Arndt, Jan 03 2021
Previous name was: Three-dimensional array: a(i,j,k) = expansion of x*(1 + (i-j)*x)/((1-j*x)*(1-x-x^2)), read by a(n,n,n).
a(i,j,k) = the k-th value of the convolution of the Fibonacci numbers (A000045) with the powers of i = Sum_{m=0..k} a(i-1,j,m), both for i = j and i > 0; a(i,j,k) = a(i-1,j,k) + a(j,j,k-1), for i,k > 0; a(i,1,k) = Sum_{m=0..k} a(i-1,0,m), for i > 0. With F = Fibonacci and L = Lucas, then a(1,1,k) = F(k+2) - 1; a(2,1,k) = F(k+3) - 2; a(3,1,k) = L(k+2) - 3; a(4,1,k) = 4*F(k+1) + F(k) - 4; a(1,2,k) = 2^k - F(k+1); a(2,2,k) = 2^(k+1) - F(k+3); a(3,2,k) = 3(2^k - F(k+2)) + F(k); a(4,2,k) = 2^(k+2) - F(k+4) - F(k+2); a(1,3,k) = (3^k + L(k-1))/5, for k > 0; a(2,3,k) = (2 * 3^k - L(k)) /5, for k > 0; a(3,3,k) = (3^(k+1) - L(k+2))/5; a(4,3,k) = (4 * 3^k - L(k+2) - L(k+1))/5, etc..
Examples
a(1,3,3) = 6 because a(1,3,0) = 0, a(1,3,1) = 1, a(1,3,2) = 2 and 4*2 - 2*1 - 3*0 = 6.
Links
- G. C. Greubel, Table of n, a(n) for n = 0..385
- Eric Weisstein's World of Mathematics, Fibonacci Number
- Eric Weisstein's World of Mathematics, Lucas Number
Crossrefs
a(0, j, k) = A000045(k).
a(1, 2, k+1) - a(1, 2, k) = A099036(k).
a(3, 2, k+1) - a(3, 2, k) = A104004(k).
a(4, 2, k+1) - a(4, 2, k) = A027973(k).
a(1, 3, k+1) - a(1, 3, k) = A099159(k).
a(i, 0, k) = A109754(i, k).
a(i, i+1, 3) = A002522(i+1).
a(i, i+1, 4) = A071568(i+1).
a(2^i-2, 0, k+1) = A118654(i, k), for i > 0.
Sequences of the form a(n, 0, k): A000045(k+1) (n=1), A000032(k) (n=2), A000285(k-1) (n=3), A022095(k-1) (n=4), A022096(k-1) (n=5), A022097(k-1) (n=6), A022098(k-1) (n=7), A022099(k-1) (n=8), A022100(k-1) (n=9), A022101(k-1) (n=10), A022102(k-1) (n=11), A022103(k-1) (n=12), A022104(k-1) (n=13), A022105(k-1) (n=14), A022106(k-1) (n=15), A022107(k-1) (n=16), A022108(k-1) (n=17), A022109(k-1) (n=18), A022110(k-1) (n=19), A088209(k-2) (n=k-2), A007502(k) (n=k-1), A094588(k) (n=k).
Programs
-
Magma
A101220:= func< n | (&+[n^k*Fibonacci(n-k): k in [0..n]]) >; [A101220(n): n in [0..30]]; // G. C. Greubel, Jun 01 2025
-
Mathematica
Join[{0}, Table[Sum[Fibonacci[n-k]*n^k, {k, 0, n}], {n, 1, 20}]] (* Vaclav Kotesovec, Jan 03 2021 *) -
PARI
a(n)=sum(k=0,n,fibonacci(n-k)*n^k) \\ Joerg Arndt, Jan 03 2021
-
SageMath
def A101220(n): return sum(n^k*fibonacci(n-k) for k in range(n+1)) print([A101220(n) for n in range(31)]) # G. C. Greubel, Jun 01 2025
Formula
a(i, j, 0) = 0, a(i, j, 1) = 1, a(i, j, 2) = i+1; a(i, j, k) = ((j+1)*a(i, j, k-1)) - ((j-1)*a(i, j, k-2)) - (j*a(i, j, k-3)), for k > 2.
a(i, j, k) = Fibonacci(k) + i*a(j, j, k-1), for i, k > 0.
a(i, j, k) = (Phi^k - (-Phi)^-k + i(((j^k - Phi^k) / (j - Phi)) - ((j^k - (-Phi)^-k) / (j - (-Phi)^-1)))) / sqrt(5), where Phi denotes the golden mean/ratio (A001622).
i^k = a(i-1, i, k) + a(i-2, i, k+1).
A104161(k) = Sum_{m=0..k} a(k-m, 0, m).
a(i, j, 0) = 0, a(i, j, 1) = 1, a(i, j, 2) = i+1, a(i, j, 3) = i*(j+1) + 2; a(i, j, k) = (j+2)*a(i, j, k-1) - 2*j*a(i, j, k-2) - a(i, j, k-3) + j*a(i, j, k-4), for k > 3. a(i, j, 0) = 0, a(i, j, 1) = 1; a(i, j, k) = a(i, j, k-1) + a(i, j, k-2) + i * j^(k-2), for k > 1.
G.f.: x*(1 + (i-j)*x)/((1-j*x)*(1-x-x^2)).
a(n, n, n) = Sum_{k=0..n} Fibonacci(n-k) * n^k. - Ross La Haye, Jan 14 2006
Sum_{m=0..k} binomial(k,m)*(i-1)^m = a(i-1,i,k) + a(i-2,i,k+1), for i > 1. - Ross La Haye, May 29 2006
From Ross La Haye, Jun 03 2006: (Start)
a(3, 3, k+1) - a(3, 3, k) = A106517(k).
Sum_{j=0..i+1} a(i-j+1, 0, j) - Sum_{j=0..i} a(i-j, 0, j) = A001595(i). (End)
a(i,j,k) = a(j,j,k) + (i-j)*a(j,j,k-1), for k > 0.
a(n) ~ n^(n-1). - Vaclav Kotesovec, Jan 03 2021
Extensions
New name from Joerg Arndt, Jan 03 2021
A109754 Matrix defined by: a(i,0) = 0, a(i,j) = i*Fibonacci(j-1) + Fibonacci(j), for j > 0; read by ascending antidiagonals.
0, 0, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 3, 3, 0, 1, 4, 4, 5, 5, 0, 1, 5, 5, 7, 8, 8, 0, 1, 6, 6, 9, 11, 13, 13, 0, 1, 7, 7, 11, 14, 18, 21, 21, 0, 1, 8, 8, 13, 17, 23, 29, 34, 34, 0, 1, 9, 9, 15, 20, 28, 37, 47, 55, 55, 0, 1, 10, 10, 17, 23, 33, 45, 60, 76, 89, 89
Offset: 0
Comments
Lower triangular version is at A117501. - Ross La Haye, Apr 12 2006
Examples
Table starts: [0] 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... [1] 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... [2] 0, 1, 3, 4, 7, 11, 18, 29, 47, 76, ... [3] 0, 1, 4, 5, 9, 14, 23, 37, 60, 97, ... [4] 0, 1, 5, 6, 11, 17, 28, 45, 73, 118, ... [5] 0, 1, 6, 7, 13, 20, 33, 53, 86, 139, ... [6] 0, 1, 7, 8, 15, 23, 38, 61, 99, 160, ... [7] 0, 1, 8, 9, 17, 26, 43, 69, 112, 181, ... [8] 0, 1, 9, 10, 19, 29, 48, 77, 125, 202, ... [9] 0, 1, 10, 11, 21, 32, 53, 85, 138, 223, ...
Links
- G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Crossrefs
Rows: A000045(j); A000045(j+1), for j > 0; A000032(j), for j > 0; A000285(j-1), for j > 0; A022095(j-1), for j > 0; A022096(j-1), for j > 0; A022097(j-1), for j > 0. Diagonals: a(i, i) = A094588(i); a(i, i+1) = A007502(i+1); a(i, i+2) = A088209(i); Sum[a(i-j, j), {j=0...i}] = A104161(i). a(i, j) = A101220(i, 0, j).
Rows 7 - 19: A022098(j-1), for j > 0; A022099(j-1), for j > 0; A022100(j-1), for j > 0; A022101(j-1), for j > 0; A022102(j-1), for j > 0; A022103(j-1), for j > 0; A022104(j-1), for j > 0; A022106(j-1), for j > 0; A022107(j-1), for j > 0; A022108(j-1), for j > 0; A022109(j-1), for j > 0; A022110(j-1), for j > 0.
a(2^i-2, j+1) = A118654(i, j), for i > 0.
Cf. A117501.
Programs
-
Maple
A := (n, k) -> ifelse(k = 0, 0, n*combinat:-fibonacci(k-1) + combinat:-fibonacci(k)): seq(seq(A(n - k, k), k = 0..n), n = 0..6); # Peter Luschny, May 28 2022 -
Mathematica
T[n_, 0]:= 0; T[n_, 1]:= 1; T[n_, 2]:= n - 1; T[n_, 3]:= n - 1; T[n_, n_]:= Fibonacci[n]; T[n_, k_]:= T[n, k] = T[n - 1, k - 1] + T[n - 2, k - 2]; Table[T[n, k], {n, 0, 15}, {k, 0, n}] (* G. C. Greubel, Jan 07 2017 *)
Formula
a(i, 0) = 0, a(i, j) = i*Fibonacci(j-1) + Fibonacci(j), for j > 0.
a(i, 0) = 0, a(i, 1) = 1, a(i, 2) = i+1, a(i, j) = a(i, j-1) + a(i, j-2), for j > 2.
G.f.: (x*(1 + ix))/(1 - x - x^2).
Sum_{j=0..i+1} a(i-j+1, j) - Sum_{j=0..i} a(i-j, j) = A001595(i). - Ross La Haye, Jun 03 2006
Extensions
More terms from G. C. Greubel, Jan 07 2017
A093564 (7,1) Pascal triangle.
1, 7, 1, 7, 8, 1, 7, 15, 9, 1, 7, 22, 24, 10, 1, 7, 29, 46, 34, 11, 1, 7, 36, 75, 80, 45, 12, 1, 7, 43, 111, 155, 125, 57, 13, 1, 7, 50, 154, 266, 280, 182, 70, 14, 1, 7, 57, 204, 420, 546, 462, 252, 84, 15, 1, 7, 64, 261, 624, 966, 1008, 714, 336, 99, 16, 1, 7, 71, 325, 885
Offset: 0
Comments
The array F(7;n,m) gives in the columns m>=1 the figurate numbers based on A016993, including the 9-gonal numbers A001106, (see the W. Lang link).
This is the seventh member, d=7, in the family of triangles of figurate numbers, called (d,1) Pascal triangles: A007318 (Pascal), A029653, A093560-3, for d=1..6.
This is an example of a Riordan triangle (see A093560 for a comment and A053121 for a comment and the 1991 Shapiro et al. reference on the Riordan group). Therefore the o.g.f. for the row polynomials p(n,x):=Sum_{m=0..n} a(n,m)*x^m is G(z,x)=(1+6*z)/(1-(1+x)*z).
The SW-NE diagonals give A022097(n-1) = Sum_{k=0..ceiling((n-1)/2)} a(n-1-k,k), n >= 1, with n=0 value 6. Observation by Paul Barry, Apr 29 2004. Proof via recursion relations and comparison of inputs.
Examples
Triangle begins [1]; [7, 1]; [7, 8, 1]; [7, 15, 9, 1]; ...
References
- Kurt Hawlitschek, Johann Faulhaber 1580-1635, Veroeffentlichung der Stadtbibliothek Ulm, Band 18, Ulm, Germany, 1995, Ch. 2.1.4. Figurierte Zahlen.
- Ivo Schneider: Johannes Faulhaber 1580-1635, Birkhäuser, Basel, Boston, Berlin, 1993, ch. 5, pp. 109-122.
Links
- Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
- W. Lang, First 10 rows and array of figurate numbers .
Crossrefs
Programs
-
Haskell
a093564 n k = a093564_tabl !! n !! k a093564_row n = a093564_tabl !! n a093564_tabl = [1] : iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [7, 1] -- Reinhard Zumkeller, Sep 01 2014 -
Maple
N:= 20: # to get the first N rows T:=Matrix(N,N): T[1,1]:= 1: for m from 2 to N do T[m,1]:= 7: T[m,2..m]:= T[m-1,1..m-1] + T[m-1,2..m]; od: for m from 1 to N do convert(T[m,1..m],list) od; # Robert Israel, Dec 28 2014
Formula
a(n, m)=F(7;n-m, m) for 0<= m <= n, otherwise 0, with F(7;0, 0)=1, F(7;n, 0)=7 if n>=1 and F(7;n, m):=(7*n+m)*binomial(n+m-1, m-1)/m if m>=1.
Recursion: a(n, m)=0 if m>n, a(0, 0)= 1; a(n, 0)=7 if n>=1; a(n, m)= a(n-1, m) + a(n-1, m-1).
G.f. column m (without leading zeros): (1+6*x)/(1-x)^(m+1), m>=0.
T(n, k) = C(n, k) + 6*C(n-1, k). - Philippe Deléham, Aug 28 2005
exp(x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)*(7 + 15*x + 9*x^2/2! + x^3/3!) = 7 + 22*x + 46*x^2/2! + 80*x^3/3! + 125*x^4/4! + .... The same property holds more generally for Riordan arrays of the form ( f(x), x/(1 - x) ). - Peter Bala, Dec 22 2014
A118654 Square array T(n,k) read by antidiagonals: T(n,k) = 2^n*Fibonacci(k) - Fibonacci(k-2).
1, 1, 0, 1, 1, 1, 1, 3, 2, 1, 1, 7, 4, 3, 2, 1, 15, 8, 7, 5, 3, 1, 31, 16, 15, 11, 8, 5, 1, 63, 32, 31, 23, 18, 13, 8, 1, 127, 64, 63, 47, 38, 29, 21, 13, 1, 255, 128, 127, 95, 78, 61, 47, 34, 21, 1, 511, 256, 255, 191, 158, 125, 99, 76, 55, 34
Offset: 0
Comments
Inverse binomial transform (by columns) of A090888.
Examples
T(2,3) = 7 because 2^2(Fibonacci(3)) - Fibonacci(3-2) = 4*2 - 1 = 7.
{1};
{1, 0};
{1, 1, 1};
{1, 3, 2, 1};
{1, 7, 4, 3, 2};
{1, 15, 8, 7, 5, 3};
{1, 31, 16, 15, 11, 8, 5};
{1, 63, 32, 31, 23, 18, 13, 8};
Crossrefs
Formula
T(n,k) = 2^n*Fibonacci(k) - Fibonacci(k-2).
T(n,k) = (2^n-2)*Fibonacci(k) + Fibonacci(k+1).
T(n,0) = 1; T(n,1) = 2^n - 1; T(n,k) = T(n,k-1) + T(n,k-2), for k > 1.
T(0,k) = Fibonacci(k-1); T(1,k) = Fibonacci(k+1); T(n,k) = 3T(n-1,k) - 2T(n-2,k), for n > 1.
T(n,k) = 2T(n-1,k) + Fibonacci(k-2), for n > 0.
O.g.f. (by rows) = (1+(-2+2^n)x)/(1-x-x^2).
Sum_{k=0..n} T(n-k,k) = A119587(n+1). - Ross La Haye, May 31 2006
A096956 Pascal (1,6) triangle.
6, 1, 6, 1, 7, 6, 1, 8, 13, 6, 1, 9, 21, 19, 6, 1, 10, 30, 40, 25, 6, 1, 11, 40, 70, 65, 31, 6, 1, 12, 51, 110, 135, 96, 37, 6, 1, 13, 63, 161, 245, 231, 133, 43, 6, 1, 14, 76, 224, 406, 476, 364, 176, 49, 6, 1, 15, 90, 300, 630, 882, 840, 540, 225, 55, 6, 1, 16, 105, 390, 930
Offset: 0
Comments
Except for the first row this is the row reversed (6,1)-Pascal triangle A093563.
This is the sixth member, q=6, in the family of (1,q) Pascal triangles: A007318 (Pascal (q=1)), A029635 (q=2) (but with a(0,0)=2, not 1), A095660 (q=3), A095666 (q=4), A096940 (q=5).
This is an example of a Riordan triangle (see A053121 for a comment and the 1991 Shapiro et al. reference on the Riordan group) with o.g.f. of column no. m of the type g(x)*(x*f(x))^m with f(0)=1. Therefore the o.g.f. for the row polynomials p(n,x):=Sum_{m=0..n} a(n,m)*x^m is G(z,x)=g(z)/(1-x*z*f(z)). Here: g(x)=(6-5*x)/(1-x), f(x)=1/(1-x), hence G(z,x)=(6-5*z)/(1-(1+x)*z).
The SW-NE diagonals give Sum_{k=0..ceiling((n-1)/2)} a(n-1-k,k) = A022097(n-2), n >= 2, with n=1 value 6. Observation by Paul Barry, Apr 29 2004. Proof via recursion relations and comparison of inputs.
Examples
Triangle begins: [0] 6; [1] 1, 6; [2] 1, 7, 6; [3] 1, 8, 13, 6; [4] 1, 9, 21, 19, 6; [5] 1, 10, 30, 40, 25, 6; ...
Links
- Paolo Xausa, Table of n, a(n) for n = 0..11475 (rows 0..150 of triangle, flattened).
- Wolfdieter Lang, First 10 rows.
Crossrefs
Programs
-
Maple
a(n,k):=piecewise(n=0,6,0
-
Mathematica
A096956[n_, k_] := If[n == k, 6, (5*k/n + 1)*Binomial[n, k]]; Table[A096956[n, k], {n, 0, 12}, {k, 0, n}] (* Paolo Xausa, Apr 14 2025 *)
Formula
Recursion: a(n,m)=0 if m > n, a(0,0) = 6; a(n,0) = 1 if n >= 1; a(n,m) = a(n-1, m) + a(n-1, m-1).
G.f. column m (without leading zeros): (6-5*x)/(1-x)^(m+1), m >= 0.
a(n,k) = (1+5*k/n)*binomial(n,k), for n > 0. - Mircea Merca, Apr 08 2012
A352744 Array read by ascending antidiagonals. Generalized Fibonacci numbers F(n, k) = (psi^k*(phi - n) - phi^k*(psi - n)) / (phi - psi) where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2. F(n, k) for n >= 0 and k >= 0.
1, 1, 0, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 3, 2, 1, 4, 4, 5, 5, 3, 1, 5, 5, 7, 8, 8, 5, 1, 6, 6, 9, 11, 13, 13, 8, 1, 7, 7, 11, 14, 18, 21, 21, 13, 1, 8, 8, 13, 17, 23, 29, 34, 34, 21, 1, 9, 9, 15, 20, 28, 37, 47, 55, 55, 34, 1, 10, 10, 17, 23, 33, 45, 60, 76, 89, 89, 55
Offset: 0
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
Examples
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
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.
Crossrefs
Programs
-
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 -
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 *) -
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 */
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
A131778 6*A065941 - 5*A049310.
1, 6, 1, 1, 6, 1, 6, -4, 12, 1, 1, 6, 3, 12, 1, 6, -9, 24, -2, 18, 1, 1, 6, 0, 24, 11, 18, 1, 6, -14, 36, -20, 60, 6, 24, 1, 1, 6, -8, 36, 15, 60, 25, 24, 1, 6, -19, 48, -58, 126, -15, 120, 20, 30, 1
Offset: 1
Comments
Row sums = A022097, a Fibonacci-like sequence starting (1, 7, 8, 15, 23, 38, ...).
Examples
First few rows of the triangle: 1; 6, 1; 1, 6, 1; 6, -4, 12, 1; 1, 6, 3, 12, 1; 6, -9, 24, -2, 18, 1; 1, 6, 0, 24, 11, 18, 1; ...
A127830 a(n) = Sum_{k=0..n} (binomial(floor(k/2),n-k) mod 2).
1, 1, 1, 2, 2, 1, 2, 3, 3, 3, 2, 2, 3, 2, 3, 5, 5, 4, 4, 5, 4, 3, 3, 3, 4, 4, 3, 4, 5, 3, 5, 8, 8, 7, 6, 7, 7, 5, 6, 8, 7, 6, 5, 5, 5, 4, 4, 5, 6, 5, 5, 7, 6, 4, 5, 6, 7, 7, 5, 6, 8, 5, 8, 13, 13, 11, 10, 12, 11, 8, 9, 11, 11, 10, 8, 9, 10, 7, 9, 13, 12
Offset: 0
Comments
Row sums of number triangle A127829.
From Johannes W. Meijer, Jun 05 2011: (Start)
The Ze3 and Ze4 triangle sums, see A180662 for their definitions, of Sierpinski's triangle A047999 equal this sequence.
The sequences A127830(2^n-p), p>=0, are apparently all Fibonacci like sequences, i.e., the next term is the sum of the two nonzero terms that precede it; see the crossrefs. (End)
Crossrefs
Cf.: A000045 (p=0), A000204 (p=7), A001060 (p=13), A000285 (p=14), A022095 (p=16), A022120 (p=24), A022121 (p=25), A022113 (p=28), A022096 (p=30), A022097 (p=31), A022098 (p=32), A022130 (p=44), A022137 (p=48), A022138 (p=49), A022122 (p=52), A022114 (p=53), A022123 (p=56), A022115 (p=60), A022100 (p=62), A022101 (p=63), A022103 (p=64), A022136 (p=79), A022388 (p=80), A022389 (p=88). - Johannes W. Meijer, Jun 05 2011
Programs
-
Maple
A127830 := proc(n) local k: option remember: add(binomial(floor(k/2), n-k) mod 2, k=0..n) end: seq(A127830(n), n=0..80); # Johannes W. Meijer, Jun 05 2011
-
Mathematica
Table[Sum[Mod[Binomial[Floor[k/2],n-k],2],{k,0,n}],{n,0,80}] (* James C. McMahon, Jan 04 2025 *) -
Python
def A127830(n): return sum(not ~(k>>1)&n-k for k in range(n+1)) # Chai Wah Wu, Jul 29 2025
A353595 Array read by ascending antidiagonals. Generalized Fibonacci numbers F(n, k) = (psi^(k - 1)*(phi + n) - phi^(k - 1)*(psi + n)) / (psi - phi) where phi = (1+sqrt(5))/2 and psi = (1-sqrt(5))/2. F(n, k) for n >= 0 and k >= 0.
0, 1, 1, 2, 1, 1, 3, 1, 2, 2, 4, 1, 3, 3, 3, 5, 1, 4, 4, 5, 5, 6, 1, 5, 5, 7, 8, 8, 7, 1, 6, 6, 9, 11, 13, 13, 8, 1, 7, 7, 11, 14, 18, 21, 21, 9, 1, 8, 8, 13, 17, 23, 29, 34, 34, 10, 1, 9, 9, 15, 20, 28, 37, 47, 55, 55, 11, 1, 10, 10, 17, 23, 33, 45, 60, 76, 89, 89
Offset: 0
Comments
Examples
Array starts: n\k 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ... -------------------------------------------------------- [0] 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... A000045 [1] 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... A000045 (shifted once) [2] 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, ... A000032 [3] 3, 1, 4, 5, 9, 14, 23, 37, 60, 97, ... A104449 [4] 4, 1, 5, 6, 11, 17, 28, 45, 73, 118, ... [4] + A022095 [5] 5, 1, 6, 7, 13, 20, 33, 53, 86, 139, ... [5] + A022096 [6] 6, 1, 7, 8, 15, 23, 38, 61, 99, 160, ... [6] + A022097 [7] 7, 1, 8, 9, 17, 26, 43, 69, 112, 181, ... [7] + A022098 [8] 8, 1, 9, 10, 19, 29, 48, 77, 125, 202, ... [8] + A022099 [9] 9, 1, 10, 11, 21, 32, 53, 85, 138, 223, ... [9] + A022100
Links
- Peter Luschny, The Fibonacci Function.
- Wikipedia, Cassini and Catalan identities.
Crossrefs
Programs
-
Julia
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(n) k == 1 && return BigInt(1) k < 0 && return (-1)^(k-1)*Fibonacci(-n - 1, 2 - k) a, b = fibrec(k - 1) a*n + b end for n in -6:6 println([n], [Fibonacci(n, k) for k in -6:6]) end -
Maple
f := n -> combinat:-fibonacci(n): F := (n, k) -> n*f(k - 1) + f(k): seq(seq(F(n - k, k), k = 0..n), n = 0..11); # The next implementation is for illustration only but is not recommended # as it relies on floating point arithmetic. Illustrates the case n,k < 0. phi := (1 + sqrt(5))/2: psi := (1 - sqrt(5))/2: F := (n, k) -> (psi^(k-1)*(psi + n) - phi^(k-1)*(phi + n)) / (psi - phi): for n from -6 to 6 do lprint(seq(simplify(F(n, k)), k = -6..6)) od;
-
Mathematica
(* Works also for n < 0 and k < 0. Uses a remark from Bill Gosper. *) c := I*ArcSinh[1/2] - Pi/2; F[n_, k_] := (n Sin[(k - 1) c] - I Sin[k c]) / (I^k Sqrt[5/4]); Table[Simplify[F[n, k]], {n, 0, 6}, {k, 0, 6}] // TableForm
Formula
Functional equation extends Cassini's theorem:
F(n, k) = (-1)^(k - 1)*F(-n - 1, 2 - k).
F(n, k) = ((1 - phi)^(k - 1)*(1 - phi + n) - phi^(k - 1)*(phi + n))/(1 - 2*phi).
F(n, k) = n*fib(k - 1) + fib(k), where fib(n) are the classical Fibonacci numbers A000045 extended in the usual way for negative n.
F(n, k) - F(n-1, k) = fib(k-1).
F(n, k) = F(n, k-1) + F(n, k-2).
F(n, k) = (n*sin((k - 1)*c) - i*sin(k*c))/(i^k*sqrt(5/4)) where c = i*arcsinh(1/2) - Pi/2, for all n, k in Z. Based on a remark of Bill Gosper.
Comments
Examples
The Wythoff array begins: 1 2 3 5 8 13 21 34 55 89 144 ... 4 7 11 18 29 47 76 123 199 322 521 ... 6 10 16 26 42 68 110 178 288 466 754 ... 9 15 24 39 63 102 165 267 432 699 1131 ... 12 20 32 52 84 136 220 356 576 932 1508 ... 14 23 37 60 97 157 254 411 665 1076 1741 ... 17 28 45 73 118 191 309 500 809 1309 2118 ... 19 31 50 81 131 212 343 555 898 1453 2351 ... 22 36 58 94 152 246 398 644 1042 1686 2728 ... 25 41 66 107 173 280 453 733 1186 1919 3105 ... 27 44 71 115 186 301 487 788 1275 2063 3338 ... ... The extended Wythoff array has two extra columns, giving the row number n and A000201(n), separated from the main array by a vertical bar: 0 1 | 1 2 3 5 8 13 21 34 55 89 144 ... 1 3 | 4 7 11 18 29 47 76 123 199 322 521 ... 2 4 | 6 10 16 26 42 68 110 178 288 466 754 ... 3 6 | 9 15 24 39 63 102 165 267 432 699 1131 ... 4 8 | 12 20 32 52 84 136 220 356 576 932 1508 ... 5 9 | 14 23 37 60 97 157 254 411 665 1076 1741 ... 6 11 | 17 28 45 73 118 191 309 500 809 1309 2118 ... 7 12 | 19 31 50 81 131 212 343 555 898 1453 2351 ... 8 14 | 22 36 58 94 152 246 398 644 1042 1686 2728 ... 9 16 | 25 41 66 107 173 280 453 733 1186 1919 3105 ... 10 17 | 27 44 71 115 186 301 487 788 1275 2063 3338 ... 11 19 | 30 49 79 ... 12 21 | 33 54 87 ... 13 22 | 35 57 92 ... 14 24 | 38 62 ... 15 25 | 40 65 ... 16 27 | 43 70 ... 17 29 | 46 75 ... 18 30 | 48 78 ... 19 32 | 51 83 ... 20 33 | 53 86 ... 21 35 | 56 91 ... 22 37 | 59 96 ... 23 38 | 61 99 ... 24 40 | 64 ... 25 42 | 67 ... 26 43 | 69 ... 27 45 | 72 ... 28 46 | 74 ... 29 48 | 77 ... 30 50 | 80 ... 31 51 | 82 ... 32 53 | 85 ... 33 55 | 88 ... 34 56 | 90 ... 35 58 | 93 ... 36 59 | 95 ... 37 61 | 98 ... 38 63 | ... ... Each row of the extended Wythoff array also satisfies the Fibonacci recurrence, and may be extended to the left using this recurrence backwards. From _Peter Munn_, Jun 11 2021: (Start) The Wythoff array appears to have the following relationship to the traditional Fibonacci rabbit breeding story, modified for simplicity to be a story of asexual reproduction. Give each rabbit a number, 0 for the initial rabbit. When a new round of rabbits is born, allocate consecutive numbers according to 2 rules (the opposite of many cultural rules for inheritance precedence): (1) newly born child of Rabbit 0 gets the next available number; (2) the descendants of a younger child of any given rabbit precede the descendants of an older child of the same rabbit. Row n of the Wythoff array lists the children of Rabbit n (so Rabbit 0's children have the Fibonacci numbers: 1, 2, 3, 5, ...). The generation tree below shows rabbits 0 to 20. It is modified so that each round of births appears on a row. 0 : ,-------------------------: : : ,---------------: 1 : : : ,--------: 2 ,---------: : : : : : ,-----: 3 ,-----: ,-----: 4 : : : : : : : : ,--: 5 ,--: ,---: 6 ,---: 7 ,---: : : : : : : : : : : : : : ,--: 8 ,--: ,--: 9 ,--: 10 ,--: ,--: 11 ,--: ,--: 12 : : : : : : : : : : : : : : : : : : : : : : 13 : : 14 : 15 : : 16 : : 17 : 18 : : 19 : 20 : The extended array's nontrivial extra column (A000201) gives the number that would have been allocated to the first child of Rabbit n, if Rabbit n (and only Rabbit n) had started breeding one round early. (End)References
Links
Crossrefs
Programs
Maple
Mathematica
W[n_, k_] := Fibonacci[k + 1] Floor[n*GoldenRatio] + (n - 1) Fibonacci[k]; Table[ W[n - k + 1, k], {n, 12}, {k, n, 1, -1}] // FlattenPARI
Python
Python
Formula
Extensions