Number of compositions of $n$ such that each term is less than equal to $k.$ Let $n$ be an integer $\geq 1.$ Then a partition of $n$ is a sequence of positive integers (greater than equal to $1$) such that their sum equals $n.$ So for instance if $n=4$ then 
$$[[4], [1, 3], [1, 1, 2], [1, 1, 1, 1], [1, 2, 1], [2, 2], [2, 1, 1], [3, 1]]$$
is a collection of all partitions of $n$ with order. Clearly for any $n$ the number of such ordered partitions is $2^{n-1}.$ However I want to count the number of paritions of $n$ where each integer in the parition is less than equal to some integer $k.$ So for instance if $n=4$ and $k=2$ then 
$$[[1, 1, 2], [1, 1, 1, 1], [1, 2, 1], [2, 2], [2, 1, 1]]$$
is a collection of all the $2$-partitions of $4.$ Is there a general formula for finding this or maybe an asymptotic expression? 
 A: I think it may be easier to deal with the simpler case of $k=2$ first. Let's find some easy, small values first:
$$n=1\rightarrow [[1]]\rightarrow f(1)=1$$
$$n=2\rightarrow [[1,1],[2]]\rightarrow f(2)=2$$
$$n=3\rightarrow [[1,1,1],[2,1],[1,2]]\rightarrow f(3)=3$$
As you have shown, $f(4)=5$.
$$n=5\rightarrow [[1,1,2,1],[1,1,1,1,1],[1,2,1,1],[2,2,1],[1,1,2,1],[1,1,1,2],[2,1,2],[1,2,2]]\rightarrow f(5)=8$$
Hopefully you notice the pattern: This is the Fibonacci sequence. The reason this is the Fibonacci sequence is because for any $n$, a partition with $k=2$ will end in either $1$ or $2$. If it ends in $1$, then we simply add $1$ onto a partition from $n-1$. If it ends in $2$, then we simply add $2$ onto a partition from $n-2$. This gives us the following recurrence:
$$f(n)=f(n-1)+f(n-2)$$
And, of course, this is the Fibonacci recurrence.
Now, let's extend this reasoning to general $k$. First, let's define $f(n, k)$ to be the number of partitions of $N$ where the positive integers involved are at most $k$. Then, let's define $f(n,k)=0$ for any $n < 0$ because we only want to allow for positive integers and $f(0,k)=1$ for any $k$ since the only way to partition $0$ is with the empty set.
Since the integers must be at most $k$, this means in every partition, we are adding some new integer $l \leq k$ every time. Thus, if we take $l$ away, we get a partition of $n-l$. Therefore, the number of partitions of $n$ must be the partitions of $n-1$ plus that of $n-2$ plus that of $n-3$ ... and so on, until $n-k$. In other words:
$$f(n,k)=\sum_{l=1}^k f(n-l,k)$$
This is a generalization of the Fibonacci numbers. For $k=3$, it gets you the tribonacci numbers, for $k=4$, if gets you the tetranacci numbers, then $k=5$ is pentanacci, $k=6$ is heptanacci, etc.
Thus, the pattern you are studying is simply a higher-order form of the Fibonacci numbers.
A: Generating functions look like the way to go. Finding $m$ pieces, each of size at most $k$, that sum to $n$, has generating function $(x+x^2+\cdots+x^k)^m$; the coefficient of $x^n$ is the number of ways. Then, we want the total number of ways, over all possible numbers of pieces, so we get
\begin{align*}F(x) &= \sum_{m=0}^{\infty} (x+x^2+\cdots+x^k)^m\\
&= \frac{1}{1-(x+x^2+\cdots+x^k)}\\
F(x) &= \frac{1}{1-\frac{x-x^{k+1}}{1-x}} = \frac{1-x}{1-2x+x^{k+1}}\end{align*}
If you're looking for specific coefficients, it's easiest to use the Fibonacci-like recursion noted in Noble Mushtak's answer, or the telescoped version $a_{n+1}=2a_n-a_{n-k}$. The initial conditions are $a_0=a_1=1,a_{-1}=\cdots=a_{-k+1}=0$. For the asymptotics? That'll come from the pole of $F$ nearest to zero - namely, the unique positive root $r$ of $x^k+\cdots+x^2+x-1=0$. For $k>1$, $r\in [0,1]$. The $n$th term will be approximately proportional to $r^{-n}$. An exact formula? You'd have to find all the roots of that polynomial and run partial fractions. The generating function then splits up as several terms of the form $\frac{b_j}{x-c_j}$, each of which gives us a geometric series. It's all fine in theory, but that first step of solving the polynomial is a doozy.
A: First a note about terminology:
 - a Partition of a positive integer $n$ is a non-decreasing sequence of positive integers summing to $n$;
 - a Composition of a positive integer $n$ is an unordered sequence of positive integers summing to $n$.
That premised, you are speaking of the number of Compositions of $n$, whose terms (parts) are not-greater than $k$.
Consider the case in which you seek for the number of compositions of the positive number $s+m$
into $m$ parts not exceeding $r+1$
$$
{\rm No}{\rm .}\,{\rm of}\,{\rm solutions}\,{\rm to}\;\left\{ \matrix{
  {\rm 1} \le {\rm integer}\;y_{\,j}  \le r + 1 \hfill \cr 
  y_{\,1}  + y_{\,2}  + \; \cdots \; + y_{\,m}  = s + m \hfill \cr}  \right.
$$
that's the same as
$$N_{\,b} (s,r,m) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered}
  0 \leqslant \text{integer  }x_{\,j}  \leqslant r \hfill \\
  x_{\,1}  + x_{\,2}  +  \cdots  + x_{\,m}  = s \hfill \\ 
\end{gathered}  \right.$$
$N_b$ is given by the following sum
$$
N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers  }s,m,r} \right.\quad  =
\sum\limits_{\left( {0\, \leqslant } \right)\,\,j\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} 
{\left( { - 1} \right)^k \binom{m}{j}
 \binom
 { s + m - 1 - j\left( {r + 1} \right) } 
 { s - j\left( {r + 1} \right)}\ }
$$
as widely explained in this related post.  
Going back to your case, the 
number of compositions of $n$ into $m$ parts not greater than $k$
will then be
$$
\eqalign{
  & N_c (n,k,m)\quad \left| {\;1 \le n,m,k} \right.\quad  =   \cr 
 & = \sum\limits_{\left( {0\, \le } \right)\,\,j\,\,\left( {\, \le \,m} \right)} {\left( { - 1} \right)^{\,j} \binom{m}{j}
\binom{n - 1 - j\,k}{ n - m - j\,k}} \cr}
$$
while the
overall number of compositions of $n$ into parts not greater than $k$
 will be the sum
of the above for $0 \le m$ : if the sum extends over $n$ it will maintain the value $2^{n-1}$.
$$ \bbox[lightyellow] {  
\eqalign{
  & N_{c\,t} (n,k)\quad \left| {\;0 \le n,k \in \mathbb Z} \right.\quad  =   \cr 
  &  = \sum\limits_{0\, \le \,\,m} {\;\sum\limits_{\left( {0\, \le } \right)\,\,j\,\,\left( {\, \le \,m} \right)} {\left( { - 1} \right)^{\,j}
    \binom{m}{j} \binom{ n - 1 - j\,k}{n - m - j\,k}
} }  \cr} 
}$$
In the example with $n=4$, the above gives for $k=1,2,3,4$
$$
1,5,7,8
$$
which in fact correspond to
$$
\eqalign{
  & \left[ {1,1,1,1} \right]  \cr 
  & \left[ {1,1,1,1} \right]\left[ {1,1,2} \right]\left[ {1,2,1} \right]\left[ {2,1,1} \right]\left[ {2,2} \right]  \cr 
  & \left[ {1,1,1,1} \right]\left[ {1,1,2} \right]\left[ {1,2,1} \right]\left[ {2,1,1} \right]\left[ {2,2} \right]\left[ {1,3} \right]\left[ {3,1} \right]  \cr 
  & \left[ {1,1,1,1} \right]\left[ {1,1,2} \right]\left[ {1,2,1} \right]\left[ {2,1,1} \right]\left[ {2,2} \right]\left[ {1,3} \right]\left[ {3,1} \right]\left[ 4 \right] \cr} 
$$
Finally note that:
 - $N_{c\,t}(n,k)$ correctly checks with OEIS seq. A126198, which provides further properties of these numbers;
 - the o.g.f. of $N_{c\,t}$ in $n$ is in fact the $F(x)$ given by @jmerry's answer (re. to the o.g.f. for $N_b$ given in related post);
$$
\sum\limits_{0\, \le \,\,n} {N_{c\,t} (n,k)\,x^{\,n} }  = {{1 - x} \over {1 - 2x + x^{\,k + 1} }}
$$
 - $N_{c\,t}(n,k)$ satisfies the recursion given by @NobleMushtak
$$
N_{c\,t} (n,k) = \sum\limits_{j = 1}^k {N_{c\,t} (n - j,k)}  + \left[ {n = 0} \right]
$$
where $[P]$ denotes the Iverson bracket.
