Properties of k-Descending Trees

Abstract

For any real-valued $k>1$, we consider the tree rooted at 0, where each positive integer $n$ has parent $\lfloor \frac{n}{k}\rfloor$. The average number of children per node is $k$, thus this definition gives a natural way to extend $k$-ary trees to irrational $k$. We focus on the sequence $r_d$: the count of nodes at depth $d$. We first prove there exists some constant $\rho (k)$ such that $r_d\sim \rho (k)\cdot k^d$. We then study a family of values $k=\frac{a+\sqrt{a+4b}}{2}$, where we prove the sequence satisfies the exact recurrence $r_d=a\cdot r_{d-1}+b\cdot r_{d-2}$. This generalizes a special case when $k$ is the golden ratio and $r_d$ is the Fibonacci sequence.

arXiv commentThis was research presented at the Worldwide Federation of National Math Competitions in Bulgaria in 2022. Additional Code/Data on github. Appendix contains code/figures as well. Will be published in the WFNMC Journal