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. 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. 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.