Compositions of $n$ with largest part at most $m$ This is a problem from Stanley's Enumerative Combinatorics that I'm failing at a bit (lot):
Let $\bar{c}(m,n)$ denote the number of compositions of $n$ with largest part at most $m$.  Show that $$\sum_{n\geq 0}\bar{c}(m,n)x^n={{1-x}\over{1-2x+x^{m+1}}}$$
Some definitions:  A composition of $n$ is an $ordered$ list of positive integers that equals $n$.  If $\{a_1,...,a_k\}$ is one such composition, we say that the composition has $k$ $parts$.
I know it's pretty traditional to list a "what you've done so far" but I'm really about as blindly stuck as can be.
 A: I tried my own way and got something slightly different - more on that in a second. Let $c(m,n,k)$ be the number of integer compositions with largers part $\le m$ and exactly $k$ parts. Then
$$\sum_n c(m,n,k)x^n=\left.\sum_{p_1=1}^m\cdots\sum_{p_k=1}^m x_1^{p_1}\cdots x_k^{p_k}\right|_{x_1=x_2=\cdots=x_k=x}=\left(x\frac{1-x^m}{1-x~~~}\right)^k$$
and therefore
$$\sum_n c(m,n)x^n=\sum_n\left[\sum_{k\ge1}c(m,n,k)\right]x^n=\sum_{k\ge1}\sum_nc(m,n,k)x^n$$
$$=\sum_{k\ge1}\left(x\frac{1-x^m}{1-x~~~}\right)^k=\frac{\displaystyle x\frac{1-x^m}{1-x~~~}}{\displaystyle 1-x\frac{1-x^m}{1-x~~~}}=\frac{x(1-x^m)}{1-2x+x^{m+1}}.$$
Note that
$$\frac{x(1-x^m)}{1-2x+x^{m+1}}=\frac{1-x}{1-2x+x^{m+1}}-1,$$
so the given answer and mine differ merely by $1$. What's the deal? The reason we need to add $1$ I presume is that $n=0$ has one integer composition, namely the empty set (it is the empty sum). At least that's what OEIS says, I haven't actually seen the textbook's definition/convention for $0$.
A: This can be solved in two ways, both quite easy.
For the first, note that the given fraction simplifies due to the decomposition $1-2x+x^{m+1}=(1-x)(1-x-x^2-\cdots-x^m)$ to the rational function
$$
\frac1{1-x-x^2-\cdots-x^m}.
$$
The coefficients $a_i$ of the corresponding power series satisfy $a_0=1$ and the recurrence
$$
  a_i=a_{i-1}+a_{i-2}+\cdots+a_m \qquad\text{for $i>0$,}
$$
where  terms with negative index are taken to be$~0$. But taking $a_i=\bar c(n,i)$ this recurrence can be easily seen to be satisfied: a composition of $i>0$ has a final part$~k$ with $1\leq k\leq m$, and removing that part leaves a composition of $i-k$ into parts at most$~m$, each obtained exactly once, so $\bar c(n,i)=\sum_{k=1}^m\bar c(n,i-k)$.
The other way is to use the form of the fraction given in the question directly. Its denominator indicates that the recurrence
$
  a_i=2a_{i-1}-a_{i-(m+1)}
$
should be satisfied for sufficiently large$~i$. Here each composition of $i$ can be obtained in one of two ways from a composition of $i-1$: either adding a part $1$, or by increasing the last part by$~1$. However the latter method cannot be applied to all compositions of $i-1$ into parts at most $m$, since it may make the final part $m+1$. The number of such forbidden extensions equals $\bar c(n,i-(m+1))$ (each composition counted by that number produces one when a $m+1$ added at its end), so that number must be subtracted in the recurrence. With again the convention that recurrence terms with negative indices are taken to be $0$, the recurrence relation gives the correcct number for $i>1$, but the value$~2$ it would give for $i=1$ is one too much (since the composition of $0$ has no part to increase). This is reflected by the term "$-x$" in the numerator of the fraction $\frac{1-x}{1-2x+x^{m+1}}$.
A: Hazy idea: I'd try to derive a relation $(\dagger)$ between for instance $\bar{c}(m, n)$ and $\bar{c}(m, n-1)$ (or even with multiple terms $\bar{c}(m, n-k)$), or something similar. The goal would then be to find an EDP for $f\colon x \to \sum_{n=0}^\infty \bar{c}(m, n)x^n$ by differentiating term by terms and using $(\dagger)$.
Then, olving the EDP for $f$, one could get a closed-form expression of it — hopefully the one you're asked to prove.
Of course, the main step is to find (via combinatorics?) the said relation.
