Number of combinatorial progressions A $k$-term combinatorial progression of order $2$ is defined as a set of positive integers $A=\{x_1<x_2<\cdots x_k\}$ such that the set $\{x_{i+1}-x_i:1\le i\le k-1\}$ has cardinality at most $2$. 
My question is given a positive integer $N$, how many $k$-term combinatorial progressions of order $2$ will exist in $\{1,2\cdots N\}$? If not a closed formula can a reasonable upper bound for this number be deduced? For example if we replace the term combinatorial progression with arithmetic progression then a reasonable upper bound is $N^2/k^2$.
Any help or ideas please.
Thanks.
 A: It is typographically easier to work with the number $m$ of "gaps." So $m=k-1$.
We will assume that $N$ is larger than $2m$. We have not done the analysis for $N$ between $m+1$ and $2m$, and are not optimistic about obtaining a simple closed form for $N$ in that range.   
There is precisely $1$ way to have the sum of the $m$ gaps equal to $m$. I prefer to call this $\binom{m}{0}$.
There are $\binom{m}{1}$ ways to have the sum of the $m$ gaps be equal to $m+1$, for we must choose $1$ place to put a gap of length $2$, with the rest of length $1$.
There are $\binom{m}{2}$ ways to have the sum of the gaps be equal to $m+2$, for we must choose $2$ places to put a gap of length $2$. 
And so on. Finally, there are $\binom{m}{m}$ ways to have the sum of the gaps be equal to $2m$.
If the sum of the lengths of the gaps is $m$, then $x_1$ can be any of $1$ to $N-m$. If the sum of the  lengths is $m+1$, then $x_1$ can be any of $1$ to $N-m+1$, and so on. So the number of $(m+1)$-term combinatorial progressions of order $2$ is
$$\binom{m}{0}(N-m)+\binom{m}{1}(N-m-1)+\binom{m}{2}(N-m-2))+\cdots +\binom{m}{m}(N-2m).$$
One can find an explicit formula for the sum. The terms in $N$ have sum $N2^m$. We need to subtract 
$$m\binom{m}{0}+(m+1)\binom{m}{1}+(m+2)\binom{m}{2}+\cdots +2m\binom{m}{m}.$$
This sum can be broken up into two parts, $\sum_{i=0}^m m\binom{m}{i}$, which is $m2^m$, and $\sum_{i=0}^m i\binom{m}{i}$, which is not difficult, we can pick it up from the expected value of a binomial, or by symmetry.  It is $m2^{m-1}$.
There is undoubtedly a nicer generating functions approach!
