Counting number of $k$-sequences I am studying a special type of a sequence on the naturals which I am calling a weak arithmetic progression. Formally I call a k-sequence $x_1<x_2<\cdots< x_k$ a weak arithmetic progression (WAP) if $\exists d\in \mathbb{N}$ such that $x_{i+1}-x_i\in\{1,d\}$. Now given two natural numbers $n\ge k\ge 1$, I wish to count the number of WAP's of length k within $\{1,2,3\ldots, n\}$, i.e. the number of WAP's of length k where each WAP consists of elements from $\{1,2\cdots n\}$. This is how I am reasoning:
First fix a $d$. Consider any collection of $k$ numbers (as yet identified as $x_1,\cdots x_k$) and write them with spaces in the middle. We will count in how many ways we can put either $d$ or $1$ in the $k-1$ spaces or gaps between these numbers. Now if all the $k-1$ gaps between the numbers have to be filled up by $d$, then the first element of the $k$-WAP can be chosen in $n-(k-1)d$ ways. I will refer to this as $(n-(k-1)d)\tbinom{k-1}{0}$. If all but one of the gaps between the numbers have to be filled up by $d$, then there are $(n-(k-2)d-1)\tbinom{k-1}{1}$ ways, the binomial coefficient indicating where to place the number $1$ in the $k-1$ gaps. Likewise for all but $r$ gaps being filled up by $d$ there would be $(n-(k-r-1)d-r)\tbinom{k-1}{r}$ ways and so for a fixed $d$ there are $\sum_{r=0}^{k-1}(n-(k-r-1)d-r)\tbinom{k-1}{r}=(n-d(k-1))2^{k-1}+(d-1)(k-1)2^{k-2}$ $k$-WAPs. Now to get the total number of $k$-WAPs I sum over $d$ from $2$ to $n-k+1$, i.e. $\sum_{d=2}^{n-k+1}\Big ((n-d(k-1))2^{k-1}+(d-1)(k-1)2^{k-2}\Big )$ and furthermore since double counting of consecutive k-terms occurs for each $d$ in this sum, we subtract $(n-k+1)(n-k-1)$, i.e the final answer is $\sum_{d=2}^{n-k+1}\Big((n-d(k-1))2^{k-1}+(d-1)(k-1)2^{k-2}\Big )-(n-k-1)(n-k+1)$.
My questions are:


*

*Is the above reasoning correct? If not, then what is the correct approach? 

*What is a good upper bound for the above sum which can be solved for $n$? I need $n$ as a function of $k$ for further study.


Thanks 
 A: I suspect that your approach is more or less correct, but it's difficult to me to follow. Let's simplify it a little.
Our statement, if I understand it right, is: given positive integers $(n,k,d)$, we want to count $N(n,k,d)$ the number of sequences $x_1, x_2 \cdots x_k$ with $  x_{i+1}−x_i \in \{1,d\}$ and $x_k\le n$
It's simpler to work with $d_i = x_{i+1}−x_i $ ($d_i \in \{1,d\}, \sum_{i=1}^k d_i =D\le n$) (let's assume $x_0=0$) .
And it's even simpler to define $$b_i = \frac{d_i-1}{d-1}$$ 
so that $b_i \in \{0,1\}$, and  $\sum_{i=1}^k b_i = W = \frac{D-k}{d-1} \le m = \frac{n-k}{d-1}$
So, we have reduced the problem to that of counting the number of bit strings of length $k$ that have weight (number of ones: $W=\sum_{i=1}^k b_i $) less or equal than $m = \frac{n-k}{d-1}$
This is simply $$\sum_{w=0}^{ w_M } {k \choose w} \hspace{1cm } w_M = \min\left(k,\left\lfloor \frac{n-k}{d-1} \right\rfloor\right)$$
For large $n,k$, this can be approximated by a gaussian integral.
Edited: I (wrongly) assumed that $d$ was given. If it's not, we can sum over the possible values,
but letting asside the zero-weight case (unit gaps in the original statement). So, the total number of sequences would be
$$ 1 + \sum_{d=2}^{n-k+1}  \sum_{w=1}^{ w_M } {k \choose w}$$
with $w_M$ as above. This can be polished a little but perhaps not much.
Added: A good approximation for large $n,k$ (and probably some bounds) can be obtained by swapping the sums:
Because 
$$\sum_{d=2}^{n-k+1}  \sum_{w=1}^{ w_M } {k \choose w} \approx \sum_{w=1}^{k} \sum_{d=2}^{(n-k)/w+1}   {k \choose w}
= \sum_{w=1}^{k} \frac{n-k}{w} {k \choose w} = (n-k) S_k$$
with $S_k = \sum_{w=1}^{k} \frac{1}{w} {k \choose w}$
So, if $N(n,k)$ is the total counting of sequences and we want to solve (approximate/bound) for $n$, we'd get:
$$n\approx   \frac{N(n,k)-1}{S_k}+k$$
For approximations of $S_k$, see here. Plugging the most rough approximation, $S_k \approx \frac{2^{k+1}}{k}$, we get
$$ n \approx 2 \, k \, N(n,k) 2^{-k}+k$$
Added: I've not proven, but I conjecture (both from the derivation and from numeric valeus) that the above expression
$$N(n,k) \approx 1 + (n-k) S_k \tag{1}$$
is actually an upper bound. One can also add a small correction term (slightly better approximation, but now it's not a strict bound) but substracting $1/2$ in the inner summation (to account for the low-rounding effect of the floor function). Then we get
$$N(n,k) \approx \frac{3}{2} + (n-k) S_k - 2^{k-1} \tag{2}$$
this improves the approximation for medium values of $k$. Here's an graph of the ratio of the exact value over the approximation (1) (blue) and (2) (green), for $n=30$.

