CATALAN'S SEQUENCES


Fibonacci numbers F(n) are the sequence 0,1,1,2,3,5,8,13,... recursively defined as 

    F(0) = 0
    F(1) = 1
    F(n) = F(n-1) + F(n-2)
The Cassini's identity for Fibonacci numbers is F(n+1) F(n-1) - F(n) F(n) = (-1)n and could be taken as an alternate recursive definition of the Fibonacci numbers, namely 
    F(n+1) = [ F(n)^2 + (-)^n ] / F(n-1)
e.g., 
    2 = [ 1^1 + (-)^2 ] / 1
    3 = [ 2^2 + (-)^3 ] / 1
    5 = [ 3^2 + (-)^4 ] / 2
    ...
Cassini identity is generalized by Catalan's identity, 
    F(n+r) = [ F(n)^2 - (-)^(n-r) F(r)^2 ] / F(n-r)
We can look at Catalan's formula as a recursive definition of the terms of a sequence, either with alternating signs, 
    C'(0) = 1
    C'(1) = A
    C'(n+1) = [ C'(n)^2 + (-)^n D ] / C'(n-1)
or with fixed sign 
    C"(0) = 1
    C"(1) = A
    C"(n+1) = [ C"(n)^2 + D ] / C"(n-1)
It turns out that only certain choices of (A,D) makes one of these into an integer sequence. The table below lists the first few terms of some of these sequences. Several of these sequences are already known sequences. Their OEIS numbers are in the table. The sequences with D=0 are trivial solutions, consisting of the powers f A: C(k) = Ak. Therefore we consider only sequences with A, and D not zero.


Question.
Is the number of non-zero integer pairs (A,D) that make C' or C" into an integer sequence finite or infinite ? Is it possible to describe the values of the non-zero integer pairs (A,D) that make C' or C" into an integer sequence ?

By looking at the sequences in the table below it seems that the values of D that make C' and C" into integer sequences are spaced by A.

Let's begin with a lemma about the sequences, defined as 

  A(0) = 1
  A(1) = a
  A(k) = ( A(k-1)^2 + (-)^k ) / A(k-2)
has the properties 
(a')   a A(k+1) = A(k+2) - A(k)
(b')   A(k+3) A(k) - A(k+2) A(k+1) = (-)^k a
Let's compute 
   A(2) = a^2 + 1
   A(3) = a^3 + 2 a
   A(4) = a^4 + 3 a^2 + 1
   A(5) = a^5 + 4 a^3 + 3 a
   ...

(a') can be proved by induction. For k=0 it is A(1) a = A(2) - A(0), ie, a a = (a2+1) - 1. For the induction step the RHS is 
   ( A(k+1)^2 + (-)^k - A(k)^2 )/A(k) = ( A(k+1)^2 - A(k+1) A(k-1) ) / A(k)
                                      = A(k+1) ( A(k+1) - A(k-1) ) / A(k)
                                      = A(k+1) ( a A(k) ) / A(k)

(b') then follows by induction, using (a'). For k=0 it is A(3) A(0) - A(2) A(1) = (a3 + 2 a) - (a2 + 1) a = a. For k=1, 

  A(4) A(1) - A(3) A(2) = (a^4 + 3 a^2 + 1) a - (a^3 + 2 a) (a^2 + 1)
                        = a^5 + 3 a^3 + a - a^5 - 3 a^3 - 2 a 
                        = - a

For the induction step 
  A(k+3) A(k) - A(k+2) A(k+1) = ( A(k+2)^2 + (-)^(k+3) )/A(k+1) * A(k) - A(k+2) A(k+1)
                              = [(A(k+2)^2 + (-)^(k+3)) A(k) - A(k+2) (A(k+2) A(k) - (-)^(k+2))]/A(k+1)
                              = (-)^k (-A(k) + A(k+2))/A(k+1)
                              = (-)^k a

Now the Catalan's sequences with alternating signs defined by A=n, D=1 + a n - n2 are integer. Let's write the first few terms: 

  C'(0) = 1,
  C'(1) = n,
  C'(2) = A(0) + A(1) n
  C'(3) = A(1) + A(2) n
  ...
  C'(k) = A(k-1) n + A(k-2) (for k > 1)
We try to verify that this expression antually satisfies the defining recursive relation of C'(k). 
( A(k-1) n + A(k-2) )^2 - (-)^k ( 1 + a n - n^2 )
  = A(k-1)^2 n^2 + 2 A(k-1) A(k-2) n + A(k-2)^2 + (-)^(k+1) + (-)^(k+1) a n + (-)^k n^2
  = [A(k-1)^2 + (-)^k] n^2 + [2 A(k-1) A(k-2) + a (-)^(k+1)] n + [ A(k-1)^2 + (-)^(k+1) ]
  = A(k) A(k-2) n^2 + A(k-1) A(k-2) n + A(k-1) A(k-3) + [ A(k-1)A(k-2) + a (-)^(k+1) ] n
  = ( A(k) n + A(k-1) ) * ( A(k-2) n + A(k-3) )    by prop. (b)

This result (almost) answers the question: there are infinitely many Catalan's sequences with alternating sign and have D = 1 + a n - n2. We still have not proved that other values of D do not give integer sequences.

A similar result should hold for Catalan's sequences with fixed sign, using D = -1 + a n - n2. We consider the sequence defined by B(k+1) = [ B(k)2 - 1 ]/B(k-1) 

   B(0) = 1
   B(1) = b
   B(2) = b^2 - 1
   B(3) = b^3 - 2 b
   B(4) = b^4 - 3 b^2 + 1
   B(5) = b^5 - 4 b^3 + 3 b
Then the two lemma are 
(a")  b B(k+1) = B(k) B(k+2)
(b")  B(k+3) B(k) - B(k+2) B(k+1) = -b

As before, these lemma can be proven by induction. Then a solution for the recurrence relation with fixed sign is 

  C"(0) = 1
  C"(1) = n
  C"(2) = B(1) n - B(0)
  C"(3) = B(2) n - B(1)
  ...
  C"(k) = B(k-1) n - B(k-2)
and, ss before this can be proven by induction, using (a") (b").

Table of integer sequences (A,D != 0) 
          A   D s
A016777   4  -9 +: 1,4,7,10,13,16,19,22,25,28
A002878   4  -5 +: 1,4,11,29,76,199,521,1364,3571,9349
A001353   4  -1 +: 1,4,15,56,209,780,2911,10864,40545,151316
A004253   4   3 +: 1,4,19,91,436,2089,10009,47956,229771,1100899
A038723   4   7 +: 1,4,23,134,781,4552,26531,154634,901273,5253004
          4  11 +: 1,4,27,185,1268,8691,59569,408292,2798475,19181033
A000285   4 -11 -: 1,4,5,9,14,23,37,60,97,157
A048654   4  -7 -: 1,4,9,22,53,128,309,746,1801,4348
A003688   4  -3 -: 1,4,13,43,142,469,1549,5116,16897,55807
A001076   4   1 -: 1,4,17,72,305,1292,5473,23184,98209,416020
A100237   4   5 -: 1,4,21,109,566,2939,15261,79244,411481,2136649
          4   9 -: 1,4,25,154,949,5848,36037,222070,1368457,8432812

A054486   5 -11 +: 1,5,14,37,97,254,665,1741,4558,11933
A001834   5  -6 +: 1,5,19,71,265,989,3691,13775,51409,191861
A004254   5  -1 +: 1,5,24,115,551,2640,12649,60605,290376,1391275
A001653   5   4 +: 1,5,29,169,985,5741,33461,195025,1136689,6625109
A033889   5   9 +: 1,5,34,233,1597,10946,75025,514229,3524578,24157817
A105426   5  14 +: 1,5,39,307,2417,19029,149815,1179491,9286113,73109413
A048655   5 -14 -: 1,5,11,27,65,157,379,915,2209,5333
A108300   5  -9 -: 1,5,16,53,175,578,1909,6305,20824,68777
A015448   5  -4 -: 1,5,21,89,377,1597,6765,28657,121393,514229
A052918   5   1 -: 1,5,26,135,701,3640,18901,98145,509626,2646275
          5   6 -: 1,5,31,191,1177,7253,44695,275423,1697233,10458821
          5  11 -: 1,5,36,257,1835,13102,93549,667945,4769164,34052093

A054491   6 -13 +: 1,6,23,86,321,1198,4471,16686,62273,232406
A030221   6  -7 +: 1,6,29,139,666,3191,15289,73254,350981,1681651
A001109   6  -1 +: 1,6,35,204,1189,6930,40391,235416,1372105,7997214
A049685   6   5 +: 1,6,41,281,1926,13201,90481,620166,4250681,29134601
          6  11 +: 1,6,47,370,2913,22934,180559,1421538,11191745,88112422
          6  17 +: 1,6,53,471,4186,37203,330641,2938566,26116453,232109511
A189735   6 -17 -: 1,6,19,63,208,687,2269,7494,24751,81747
A048875   6 -11 -: 1,6,25,106,449,1902,8057,34130,144577,612438
A015449   6  -5 -: 1,6,31,161,836,4341,22541,117046,607771,3155901
A005668   6   1 -: 1,6,37,228,1405,8658,53353,328776,2026009,12484830
          6   7 -: 1,6,43,307,2192,15651,111749,797894,5697007,40676943
          6  13 -: 1,6,49,398,3233,26262,213329,1732894,14076481,114344742

A055271   7 -15 +: 1,7,34,163,781,3742,17929,85903,411586,1972027
A002315   7  -8 +: 1,7,41,239,1393,8119,47321,275807,1607521,9369319
A004187   7  -1 +: 1,7,48,329,2255,15456,105937,726103,4976784,34111385
A070997   7   6 +: 1,7,55,433,3409,26839,211303,1663585,13097377,103115431
          7  13 +: 1,7,62,551,4897,43522,386801,3437687,30552382,271533751
          7  20 +: 1,7,69,683,6761,66927,662509,6558163,64919121,642633047
A048876   7 -20 -: 1,7,29,123,521,2207,9349,39603,167761,710647
          7 -13 -: 1,7,36,187,971,5042,26181,135947,705916,3665527
A015451   7  -6 -: 1,7,43,265,1633,10063,62011,382129,2354785,14510839
A054413   7   1 -: 1,7,50,357,2549,18200,129949,927843,6624850,47301793
          7   8 -: 1,7,57,463,3761,30551,248169,2015903,16375393,133019047
          7  15 -: 1,7,64,583,5311,48382,440749,4015123,36576856,333206827

A054488   8 -17 +: 1,8,47,274,1597,9308,54251,316198,1842937,10741424
A033890   8  -9 +: 1,8,55,377,2584,17711,121393,832040,5702887,39088169
A001090   8  -1 +: 1,8,63,496,3905,30744,242047,1905632,15003009,118118440
A070998   8   7 +: 1,8,71,631,5608,49841,442961,3936808,34988311,310957991
          8  15 +: 1,8,79,782,7741,76628,758539,7508762,74329081,735782048
          8  23 +: 1,8,87,949,10352,112923,1231801,13436888,146573967,1598876749
          8 -23 -: 1,8,41,213,1106,5743,29821,154848,804061,4175153
          8 -15 -: 1,8,49,302,1861,11468,70669,435482,2683561,16536848
A015453   8  -7 -: 1,8,57,407,2906,20749,148149,1057792,7552693,53926643
A041025   8   1 -: 1,8,65,528,4289,34840,283009,2298912,18674305,151693352
          8   9 -: 1,8,73,665,6058,55187,502741,4579856,41721445,380072861
          8  17 -: 1,8,81,818,8261,83428,842541,8508838,85930921,867818048

          9 -19 +: 1,9,62,425,2913,19966,136849,937977,6428990,44064953
A057080   9 -10 +: 1,9,71,559,4401,34649,272791,2147679,16908641,133121449
A018913   9  -1 +: 1,9,80,711,6319,56160,499121,4435929,39424240,350382231
A072256   9   8 +: 1,9,89,881,8721,86329,854569,8459361,83739041,828931049
          9  17 +: 1,9,98,1069,11661,127202,1387561,15135969,165108098,1801053109
          9 -26 -: 1,9,55,339,2089,12873,79327,488835,3012337,18562857
          9 -17 -: 1,9,64,457,3263,23298,166349,1187741,8480536,60551493
A015454   9  -8 -: 1,9,73,593,4817,39129,317849,2581921,20973217,170367657
A099371   9   1 -: 1,9,82,747,6805,61992,564733,5144589,46866034,426938895
A109108   9  10 -: 1,9,91,919,9281,93729,946571,9559439,96540961,974969049
          9  19 -: 1,9,100,1109,12299,136398,1512677,16775845,186046972,2063292537

A077245  10 -21 +: 1,10,79,622,4897,38554,303535,2389726,18814273,148124458
A057081  10 -11 +: 1,10,89,791,7030,62479,555281,4935050,43860169,389806471
A004189  10  -1 +: 1,10,99,980,9701,96030,950599,9409960,93149001,922080050
A078922  10   9 +: 1,10,109,1189,12970,141481,1543321,16835050,183642229,2003229469
         10 -29 -: 1,10,71,507,3620,25847,184549,1317690,9408379,67176343
         10 -19 -: 1,10,81,658,5345,43418,352689,2864930,23272129,189041962
A015455  10  -9 -: 1,10,91,829,7552,68797,626725,5709322,52010623,473804929
A041041  10   1 -: 1,10,101,1020,10301,104030,1050601,10610040,107151001,1082120050

         11 -23 +: 1,11,98,871,7741,68798,611441,5434171,48296098,429230711
A054320  11 -12 +: 1,11,109,1079,10681,105731,1046629,10360559,102558961,1015229051
         11 -32 -: 1,11,89,723,5873,47707,387529,3147939,25571041,207716267
         11 -21 -: 1,11,100,911,8299,75602,688717,6274055,57155212,520670963
A015456  11 -10 -: 1,11,111,1121,11321,114331,1154631,11660641,117761041,1189271051

A077251  12 -25 +: 1,12,119,1178,11661,115432,1142659,11311158,111968921,1108378052
         12 -35 -: 1,12,109,993,9046,82407,750709,6838788,62299801,567536997
A171510  12 -23 -: 1,12,121,1222,12341,124632,1258661,12711242,128371081,1296422052

         13 -40 +: 1,13,129,1277,12641,125133,1238689,12261757,121378881,1201527053
         13 -51 -: 1,13,118,1075,9793,89212,812701,7403521,67444390,614403031
         13 -38 -: 1,13,131,1323,13361,134933,1362691,13761843,138981121,1403573053

         14 -57 +: 1,14,139,1376,13621,134834,1334719,13212356,130788841,1294676054
         14 -69 -: 1,14,127,1157,10540,96017,874693,7968254,72588979,661269065
         14 -55 -: 1,14,141,1424,14381,145234,1466721,14812444,149591161,1510724054

         15 -74 -: 1,15,151,1525,15401,155535,1570751,15863045,160201201,1617875055

Marco Corvi - 2014