A014742 Expansion of (1+x^2)/(1 - 2*x - 2*x^2 + x^3).

1, 2, 7, 17, 46, 119, 313, 818, 2143, 5609, 14686, 38447, 100657, 263522, 689911, 1806209, 4728718, 12379943, 32411113, 84853394, 222149071, 581593817, 1522632382, 3986303327, 10436277601, 27322529474, 71531310823, 187271402993, 490282898158, 1283577291479

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

Let M = a triangle with (1,1,1,3,3,5,5,7,7,...) as the left border and (0,1,2,3,4,5,...) as all other columns. A014742 = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. - Gary W. Adamson, Jul 26 2010

For n >= 1, a(n) is the ratio of L/h (rounded down), where L = length of short sides of parallelogram appearing in dissection fallacy of square F(n+2) X F(n+2), F(n) is Fibonacci number, and h = perpendicular distance between the long sides LL. The first differences of A069921 give L^2. See illustration. - Kival Ngaokrajang, Jun 27 2014

From Wolfdieter Lang, Jul 15 2014: (Start)

The preceding comment is a conjecture using a(n) = floor(LL(n)*L(n)) with LL(n) = sqrt(F(n+2)^2 + F(n)^2) and L(n) = LL(n-1), n >= 1 (its author agreed with this in an email). See also, e.g., the Koshy reference for the dissection fallacy, sect. 6, 100 - 108.

The proof of the conjecture uses first the identity (LL(n)*LL(n-1))^2 - a(n)^2 = + 1 with a(n) = F(n-1)*F(n) + F(n+1)*F(n+2) (see the formula section for a(n)). This identity is due to the factorization of the left-hand side which is A(n)^2 with A(n) = F(n)*F(n+1) - F(n-1)*F(n+2). But A(n) = (-1)^(n+1) is a special instance of a well known Fibonacci identity (Koshy, p. 88, Nr. 19 for h=-1, k=2, F(-1) = 1). Now one has (LL(n)*LL(n-1))^2 = 1 + a(n)^2, that is LL(n)*LL(n-1) = sqrt(1 + a(n)^2). Because a(n) < sqrt(1 + a(n)^2) < a(n) + 1 (just square both inequalities using a(n) > 0) one has now proved that floor(LL(n)*LL(n-1)) = a(n), n >= 1. (End)

a(n) = numerator(Re(C(n))), with the complex sequence C(n) defined in the name of A069921. - Wolfdieter Lang, Jul 16 2014

Examples

			a(2) = F(1)*F(2) + F(3)*F(4) = 1*1 + 2*3 = 7. - _James R. Buddenhagen_, Jan 06 2009
		

References

• T. Koshy, Fibonacci and Lucas Numbers with Applications, John Wiley & Sons, 2001.

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Kival Ngaokrajang, Illustration of initial terms
• Eric Weisstein's World of Mathematics, Dissection Fallacy
• Wikipedia, Missing square puzzle
• Index entries for linear recurrences with constant coefficients, signature (2,2,-1).

Crossrefs

Cf. A069921. - Kival Ngaokrajang, Jun 27 2014

Cf. similar sequences of the type k*F(n)*F(n+1) + (-1)^n listed in A264080.

Cf. A000032, A000045.

Programs

Maple

seq(combinat[fibonacci](n-1)*combinat[fibonacci](n)+combinat[fibonacci](n+1)*combinat[fibonacci](n+2), n=0..50); # will give first 50 terms - James R. Buddenhagen, Jan 06 2009

Mathematica

CoefficientList[Series[(1 + x^2)/(1 - 2*x - 2*x^2 + x^3), {x, 0, 30}], x] (* Wesley Ivan Hurt, Jun 27 2014 *)
LinearRecurrence[{2, 2, -1},{1, 2, 7},30] (* Ray Chandler, Sep 23 2015 *)

PARI

Vec((1+x^2)/(1-2*x-2*x^2+x^3)+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

PARI

a(n) = round((2^(-1-n)*((-1)^n*2^(2+n)-3*(3-sqrt(5))^n*(-1+sqrt(5))+3*(1+sqrt(5))*(3+sqrt(5))^n))/5) \\ Colin Barker, Sep 29 2016

Formula

a(n) = F(n-1)*F(n) + F(n+1)*F(n+2), where F = A000045. - James R. Buddenhagen, Jan 06 2009

From Wolfdieter Lang, Jul 15 2014: (Start)

G.f.: (1+x^2)/(1 - 2*x - 2*x^2 + x^3) = (1+x^2)/((1+x)*(1 - 3*x + x^2)) = (2/(1+x) + 3*(1+x)/(1 - 3*x + x^2))/5 (see the name).

a(n) = (2*(-1)^n + 3*(F(2*n) + F(2*(n+1))))/5,

a(n) = (2*(-1)^n + L(2*n-1) + L(2*n+3))/5 with L(n) = A000032(n) and L(-1) = -1. (End)

a(n) = 3*F(n)*F(n+1) + (-1)^n. - Bruno Berselli, Oct 30 2015

a(n) = (2^(-1-n)*((-1)^n*2^(2+n) - 3*(3-sqrt(5))^n*(-1+sqrt(5)) + 3*(1+sqrt(5))*(3+sqrt(5))^n))/5. - Colin Barker, Sep 29 2016

a(n) = Fibonacci(n + 2)^2 - 2*Fibonacci(n)^2. - Detlef Meya, Jun 29 2024

E.g.f.: exp(-x)*(2 + 3*exp(5*x/2)*(cosh(sqrt(5)*x/2) + sqrt(5)*sinh(sqrt(5)*x/2)))/5. - Stefano Spezia, Jun 30 2024

Extensions

Buddenhagen's Jan 06 2009 entries adjusted for offset 0 by Wolfdieter Lang, Jul 15 2014