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
A093565 (8,1) Pascal triangle.
1, 8, 1, 8, 9, 1, 8, 17, 10, 1, 8, 25, 27, 11, 1, 8, 33, 52, 38, 12, 1, 8, 41, 85, 90, 50, 13, 1, 8, 49, 126, 175, 140, 63, 14, 1, 8, 57, 175, 301, 315, 203, 77, 15, 1, 8, 65, 232, 476, 616, 518, 280, 92, 16, 1, 8, 73, 297, 708, 1092, 1134, 798, 372, 108, 17, 1, 8, 81, 370, 1005
Offset: 0
Comments
The array F(8;n,m) gives in the columns m>=1 the figurate numbers based on A017077, including the decagonal numbers A001107,(see the W. Lang link).
This is the eighth member, d=8, in the family of triangles of figurate numbers, called (d,1) Pascal triangles: A007318 (Pascal), A029653, A093560-4, for d=1..7.
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+7*z)/(1-(1+x)*z).
The SW-NE diagonals give A022098(n-1) = Sum_{k=0..ceiling((n-1)/2)} a(n-1-k,k), n >= 1, with n=0 value 7. Observation by Paul Barry, Apr 29 2004. Proof via recursion relations and comparison of inputs.
Examples
Triangle begins [1]; [8, 1]; [8, 9, 1]; [8, 17, 10, 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
a093565 n k = a093565_tabl !! n !! k a093565_row n = a093565_tabl !! n a093565_tabl = [1] : iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [8, 1] -- Reinhard Zumkeller, Aug 31 2014
Formula
a(n, m)=F(8;n-m, m) for 0<= m <= n, otherwise 0, with F(8;0, 0)=1, F(8;n, 0)=8 if n>=1 and F(8;n, m):=(8*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)=8 if n>=1; a(n, m)= a(n-1, m) + a(n-1, m-1).
G.f. column m (without leading zeros): (1+7*x)/(1-x)^(m+1), m>=0.
T(n, k) = C(n, k) + 7*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)*(8 + 17*x + 10*x^2/2! + x^3/3!) = 8 + 25*x + 52*x^2/2! + 90*x^3/3! + 140*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
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
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
A229339 GCD of all sums of n consecutive Lucas numbers.
1, 1, 2, 5, 1, 4, 1, 15, 2, 11, 1, 40, 1, 29, 2, 105, 1, 76, 1, 275, 2, 199, 1, 720, 1, 521, 2, 1885, 1, 1364, 1, 4935, 2, 3571, 1, 12920, 1, 9349, 2, 33825, 1, 24476, 1, 88555, 2, 64079, 1, 231840, 1, 167761, 2, 606965, 1, 439204, 1, 1589055, 2, 1149851, 1, 4160200, 1, 3010349, 2
Offset: 1
Comments
The sum of two consecutive Lucas number is the sum of four consecutive Fibonacci numbers, which is verified easily enough with the identity L(n) = F(n - 1) + F(n + 1). Therefore a(1) = a(2) = A210209(4).
Examples
a(3) = 2 because any sum of three consecutive Lucas numbers is an even number. a(4) = 5 because all sums of four consecutive Lucas numbers are divisible by 5. a(5) = 1 because some sums of five consecutive Lucas numbers are coprime.
Links
- Colin Barker, Table of n, a(n) for n = 1..1000
- Dan Guyer and aBa Mbirika, GCD of sums of k consecutive Fibonacci, Lucas, and generalized Fibonacci numbers, Journal of Integer Sequences, 24 No.9, Article 21.9.8 (2021), 25pp; arXiv preprint, arXiv:2104.12262 [math.NT], 2021.
- Index entries for linear recurrences with constant coefficients, signature (0,0,0,3,0,1,0,-1,0,-3,0,0,0,1).
Programs
-
Mathematica
a[n_] := a[n] = If[n <= 14, {1, 1, 2, 5, 1, 4, 1, 15, 2, 11, 1, 40, 1, 29}[[n]], 3*a[n - 4] + a[n - 6] - a[n - 8] - 3*a[n - 10] + a[n - 14]]; Array[a, 64] (* Giovanni Resta, Oct 04 2013 *) CoefficientList[Series[(x^12 - x^11 + 2 x^10 - 5 x^9 - 2 x^8 - x^7 - 6 x^6 + x^5 - 2 x^4 + 5 x^3 + 2 x^2 + x + 1) / (-x^14 + 3 x^10 + x^8 - x^6 - 3 x^4 + 1), {x, 0, 40}], x] (* Vincenzo Librandi, Nov 09 2014 *) LinearRecurrence[{0,0,0,3,0,1,0,-1,0,-3,0,0,0,1},{1,1,2,5,1,4,1,15,2,11,1,40,1,29},70] (* Harvey P. Dale, Jul 21 2021 *) Table[GCD[LucasL[n + 1] - 2, LucasL[n] + 1], {n, 0, 50}] (* Horst H. Manninger, Dec 25 2021 *) -
PARI
Vec(x*(x^12 -x^11 +2*x^10 -5*x^9 -2*x^8 -x^7 -6*x^6 +x^5 -2*x^4 +5*x^3 +2*x^2 +x +1) / (-x^14 +3*x^10 +x^8 -x^6 -3*x^4 +1) + O(x^100)) \\ Colin Barker, Nov 09 2014
Formula
a(n) = 3*a(n-4) + a(n-6) - a(n-8) - 3*a(n-10) + a(n-14) for n > 14. - Giovanni Resta, Oct 04 2013
G.f.: x*(x^12 -x^11 +2*x^10 -5*x^9 -2*x^8 -x^7 -6*x^6 +x^5 -2*x^4 +5*x^3 +2*x^2 +x +1) / (-x^14 +3*x^10 +x^8 -x^6 -3*x^4 +1). - Colin Barker, Nov 09 2014
From Aba Mbirika, Jan 04 2022: (Start)
a(n) = gcd(L(n+1)-1, L(n+2)-3).
a(n) = Lcm_{A106291(m) divides n} m.
Proofs of these formulas are given in Theorems 15 and 25 of the Guyer-Mbirika paper. (End)
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.
A022370 Fibonacci sequence beginning 2, 16.
2, 16, 18, 34, 52, 86, 138, 224, 362, 586, 948, 1534, 2482, 4016, 6498, 10514, 17012, 27526, 44538, 72064, 116602, 188666, 305268, 493934, 799202, 1293136, 2092338, 3385474, 5477812, 8863286, 14341098
Offset: 0
Keywords
Links
- G. C. Greubel, Table of n, a(n) for n = 0..1000
- Tanya Khovanova, Recursive Sequences
- Index entries for linear recurrences with constant coefficients, signature (1, 1).
Crossrefs
Cf. A022098.
Programs
-
Mathematica
a={};b=2;c=16;AppendTo[a, b];AppendTo[a, c];Do[b=b+c;AppendTo[a, b];c=b+c;AppendTo[a, c], {n, 4!}];a (* Vladimir Joseph Stephan Orlovsky, Sep 18 2008 *) LinearRecurrence[{1,1},{2,16},40] (* Harvey P. Dale, Aug 11 2011 *) -
PARI
for(n=0,50, print1(2*(fibonacci(n+2) + 6*fibonacci(n)), ", ")) \\ G. C. Greubel, Aug 27 2017
Formula
G.f.: (2+14*x)/(1-x-x^2). - Philippe Deléham, Nov 19 2008
a(n) = 2*(Fibonacci(n+2) + 6*Fibonacci(n)). - G. C. Greubel, Aug 27 2017
a(n) = 2 * A022098(n). - Alois P. Heinz, Aug 27 2017
A199535 Clark Kimberling's even first column Stolarsky array read by antidiagonals.
1, 2, 4, 3, 7, 6, 5, 11, 9, 10, 8, 18, 15, 17, 12, 13, 29, 24, 27, 19, 14, 21, 47, 39, 44, 31, 23, 16, 34, 76, 63, 71, 50, 37, 25, 20, 55, 123, 102, 115, 81, 60, 41, 33, 22, 89, 199, 165, 186, 131, 97, 66, 53, 35, 26, 144, 322, 267, 301, 212, 157, 107, 86, 57, 43, 28
Offset: 1
Comments
The rows of the array can be seen to have the form A(n, k) = p(n)*Fibonacci(k) + q(n)*Fibonacci(k+1) where p(n) is the sequence {0, 1, 3, 3, 3, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, 15, 17, ...}{n >= 1} and q(n) is the sequence {1, 3, 3, 7, 2, 9, 9, 13, 13, 17, 17, 19, 19, 23, 23, 25, ...}{n >= 1}. - G. C. Greubel, Jun 23 2022
Examples
The even first column stolarsky array (EFC array), northwest corner: 1......2.....3.....5.....8....13....21....34....55....89...144 ... A000045; 4......7....11....18....29....47....76...123...199...322...521 ... A000032; 6......9....15....24....39....63...102...165...267...432...699 ... A022086; 10....17....27....44....71...115...186...301...487...788..1275 ... A022120; 12....19....31....50....81...131...212...343...555...898..1453 ... A013655; 14....23....37....60....97...157...254...411...665..1076..1741 ... A000285; 16....25....41....66...107...173...280...453...733..1186..1919 ... A022113; 20....33....53....86...139...225...364...589...953..1542..2495 ... A022096; 22....35....57....92...149...241...390...631..1021..1652..2673 ... A022130; Antidiagonal rows (T(n, k)): 1; 2, 4; 3, 7, 6; 5, 11, 9, 10; 8, 18, 15, 17, 12; 13, 29, 24, 27, 19, 14; 21, 47, 39, 44, 31, 23, 16; 34, 76, 63, 71, 50, 37, 25, 20; 55, 123, 102, 115, 81, 60, 41, 33, 22;
Links
- Clark Kimberling, The first column of an interspersion, Fibonacci Quarterly 32 (1994), pp. 301-314.
Crossrefs
Formula
From G. C. Greubel, Jun 23 2022: (Start)
T(n, 1) = A000045(n+1).
T(n, 2) = A000032(n+1), n >= 2.
T(n, 4) = A022120(n-2), n >= 4.
T(n, 5) = A013655(n-1), n >= 5.
T(n, 6) = A000285(n-2), n >= 6.
T(n, 7) = A022113(n-4), n >= 7.
T(n, 8) = A022096(n-4), n >= 8.
T(n, 9) = A022130(n-6), n >= 9.
T(n, 10) = A022098(n-5), n >= 10.
T(n, 11) = A022095(n-7), n >= 11.
T(n, 12) = A022121(n-8), n >= 12.
T(n, 13) = A022388(n-10), n >= 13.
T(n, 14) = A022122(n-10), n >= 14.
T(n, 15) = A022097(n-10), n >= 15.
T(n, 16) = A022088(n-10), n >= 16.
T(n, 17) = A022390(n-14), n >= 17.
T(n, n) = A199536(n).
T(n, n-1) = A199537(n-1), n >= 2. (End)
Extensions
More terms added by G. C. Greubel, Jun 23 2022
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