show/hide this revision's text 3 deleted 21 characters in body; added 16 characters in body

You are essentially looking at a graph (loops allowed) whose vertex set is $V=\{1,2,\dots,n\}$ with edges $E=\{(i,j) \ | \ |i-j|\le k\}$. These graphs are called path-schemes, see my answer here.

Let $A$ be the adjacency matrix of this graph, then $\sum_{r\le k} N_k$ is equal the sum of all entries in $A^m$ lying on or above the diagonal, A^{m-1}$, because $(A^m)_{ij}$ (A^{m-1})_{ij}$ is the number of walks in the graph of length $m$. m-1$ from $i$ to $j$. I don't expect a simple expression in the end, however since $A$ is a Toeplitz matrix the calculations should be friendly.
show/hide this revision's text 2 added 8 characters in body

You are essentially looking at a graph (loops allowed) whose vertex set is $V=\{1,2,\dots,n\}$ with edges $E=\{(i,j) \ | \ |i-j|\le k\}$. These graphs are called path-schemes, see my answer here.

Let $A$ be the adjacency matrix of this graph, then $\sum_{r\le k} N_k$ is equal the sum of all entries in $A^m$ lying on or above the diagonal, because $(A^m)_{ij}$ is the number of walks in the graph of length $m$. I don't expect a simple expression in the end, however since $A$ is circulant a Toeplitz matrix the calculations should be friendly.
show/hide this revision's text 1

You are essentially looking at a graph (loops allowed) whose vertex set is $V=\{1,2,\dots,n\}$ with edges $E=\{(i,j) \ | \ |i-j|\le k\}$. These graphs are called path-schemes, see my answer here.

Let $A$ be the adjacency matrix of this graph, then $\sum_{r\le k} N_k$ is equal the sum of all entries in $A^m$ lying on or above the diagonal, because $(A^m)_{ij}$ is the number of walks in the graph of length $m$. I don't expect a simple expression in the end, however since $A$ is circulant the calculations should be friendly.