A022309 a(n) = a(n-1) + a(n-2) + 1 for n>1, a(0)=0, a(1)=4.

0, 4, 5, 10, 16, 27, 44, 72, 117, 190, 308, 499, 808, 1308, 2117, 3426, 5544, 8971, 14516, 23488, 38005, 61494, 99500, 160995, 260496, 421492, 681989, 1103482, 1785472, 2888955, 4674428, 7563384, 12237813, 19801198, 32039012, 51840211, 83879224, 135719436

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Links

• Colin Barker, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Crossrefs

Cf. A000045, A022095, A022308.

Programs

Mathematica

RecurrenceTable[{a[0]==0,a[1]==4,a[n]==a[n-1]+a[n-2]+1},a,{n,40}] (* or *) CoefficientList[Series[-x(-4+3x)/((x-1)(x^2+x-1)),{x,0,40}],x]  (* Harvey P. Dale, Apr 24 2011 *)

PARI

concat(0, Vec(x*(4-3*x) / ((1-x)*(1-x-x^2)) + O(x^50))) \\ Colin Barker, Feb 20 2017

Formula

From R. J. Mathar, Apr 07 2011: (Start)

G.f. -x*(-4+3*x) / ( (x-1)*(x^2+x-1) ).

a(n) = A022095(n) - 1. (End)

From Colin Barker, Feb 20 2017: (Start)

a(n) = -1 + (2^(-1-n)*((1-t)^n*(-9+t) + (1+t)^n*(9+t)))/t, where t=sqrt(5).

a(n) = 2*a(n-1) - a(n-3) for n>2. (End)

a(n) = 5*F(n) + F(n-1) - 1, where F = A000045. - Bruno Berselli, Feb 20 2017