cp's OEIS Frontend

A049652 a(n) = (F(3*n+2) - 1)/4, where F=A000045 (the Fibonacci sequence).

%I A049652 #60 May 27 2024 15:46:53
%S A049652 0,1,5,22,94,399,1691,7164,30348,128557,544577,2306866,9772042,
%T A049652 41395035,175352183,742803768,3146567256,13329072793,56462858429,
%U A049652 239180506510,1013184884470,4291920044391,18180865062035,77015380292532,326242386232164,1381984925221189,5854182087116921
%N A049652 a(n) = (F(3*n+2) - 1)/4, where F=A000045 (the Fibonacci sequence).
%C A049652 From _Anant Godbole_, Apr 27 2006: (Start)
%C A049652 "a(n) equals the number of 2 by 2 determinants that need to be computed while finding the determinant of an n X n matrix using the method discovered by C. L. Dodgson (Lewis Carroll) in the 19th century.
%C A049652 "To evaluate the determinant of an n X n matrix A, set up a 2 by 2 determinant with entries that equal the determinants of the "northwest, northeast, southwest and southeast" (n-1) by (n-1) submatrices of A. Divide this by determinant of the "central" (n-2) by (n-2) submatrix of A. If the latter is zero, the problem can be fixed by row interchanges.
%C A049652 "The Dodgson method does better than the standard method of using cofactors and an expansion in terms of a row/column if n is 6 or larger. By this we mean that a fewer number of 2 by 2 determinants need to be calculated. Of course, the method of choice is diagonalization which can be achieved in polynomial time. Dodgson's method runs in exponential time, whereas the "standard" method requires one to evaluate n!/2 two by two determinants.
%C A049652 "A beautiful combinatorial proof of Dodgson's result was recently given by Zeilberger and an application is presented by Amdeberhan and Ekhad, where a conjecture of Kuperberg and Propp is proved using Dodgson's formula." (End)
%C A049652 This is the sequence A(0,1;4,1;1)of the family of sequences [a,b:c,d:k] considered by G. Detlefs, and treated as A(a,b;c,d;k) in the W. Lang link given below. - _Wolfdieter Lang_, Oct 18 2010
%H A049652 G. C. Greubel, <a href="/A049652/b049652.txt">Table of n, a(n) for n = 0..1000</a>
%H A049652 T. Amdeberhan and S. Ekhad, <a href="http://www.math.temple.edu/~tewodros/papersps/RABBIT.PDF">A condensed condensation proof of a determinant evaluation conjectured by Greg Kuperberg and Jim Propp</a>.
%H A049652 C. L. Dodgson, <a href="https://doi.org/10.1098/rspl.1866.0037">Condensation of determinants</a>, Proceedings of the Royal Society of London, 15 (1866), 150-155.
%H A049652 Wolfdieter Lang, <a href="/A049652/a049652.pdf">Notes on certain inhomogeneous three term recurrences.</a>
%H A049652 Doron Zeilberger, <a href="https://doi.org/10.37236/1337">Dodgson's Determinant-Evaluation Rule Proved by Two-Timing Men and Women</a>, Electron. J. Combin. 4 (no. 2, "The Wilf Festschrift") (1997), #R22, 2 pp. (p. 12).
%H A049652 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (5,-3,-1).
%F A049652 a(n) = A099919(n)/2.
%F A049652 From _Benoit Cloitre_, May 06 2003: (Start)
%F A049652 a(0) = 0, a(1) = 1; a(n) = ceiling(r(4)*a(n-1)) where r(4) = 2+sqrt(5) is the positive root of X^2 = 4*X+1. More generally the sequence a(1) = 1, a(n) = ceiling(r(z)*a(n-1)) where r(z) = (1/2)*(z+sqrt(z^2+4)) is the positive root of X^2 = z*X+1 satisfies the linear recurrence: n > 3, a(n) = (z+1)*a(n-1) - (z-1)*a(n-2) - a(n-3) and the closed form formula: a(n) = floor(t(z)*r(z)^n) where t(z) = (1/(2*z))*(1+(z+2)/sqrt(z^2+4)) is the positive root of z*(z^2+4)*X^2 = (z^2+4)*X+1.
%F A049652 a(0) = 0, a(1) = 1, a(2) = 5, a(3) = 22, a(n) = 5*a(n-1) - 3*a(n-2) - a(n-3); a(n) = floor(t(4)*r(4)^n) where t(4) = (1/8)*(1+3/sqrt(5)) is the positive root of 80*X^2 = 20*X+1. (End)
%F A049652 a(n+2) = 4*a(n+1) + a(n) + 1. - _Anant Godbole_, Apr 27 2006
%F A049652 G.f.: x/((x-1)*(x^2+4*x-1)). - _R. J. Mathar_, Nov 23 2007
%F A049652 E.g.f.: exp(x)*(exp(x)*(5*cosh(sqrt(5)*x) + 3*sqrt(5)*sinh(sqrt(5)*x)) - 5)/20. - _Stefano Spezia_, May 24 2024
%p A049652 a:= n-> add(fibonacci(i,4), i=0..n): seq(a(n), n=0..22); # _Zerinvary Lajos_, Mar 20 2008
%t A049652 s = 0; lst = {s}; Do[s += Fibonacci[n, 4]; AppendTo[lst, s], {n, 1, 22, 1}]; lst (* _Zerinvary Lajos_, Jul 14 2009 *)
%t A049652 LinearRecurrence[{5, -3, -1}, {0, 1, 5}, 30] (* or *) Table[(Fibonacci[ 3*n+2] - 1)/4, {n,0,30}] (* _G. C. Greubel_, Dec 05 2017 *)
%o A049652 (PARI) a(n)=fibonacci(3*n+2)\4 \\ _Charles R Greathouse IV_, Jun 11 2015
%o A049652 (Magma) [(Fibonacci(3*n+2) - 1)/4: n in [0..30]]; // _G. C. Greubel_, Dec 05 2017
%Y A049652 Cf. A000045, A000071, A048739, A099919.
%K A049652 nonn,easy
%O A049652 0,3
%A A049652 _Clark Kimberling_