I am interested in an asymptotic formula $f(m,k)$ as $k\rightarrow\infty$. Starting points include the following two previous Stackechange questions

as well as the following sequence corresponding to $m=3$: https://oeis.org/A000100. For $m=2$, it involves Fibonacci numbers and an exact formula is easy to obtain. Exact formulas (based on recursions) are available for all $m$ but cumbersome. It seems that asymptotically, we have:

$f(m,k) = a_1 \cdot r_1^k + a_2 \cdot r_2^k + \cdots$

where $r_1 > r_2 > \cdots$ are the (real?) roots of $r^m=1+r+r^2 + \cdots + r^{m-1}$. Is this correct, and if yes, what are the coefficients $a_1, a_2$ and so on? At least, what is the dominant coefficient $a_1$?


$r^m=1+r+r^2 + \cdots + r^{m-1}$ is correct. If $c(k,m)$ is the number of compositions of $k$ with parts of at most $m$, for $k \gt m$ the recurrence is $c(k,m)=c(k-1,m)+c(k-2,m)+\ldots c(k-m,m)$ because you can make a composition of $k$ by starting with one of $k-m$ to $k-1$ and adding the proper number. The usual technique of finding the characteristic polynomial for a recursion relation gives the equation you gave.

This gives $$r^m=\frac {r^m-1}{r-1}\\ r^{m+1}-r^m=r^m-1\\r^{m+1}-2r^m+1=0$$ If $m$ is large the dominant root will be just less than $2$. If we write $r=2-a$ with $a \ll 1$ we have $$2(2-a)^m-(2-a)^{m+1}=1\\ a(2-a)^m=1$$ and to first order $a\approx 2^{-m}$ We could write $a=\frac 1{(2-a)^m}$ and iterate to convergence to get a better value. By the time $m=15$ we get three place accuracy with just $a\approx 2^{-m}$

I just fed the $m=10$ case to Alpha. The dominant root is near $r=2$ as expected. The rest seem to be roughly on the circle with radius $1$ in the complex plane. The same thing happened for $[m=15][2]$. I would expect it to be general. If $r^m=1, r^{m+1}-2r^m+1 =r-1$ and we don't have to perturb $r$ much to make it work. enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.