Question: For $n,k\in \mathbb{N}$, let $a_{n,k}$ denote the number of lattice paths starting at $(0,0)$ and ending at $(n,n)$, with allowed steps $(1,0)$ and $(0,1)$, such that all points $(x,y)$ on the path satisfy $x\leq y\leq x+k$.
Let $A_k(t)=\sum_{n\geq 0} a_{n,k}t^n$. Find a recurrence relation for $A_k(t)$, $k\geq 1$. Hence, or otherwise, prove that $$A_k(t)=\frac{\sum_{m=0}^{\lfloor\tfrac{k}{2}\rfloor}(-1)^{m}\binom{k-m}{m}t^m}{\sum_{m=0}^{\lfloor\tfrac{k+1}{2}\rfloor}(-1)^{m}\binom{k+1-m}{m}t^m}.$$
Approach: Let $L_k$ be such a lattice path that stays between $y=x$ and $y=k+k$. Like in the standard "Catalan" case, lets break $L_k$ apart at the point it meets the line $y=x$. We observe that each valid $L_k$ path can be broken into a sequence of paths of the form $$\{N\}\times L_{k-1} \times \{E\}.$$ Where $L_{k-1}$ is a path that stays below the line $y=x+k-1$ (because of the already taken initial $N$ step) Thus, we obtain the recurrence relation for the generating series $$A_k(t)=\frac{1}{1-tA_{k-1}(t)}.$$ Any idea how can I get the formula above from this recurrence relation other than induction?