login
Generalized Fibonacci numbers: a(n) = a(n-1) + 10*a(n-2).
16

%I #103 Sep 08 2022 08:44:40

%S 1,1,11,21,131,341,1651,5061,21571,72181,287891,1009701,3888611,

%T 13985621,52871731,192727941,721445251,2648724661,9863177171,

%U 36350423781,134982195491,498486433301,1848308388211,6833172721221

%N Generalized Fibonacci numbers: a(n) = a(n-1) + 10*a(n-2).

%C The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=2, 11*a(n-2) equals the number of 11-colored compositions of n with all parts >=2, such that no adjacent parts have the same color. - _Milan Janjic_, Nov 26 2011

%C For a(n) = [(1+(4m+1)^1/2)^n)-(1-(4m+1)^1/2))^n)]/[(2^n)(4m+1)^1/2), a(n)/a(n-1) appears to converge to (1+sqrt(4m+1))/2. Here with m = 10, the numbers in the sequence are congruent with those of the Fibonacci sequence modulo m-1 = 9. For example, F(8) = 21 (Fibonacci) corresponds to a(8) = 5061 (here) because 2+1 and 5+0+1+6 are congruent. - _Maleval Francis_, Nov 12 2013

%H Vincenzo Librandi, <a href="/A015446/b015446.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1, 10).

%F a(n) = (((1+sqrt(41))/2)^(n+1) - ((1-sqrt(41))/2)^(n+1))/sqrt(41).

%F From _Paul Barry_, Sep 10 2005: (Start)

%F a(n) = Sum_{k=0..n} binomial((n+k)/2, k)*(1+(-1)^(n-k))*10^((n-k)/2)/2.

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k)*10^k. (End)

%F a(n) is the entry (M^n)_1,1 where the matrix M = [1,2;5,0]. - _Simone Severini_, Jun 22 2006

%F a(n) = Sum_{k=0..n} A109466(n,k)*(-10)^(n-k). - _Philippe Deléham_, Oct 26 2008

%F G.f.: 1/(1-x-10*x^2). - _Colin Barker_, Feb 03 2012

%F a(n) = (sum{1<=k<=n+1, k odd}C(n+1,k)*41^((k-1)/2))/2^n. - _Vladimir Shevelev_, Feb 05 2014

%t Table[MatrixPower[{{1,2},{5,0}},n][[1]][[1]],{n,0,44}] (* _Vladimir Joseph Stephan Orlovsky_, Feb 20 2010 *)

%t CoefficientList[Series[1/(1-x-10*x^2), {x,0,50}], x] (* _G. C. Greubel_, Apr 30 2017 *)

%t LinearRecurrence[{1,10},{1,1},30] (* _Harvey P. Dale_, Dec 12 2018 *)

%o (Sage) [lucas_number1(n,1,-10) for n in range(1, 25)] # _Zerinvary Lajos_, Apr 22 2009

%o (Magma) [ n eq 1 select 1 else n eq 2 select 1 else Self(n-1)+10*Self(n-2): n in [1..30] ]; // _Vincenzo Librandi_, Aug 23 2011

%o (PARI) a(n)=([1,2;5,0]^n)[1,1] \\ _Charles R Greathouse IV_, Mar 09 2014

%Y Cf. A015447, A015443.

%K nonn,easy

%O 0,3

%A _Olivier Gérard_