%I #11 Jun 13 2015 00:51:23
%S 0,0,4,9,34,71,245,543,1835,4223,14167,33279,111279,264191,882015,
%T 2105343,7023295,16809983,56055167,134348799,447916799,1074266111,
%U 3581236735,8592031743,28641504255,68727865343,229098477567
%N Number of different squares created when a square sheet of paper is folded n times, the first time by one of the diagonal of the square and after by the median of the triangle.
%C There are two types of squares: (1) those whose edges are parallel to the edges of the initial square and (2) those whose edges are diagonal to the edges of the initial square. These squares are enumerated by the p(x) and d(x) functions. - _T. D. Noe_, Aug 15 2004
%H <a href="/index/Rec">Index entries for linear recurrences with constant coefficients</a>, signature (1,14,-14,-56,56,64,-64).
%F a(1)=0, a(2)=0, a(3)=4, a(5)=34, a(6)=71, a(7)=245, a(8)=509 are easily computed. If n even > 8 define Y(8)=130, Y(n)=3*Y(n-2) and then a(n)=9*a(n-2)-3*Y(n-2); if n odd define Y(7)=27, Y(n)=6*Y(n-2)-3 and then a(n)=8*a(n-2)+3-6*Y(n-2)
%F Let p(x) = x(x+1)(2x+1)/6 and d(x) = x(4x+1)(4x-1)/3. Then, for n>3, a(n) = -1 + p(2^ceiling(n/2-1)) + d(2^floor(n/2-2)) - _T. D. Noe_, Aug 15 2004
%F For n>3, satisfies a linear recurrence with characteristic polynomial (1-x)(1-2x)(1+2x)(1-2x^2)(1-8x^2).
%F G.f.: -x^3*(32*x^7-60*x^5-48*x^4+33*x^3+31*x^2-5*x-4)/((x-1)*(2*x-1)*(2*x+1)*(2*x^2-1)*(8*x^2-1)). [_Colin Barker_, Oct 21 2012]
%Y Cf. A096260, A096227.
%K nonn,easy
%O 1,3
%A _Pierre CAMI_, Aug 13 2004
%E Corrected and extended by _T. D. Noe_, Aug 15 2004