Number of compositions of $k$ in which the maximal part is $m$: asymptotic formula? I am interested in an asymptotic formula $f(m,k)$ as $k\rightarrow\infty$. Starting points include the following two previous Stackechange questions


*

*Compositions of $n$ with largest part at most $m$

*Maximum run in binary digit expansions
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$?  
 A: $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.

