Name
Abstract | ||
|---|---|---|
A nondecreasing sequence of positive integers is $(\alpha,\beta)$-Conolly, or Conolly-like for short, if for every positive integer $m$ the number of times that $m$ occurs in the sequence is $\alpha + \beta r_m$, where $r_m$ is $1$ plus the 2-adic valuation of $m$. A recurrence relation is $(\alpha, \beta)$-Conolly if it has an $(\alpha, \beta)$-Conolly solution sequence. We discover that Conolly-like sequences often appear as solutions to nested (or meta-Fibonacci) recurrence relations of the form $A(n) = \sum_{i=1}^k A(n-s_i-\sum_{j=1}^{p_i} A(n-a_{ij}))$ with appropriate initial conditions. For any fixed integers $k$ and $p_1,p_2,\ldots, p_k$ we prove that there are only finitely many pairs $(\alpha, \beta)$ for which $A(n)$ can be $(\alpha, \beta)$-Conolly. For the case where $\alpha =0$ and $\beta =1$, we provide a bijective proof using labeled infinite trees to show that, in addition to the original Conolly recurrence, the recurrence $H(n)=H(n-H(n-2)) + H(n-3-H(n-5))$ also has the Conolly sequence as a solution. When $k=2$ and $p_1=p_2$, we construct an example of an $(\alpha,\beta)$-Conolly recursion for every possible ($\alpha,\beta)$ pair, thereby providing the first examples of nested recursions with $p_i1$ whose solutions are completely understood. Finally, in the case where $k=2$ and $p_1=p_2$, we provide an if and only if condition for a given nested recurrence $A(n)$ to be $(\alpha,0)$-Conolly by proving a very general ceiling function identity. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/100795425 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
conolly-like solutions,conolly solution sequence,positive integer,conolly sequence,nested recurrence relations,nested recurrence,conolly recursion,nondecreasing sequence,original conolly recurrence,nested recursions,recurrence relation,beta r_m,bijective proof,ruler function | Integer,Discrete mathematics,Combinatorics,Recurrence relation,Bijective proof,Floor and ceiling functions,Mathematics | Journal |
Volume | Issue | ISSN |
26 | 1 | SIAM J. Discrete Mathematics, 26 2012, pp. 206-238 (33 pages) |
Citations | PageRank | References |
1 | 0.43 | 4 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alejandro Erickson | 1 | 14 | 5.84 |
| Abraham Isgur | 2 | 7 | 2.27 |
| Bradley W. Jackson | 3 | 6 | 2.16 |
| Frank Ruskey | 4 | 906 | 116.61 |
| Stephen M Tanny | 5 | 34 | 8.06 |