A116157 a(n) = a(n-1) + 2*a(n-2) - 2*a(n-3) + a(n-5).

1, 1, 3, 3, 7, 8, 17, 22, 43, 60, 110, 161, 283, 428, 732, 1132, 1901, 2984, 4950, 7848, 12912, 20609, 33721, 54065, 88137, 141737, 230490, 371411, 602982, 972961, 1577840, 2548288, 4129457, 6673335, 10808634, 17474230, 28293116, 45753765, 74064872, 119794804

Offset: 0

Author

Nikita Gogin & Aleksandr Myllari (alemio(AT)utu.fi), Apr 15 2007

Keywords

• easy
• nonn

Comments

A Fibonacci-Padovan sequence.

The summation over some naturally chosen planes in the pyramid composed of MacWilliams transform matrices yields this sequence, which is the convolution of the Fibonacci numbers and the (alternating) Padovan numbers. Namely, the formula F(n) = Sum_{i+k=n, i>0, k>0} binomial(k,i) = Sum_{i+k=n, i>0, k>0} Krawtchouk[{k,i},0] where Krawtchouk[{k,i},x] is the i-th Krawtchouk polynomial of order k has a natural generalization as G(n) = Sum_{i+j+k=n, i>0,j>0, k>0} Krawtchouk[{k,i},j].

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1000
• N. Gogin and A. Myllari, The Fibonacci-Padovan sequence and MacWilliams transform matrices, Programming and Computing Software, Vol. 33, Issue 2 (March 2007), pp. 74-79.
• Sait Tas, Omur Deveci and Erdal Karaduman, The Fibonacci-Padovan sequences in finite groups, Maejo Int. J. Sci. Technol. 8 (2014), no. 03, pp. 279-287.
• Index entries for linear recurrences with constant coefficients, signature (1,2,-2,0,1).

Crossrefs

Cf. A000045, A000931.

Programs

GAP

a:=[1,1,3,3,7];; for n in [6..50] do a[n]:=a[n-1]+2*a[n-2]- 2*a[n-3]+a[n-5]; od; a; # G. C. Greubel, May 10 2019

Magma

R:=PowerSeriesRing(Integers(), 50); Coefficients(R!( 1/((1-x-x^2)*(1-x^2+x^3)) )); // G. C. Greubel, May 10 2019

Mathematica

a[0]=1; a[1]=1; a[2]=3; a[3]=3; a[4]=7; a[n_]:=a[n]=a[n-1]+2a[n-2]-2a[n-3]+a[n-5]; Table[a[n], {n, 0, 50}]
LinearRecurrence[{1,2,-2,0,1},{1,1,3,3,7},50] (* Harvey P. Dale, Mar 07 2015 *)

PARI

my(x='x+O('x^50)); Vec(1/((1-x-x^2)*(1-x^2+x^3))) \\ G. C. Greubel, May 10 2019

Sage

(1/((1-x-x^2)*(1-x^2+x^3))).series(x, 50).coefficients(x, sparse=False) # G. C. Greubel, May 10 2019

Formula

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