{
  "id": "2105.04334",
  "version": "v1",
  "published": "2021-05-10T13:08:56.000Z",
  "updated": "2021-05-10T13:08:56.000Z",
  "title": "Asymptotic Analysis of q-Recursive Sequences",
  "authors": [
    "Clemens Heuberger",
    "Daniel Krenn",
    "Gabriel F. Lipnik"
  ],
  "categories": [
    "math.CO",
    "math.NT"
  ],
  "abstract": "For an integer $q\\ge2$, a $q$-recursive sequence is defined by recurrence relations on subsequences of indices modulo some powers of~$q$. In this article, $q$-recursive sequences are studied and the asymptotic behavior of their summatory functions is analyzed. It is shown that every $q$-recursive sequence is $q$-regular in the sense of Allouche and Shallit and that a $q$-linear representation of the sequence can be computed easily by using the coefficients from the recurrence relations. Detailed asymptotic results for $q$-recursive sequences are then obtained based on a general result on the asymptotic analysis of $q$-regular sequences. Three particular sequences are studied in detail: We discuss the asymptotic behavior of the summatory functions of Stern's diatomic sequence, the number of non-zero elements in some generalized Pascal's triangle and the number of unbordered factors in the Thue--Morse sequence. For the first two sequences, our analysis even leads to precise formul\\ae{} without error terms.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-05-10T13:08:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A16",
      "11A63",
      "30B50",
      "68Q45",
      "68R05"
    ],
    "keywords": [
      "asymptotic analysis",
      "q-recursive sequences",
      "recurrence relations",
      "asymptotic behavior",
      "summatory functions"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}