|
%I #63 Jan 09 2019 03:32:30
%S 5,17,58,198,676,2308,7880,26904,91856,313616,1070752,3655776,
%T 12481600,42614848,145496192,496755072,1696027904,5790601472,
%U 19770350080,67500197376,230460089344,786839962624,2686439671808,9172078761984,31315435704320,106917585293312
%N Pisot sequence E(5,17), a(n) = floor(a(n-1)^2 / a(n-2) + 1/2).
%H Colin Barker, <a href="/A010914/b010914.txt">Table of n, a(n) for n = 0..1000</a>
%H D. W. Boyd, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa34/aa3444.pdf">Some integer sequences related to the Pisot sequences</a>, Acta Arithmetica, 34 (1979), 295-305.
%H D. W. Boyd, <a href="https://www.researchgate.net/publication/262181133_Linear_recurrence_relations_for_some_generalized_Pisot_sequences_-_annotated_with_corrections_and_additions">Linear recurrence relations for some generalized Pisot sequences</a>, Advances in Number Theory ( Kingston ON, 1991) 333-340, Oxford Sci. Publ., Oxford Univ. Press, New York, 1993.
%H S. B. Ekhad, N. J. A. Sloane, D. Zeilberger, <a href="http://arxiv.org/abs/1609.05570">Automated proofs (or disproofs) of linear recurrences satisfied by Pisot Sequences</a>, arXiv:1609.05570 [math.NT] (2016).
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2).
%F From _Max Alekseyev_, Sep 03 2013: (Start)
%F It is not hard to show that this sequence satisfies the following simple linear recurrence relation: a(n) = 4*a(n-1) - 2*a(n-2).
%F Proof: Let a(n) = A010914(n) be the sequence defined by the recurrence a(n) = floor( a(n-1)^2/a(n-2) + 1/2 ) and initial terms a(0)=5 and a(1)=17. Define a sequence b(n) by the recurrence b(n) = 4*b(n-1) - 2*b(n-2) and the same initial terms b(0)=a(0)=5 and b(1)=a(1)=17. We want to prove that a(n)=b(n) for all n.
%F The main trick is that instead of proving that the sequence a() satisfies the recurrence for the sequence b(), we will do it the other way around: prove that b() satisfies the recurrence for a(). This will imply that these two sequences coincide.
%F To prove that b() satisfies the recurrence for a(), it is enough to show that abs( b(n-1)^2 - b(n)*b(n-2) ) < b(n-2)/2. To do this, we will use the explicit formula for b(n) that
%F b(n) = (10+7*sqrt(2))/4 * (2+sqrt(2))^n + (10-7*sqrt(2))/4 * (2-sqrt(2))^n.
%F Computing abs( b(n-1)^2 - b(n)*b(n-2) ), one finds that it equals 2^n times a constant. At the same time, b(n) grows as (2+sqrt(2))^n (up to a constant) which allows one to easily prove (e.g., by induction on n) that abs( b(n-1)^2 - b(n)*b(n-2) ) < b(n-2)/2. (End)
%F For positive n, a(n) equals [1,1;1,3]^n.[1,2].[1.2], which means calculate the n-th power of the specific 2 X 2 matrix, multiply from the right by the column vector [1,2], and finally take the dot product of this column vector with the vector [1,2]. - _John M. Campbell_, Jul 09 2011
%F a(n) is the 3rd subdiagonal of array A228405. - _Richard R. Forberg_, Sep 02 2013
%F a(n) = A079496(n+3) * A016116(n). - _Michael Somos_, Sep 03 2013
%F a(n) - a(n-1)^2 / a(n-2) = 2^floor(n/2) / A143609(n+1) < 1/2 if n>1. - _Michael Somos_, Sep 03 2013
%F G.f.: (5-3*x) / (1-4*x+2*x^2). - _Colin Barker_, Dec 06 2015
%t LinearRecurrence[{4, -2}, {5, 17}, 26] (* _Jean-François Alcover_, Jan 09 2019 *)
%o (PARI) {a(n) = if( n<0, 0, real( (10 + 7 * quadgen(8)) / 2 * (2 + quadgen(8))^n ))} /* _Michael Somos_, Sep 03 2013 */
%o (PARI) {a(n) = if( n<0, 0, n += 3 ; 2^ceil((n - 4)/2) * polcoeff( (1 + x - 3*x^2 - x^3) / (1 - 6*x^2 + x^4) + x * O(x^n), n))} /* _Michael Somos_, Sep 03 2013 */
%o (PARI) Vec((5-3*x)/(1-4*x+2*x^2) + O(x^30)) \\ _Colin Barker_, Dec 06 2015
%Y Cf. A079496, A143609.
%K nonn,easy
%O 0,1
%A _Simon Plouffe_
|
