login
a(n) = a(n-1) + 3*a(n-2) + a(n-3) with a(0) = 1, a(1) = 3, a(2) = 6.
2

%I #26 Sep 27 2024 05:24:54

%S 1,3,6,16,37,91,218,528,1273,3075,7422,17920,43261,104443,252146,

%T 608736,1469617,3547971,8565558,20679088,49923733,120526555,290976842,

%U 702480240,1695937321,4094354883,9884647086,23863649056,57611945197,139087539451,335787024098

%N a(n) = a(n-1) + 3*a(n-2) + a(n-3) with a(0) = 1, a(1) = 3, a(2) = 6.

%C a(n) is the number of subsets T of A = {1, 2, ..., 2*n} such that no pair of elements a, b of T satisfy |a-b| = 1 or n.

%H Yifan Xie, <a href="/A375726/a375726.txt">Proof for the comment</a>

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

%F a(n) = (1/4)*((3 + sqrt(2))*(1+sqrt(2))^n + (3 - sqrt(2))*(1-sqrt(2))^n-2*(-1)^n).

%F For n >= 2, a(n) = 2*a(n-1) + a(n-2) - (-1)^n.

%F From _Stefano Spezia_, Aug 26 2024: (Start)

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

%F E.g.f.: (sinh(x) - cosh(x) + exp(x)*(3*cosh(sqrt(2)*x) + sqrt(2)*sinh(sqrt(2)*x)))/2. (End)

%F Let f = (3 - sqrt(2))*exp((1 - sqrt(2))*x) + (3 + sqrt(2))*exp((1 + sqrt(2))*x), then 4*a(n) + 2*(-1)^n = n! * [x^n] f. - _Peter Luschny_, Sep 10 2024

%F a(n)+a(n-1) = A048654(n). - _R. J. Mathar_, Sep 27 2024

%e For n = 2, the a(2) = 6 subsets of {1, 2, 3, 4} are {}, {1}, {2}, {3}, {4}, {1, 4}.

%t LinearRecurrence[{1, 3, 1}, {1, 3, 6}, 31] (* _Hugo Pfoertner_, Aug 26 2024 *)

%o (PARI) my(a=1, b=3, c=6); for(n=1, 31, print1(a, ", "); my(d=a+3*b+c); a=b; b=c; c=d)

%Y Cf. A001333 (b), A000129 (c), A097076 (d).

%K nonn,easy

%O 0,2

%A _Yifan Xie_, Aug 25 2024