login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A049652 a(n)=(F(3n+2)-1)/4, where F=A000045 (the Fibonacci sequence). 12
0, 1, 5, 22, 94, 399, 1691, 7164, 30348, 128557, 544577, 2306866, 9772042, 41395035, 175352183, 742803768, 3146567256, 13329072793, 56462858429, 239180506510, 1013184884470, 4291920044391, 18180865062035 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

From Anant Godbole, Apr 27 2006: (Start)

"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.

"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.

"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.

"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)

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

REFERENCES

C. L. Dodgson, "Condensation of determinants," Proceedings of the Royal Society of London, 15 (1866), 150-155.

D. Zeilberger, "Dodgson's determinant-evaluation rule proved by TWO-TIMING MEN and WOMEN," Electron. J. Combin. 4 (no. 2, "The Wilf Festschrift") (1997), #R22, 2 pp. (p. 12).

LINKS

Table of n, a(n) for n=0..22.

T. Amdeberhan and S. Ekhad, A condensed condensation proof of a determinant evaluation conjectured by Greg Kuperberg and Jim Propp.

Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.

Index entries for linear recurrences with constant coefficients, signature (5,-3,-1).

FORMULA

a(n)= A099919(n)/2.

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. - Benoit Cloitre, May 06 2003

a(0) = 0, a(1) = 1, a(2) = 5, a(3) = 22, a(n) = 5a(n-1)-3a(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. - Benoit Cloitre, May 06 2003

a(n+2) = 4*a(n+1)+a(n)+1. - Anant Godbole, Apr 27 2006

G.f.: x/((x-1)*(x^2+4*x-1)). - R. J. Mathar, Nov 23 2007

MAPLE

a:= n-> add(fibonacci(i, 4), i=0..n): seq(a(n), n=0..22); # Zerinvary Lajos, Mar 20 2008

MATHEMATICA

s = 0; lst = {s}; Do[s += Fibonacci[n, 4]; AppendTo[lst, s], {n, 1, 22, 1}]; lst (* Zerinvary Lajos, Jul 14 2009 *)

PROG

(PARI) a(n)=fibonacci(3*n+2)\4 \\ Charles R Greathouse IV, Jun 11 2015

CROSSREFS

Cf. A000071, A048739.

Sequence in context: A095932 A000346 A026672 * A026877 A128746 A049675

Adjacent sequences:  A049649 A049650 A049651 * A049653 A049654 A049655

KEYWORD

nonn,easy

AUTHOR

Clark Kimberling

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 24 07:19 EDT 2017. Contains 288697 sequences.