close form solution for A136010 (per PURRS http://www.cs.unipr.it/purrs/)

Sat Mar 29 19:35:03 CET 2008

It is well known (cf e.g.
http://en.wikipedia.org/wiki/Recurrence_relation) that if
    a[n] = A a[n-1]+B a[n-2]
with A^2+4B > 0, then
    a[n] = C u^n + D v^n
where u,v are the 2 roots of the char. equation
    r^2-Ar-B = 0
and C,D are given by the initial conditions
   a[0] = C+D, a[1] = Cu+Dv.
i.e.
  C = (v a[0] -a[1])/(v-u)
  D = (a[1] - u a[0])/(v-u)
such that finally

a[n] = [( v a[0] - a[1]) u^n +  (a[1] - u a[0]) v^n ] / (v-u)

i.e.
A136010(n)=(10+61/sqrt(85))*(7/2-1/2*sqrt(85))^n+(10-61/sqrt(85))*(7/2+1/2*sqrt(85))^n
in our case.

Maple:
A136010:=n->simplify((10+61/sqrt(85))*(7/2-1/2*sqrt(85))^n+(10-61/sqrt(85))*(7/2+1/2*sqrt(85))^n);

PARI:
A136010(n) = round((10+61/sqrt(85))*(7/2-1/2*sqrt(85))^n+(10-61/sqrt(85))*(7/2+1/2*sqrt(85))^n)

Maximilian

On Sat, Mar 29, 2008 at 12:30 PM, Alexander Povolotsky
<apovolot at gmail.com> wrote:
> http://www.cs.unipr.it/purrs/
> PURRS Demo Results
> Exact solution for x(n) = 7*x(-1+n)+9*x(-2+n)
> for the initial conditions
> x(1) = 20
> x(2) = 9
>
> x(n) = -1277/1530*(7/2-1/2*sqrt(85))^n*sqrt(85)    -
> 131/18*(7/2-1/2*sqrt(85))^n
>         +1277/1530 *sqrt(85)*(7/2+1/2*sqrt(85))^n  -
> 131/18*(7/2+1/2*sqrt(85))^n
>
> for each n >= 1
>
> I checked first few terms and it looks correct.
>
> (11:32) gp > a(n) = -1277/1530*(7/2-1/2*sqrt(85))^n*sqrt(85)-
> 131/18*(7/2-1/2*sqrt(85))^n+1277/1530
>  *sqrt(85)*(7/2+1/2*sqrt(85))^n-131/18*(7/2+1/2*sqrt(85))^n
>
> (11:33) gp > a(1)
> %1 = 20.00000000000000000000000000
> (11:33) gp > a(2)
> %2 = 9.000000000000000000000000000
> (11:33) gp > a(3)
> %3 = 243.0000000000000000000000000
> (11:33) gp > a(4)
> %4 = 1782.000000000000000000000001
>  --------------------------------------------------------------------------------------------
>  On Thu, Mar 27, 2008 at 2:56 PM, Maximilian Hasler
>  < Maximilian.Hasler at martinique.univ-ag.fr> wrote:
>  Then a g.f. for the sequence including 1st 2 terms would be
>
>   gf = (131*x - 20)/(9*x^2 + 7*x - 1)
>
>  = 20 + 9*x + 243*x^2 + 1782*x^3 + 14661*x^4 + 118665*x^5 +
>  962604*x^6 + 7806213*x^7 + 63306927*x^8 + 513404406*x^9 +
>  4163593185*x^10 + 33765791949*x^11 + 273832882308*x^12 +
>  2220722303697*x^13 + 18009552066651*x^14 + 146053365199830*x^15 +
>  O(x^16)
>
>  The denom. being of the form (9x^2+7x-1), this means that
>  a[n] = 7a[n-1] + 9a[n-2]
>
>  (in some sense, the higher powers of x add previous terms (coeff's of
>  lower powers) to the term corresponding to a given power).
>  ---------- Forwarded message ----------
>  From: Alexander Povolotsky <apovolot at gmail.com>
>  Date: Thu, Mar 27, 2008 at 9:40 AM
>
>  Return-Path: <superseq-reply at research.att.com>
>
>  Report on [ 243,1782,14661,118665,962604,7806213,63306927,513404406]:
>  Many tests are carried out, but only potentially useful information
>  (if any) is reported here.
>
>  TEST: IS THE SEQUENCE OF ABSOLUTE VALUES IN THE ENCYCLOPEDIA?
>
>  Matches (up to a limit of 50) found for  243 1782 14661 118665 962604
>  7806213 63306927 513404406  :
>
>  SUGGESTION: GUESSGF FOUND ONE OR MORE GENERATING FUNCTIONS
>  WARNING: THESE MAY BE ONLY APPROXIMATIONS!
>  Generating function(s) and type(s) are:
>
>                                 243 + 81 x
>                            [- --------------, ogf]
>                                  2
>                               9 x  - 1 + 7 x
>
>   SUGGESTION: LISTTOALGEQ FOUND ONE OR MORE ALGEBRAIC
>  EQUATIONS SATISFIED BY THE GEN. FN.
>  WARNING: THESE MAY BE ONLY APPROXIMATIONS!
>  Equation(s) and type(s) are:
>                                                        2
>               [-n + (243 + 7 n) a(n) + (81 + 9 n) a(n) , revogf]
>
>
>  Types of generating functions that may have been mentioned above:
>
>  ogf     =       ordinary generating function
>  egf     =       exponential generating function
>  revogf  =       reversion of ordinary generating function
>  revegf  =       reversion of exponential generating function
>  lgdogf  =       logarithmic derivative of ordinary generating function
>  lgdegf  =       logarithmic derivative of exponential generating function
>
>
>  TRY "GUESSS", HARM DERKSEN'S PROGRAM FOR GUESSING A GENERATING FUNCTION FOR A
>  SEQUENCE.
>
>         Guesss - guess a sequence, by Harm Derksen (hderksen at math.mit.edu)
>
>  Guesss suggests that the generating function  F(x)
>  may satisfy the following algebraic or differential equation:
>
>  9*x+27+(x^2+7/9*x-1/9)*F(x) = 0
>
>  If this is correct the next 6 numbers in the sequence are:
>
>  [4163593185, 33765791949, 273832882308, 2220722303697, 18009552066651,
>  146053365199830]
> ---------- Forwarded message ----------
> From: zak seidov <zakseidov at yahoo.com>
> Date: Thu, Mar 27, 2008 at 9:44 PM
> Subject: Re: A136010 solved
> To: franktaw at netscape.net, djr at nk.ca, seqfan at ext.jussieu.fr,
> njas at research.att.com, jordyg365 at gmail.com
>
> And in general, at recurrency
>  a[n]==A a[n-1]+B a[n-2], (A>0)
>
>  lim (n->+inf) a(n+1)/a(n)=
>  (A+sqrt(A^2+4B))/2.
>
>  --- franktaw at netscape.net wrote:
>  > See below for the answer.
>  > Franklin T. Adams-Watters
>  > -----Original Message-----
>  > > From: Don Reble <djr at nk.ca>
>  > > Seqfans, njas, Jordan:
>  > >
>  > > %I A136010
>  > > %S A136010
>  > > 20,9,243,1782,14661,118665,962604,7806213,63306927,513404406
>  > > %N A136010 From an online IQ test (Adaptive IQ ).
>  > >    a(1)=20, a(2)=9, a(n+2) = 7*a(n+1) + 9*a(n).
>  > >    Quick puzzle: What's lim (n->+inf) a(n+1)/a(n) ?
>  > That would be the larger root of x^2-7x-9, which is
>  > (7+sqrt(85))/2, or
>  > 8.1097722286464436550011371408814....
>