# 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 recursive analysis is also possible.

Let $P_k(n)$ be the set of $k$-term combinatorial progressions of order $2$ in $[n]$, and let $p_k(n)=|P_k(n)|$. I claim that $$p_{k+1}(n+1)=p_k(n)+p_k(n-1)\tag{1}$$

for $k,n\ge 1$, with initial conditions $p_1(n)=n$ for all $n\ge 1$ and $p_k(0)=0$ for all $k\ge 1$.

Proof: Clearly $p_k(n)=0$ if $k>n$, and $p_k(k)=1$, so $(1)$ holds for $1\le n\le k$.

Let $P_k^'(n)$ be the set of progressions in $P_k(n)$ that contain $n$, and let $p_k^'(n)=|P_k^'(n)|$. Every progression in $P_{k+1}^'(n+1)$ is uniquely obtained by appending $n+1$ to a progression in $P_k^'(n)\cup P_k^'(n-1)$, so $p_{k+1}^'(n+1)=p_k^'(n)+p_k^'(n-1)$. Moreover, $$P_{k+1}(n+1)\setminus P_{k+1}^'(n+1)=P_{k+1}(n)\;,$$ so

\begin{align*} p_{k+1}(n+1)&=p_{k+1}(n)+p_k^'(n)+p_k^'(n-1)\\ &=p_{k+1}(n)+\Big(p_k(n)-p_k(n-1)\Big)+\Big(p_k(n-1)-p_k(n-2)\Big)\\ &=p_{k+1}(n)+p_k(n)-p_k(n-2)\tag{2}\;. \end{align*}

Now assume that $(1)$ holds for some $n$ and $k$; then by $(2)$ we have

\begin{align*} p_{k+1}(n+2)&=p_{k+1}(n+1)+p_k(n+1)-p_k(n-1)\\ &=p_k(n)+p_k(n-1)+p_k(n+1)-p_k(n-1)\\ &=p_k(n+1)+p_k(n)\;; \end{align*}

this completes the proof of $(1)$. $\dashv$

Next,

$$p_k(n)=(k+1)2^{k-2}+(n-2k+1)2^{k-1}\tag{3}$$ for $n\ge 2k-1$.

Proof: Let $d=n-(2k+1)$, and rewrite $(3)$ as $$p_k(2k-1+d)=(k+1+2d)2^{k-2}$$ for $k\ge 1$ and $d\ge 0$. For $k=1$ this is simply the initial condition $p_1(d+1)=d+1$, and $(1)$ then gives us \begin{align*} p_{k+1}(2k+1+d)&=p_k(2k+d)+p_k(2k-1+d)\\ &=\big(k+1+2(d+1)\big)2^{k-2}+(k+1+2d)2^{k-2}\\ &=(2k+4+4d)2^{k-2}\\ &=(k+2+2d)2^{k-1} \end{align*} to complete the induction. $\dashv$

In fact it’s not hard to check that $(3)$ gives the correct result for $n=2k-2$ as well and exceeds the correct value by $1$ when $n=2k-3$.

I tried to see what happens when $n\le 2k$. For this it was convenient to set $a_n(k)=p_k(n+k)$. It’s not hard to see that $a_0(k)=1$ for $k\ge 1$, and if we further set $a_n(0)=1$, $(1)$ implies (after a bit of work) that $$a_n(k)=n+1+\sum_{i=1}^{k-1}a_{n-1}(k)$$ for $k>0$. By direct computation we then find that

\begin{align*} a_1(k)&=\binom{k+1}1\\ a_2(k)&=2\binom{k+1}0+\binom{k+1}2\\ a_3(k)&=2\binom{k+1}1+\binom{k+1}3\\ a_4(k)&=3\binom{k+1}0+2\binom{k+1}2+\binom{k+1}4\\ a_5(k)&=3\binom{k+1}1+2\binom{k+1}3+\binom{k+1}5\\ a_6(k)&=4\binom{k+1}0+3\binom{k+1}2+2\binom{k+1}4+\binom{k+1}6\;, \end{align*}

which leads to the obvious conjecture that

$$a_n(k)=\sum_{i=1}^{\lceil n/2\rceil}i\binom{k+1}{n+2-2i}\;.$$

This conjecture is easily proved by induction:

\begin{align*} a_{2n+1}(k)&=2n+2+\sum_{i=1}^{k-1}a_{2n}(k)\\ &=2n+2+\sum_{i=1}^{k-1}\left(\binom{i+1}n+2\binom{i+1}{n-2}+\ldots+(n+1)\binom{i+1}0\right)\\ &=\binom{k+1}{n+1}+2\binom{k+1}{n-1}+\ldots+(n+1)\binom{k+1}1\\ &=\sum_{i=1}^{n+1}i\binom{k+1}{2n+3-2i}\;, \end{align*}

and

\begin{align*} a_{2n+2}(k)&=2n+2+\sum_{i=1}^{k-1}a_{2n+1}(k)\\ &=2n+3+\sum_{i=1}^{k-1}\left(\binom{i+1}{n+1}+2\binom{i+1}{n-1}+\ldots+(n+1)\binom{i+1}1\right)\\ &=\binom{k+1}{n+2}+2\binom{k+1}{n}+\ldots+(n+1)\binom{k+1}2+(n+2)\binom{k+1}0\\ &=\sum_{i=1}^{n+2}i\binom{k+1}{2n+4-2i}\;. \end{align*}

Unfortunately, while this is rather pretty, it doesn’t seem to be very tractable: I’ve had no luck coming up with a closed form.

-
Can you explain the following line: "Every progression in $P'_{k+1}(n+1)$ is uniquely obtained by appending $n+1$ to a progression in $P′_k(n)\cup P′_k(n−1)$." For $k=3$, $n=7$ consider the progression $1,3,5,8$. Am I missing something here? – Shahab May 21 '12 at 6:55
@Shahab: $\{1,3,5,8\}$ isn’t a progression of order $2$: the last gap is too big. – Brian M. Scott May 21 '12 at 6:59
I think you misunderstand, the gaps 3-1=2, 5-3=2, 8-5=3 all belong to the set $\{2,3\}$ which has order 2. Hence it is a 4-term combinatorial progression of order 2. – Shahab May 21 '12 at 7:33
@Shahab: You’re right: I was trying to find a version of André’s argument that would give more information about the cases with small $n$, and didn’t go back to check the definition carefully; he and I both oversimplified the definition to require that all gaps be either $1$ or $2$. I’ll try to make time to look at this again. – Brian M. Scott May 21 '12 at 7:49

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!

-
Isn't $\sum i\tbinom{m}{i}=m2^{m-1}$? Why have you written "It is $2^{m-1}$" in your second last line? Also, may I conclude that for $N>2m$, the answer is $N2^{k-1}-3(k-1)2^{k-2}$? – Shahab May 12 '12 at 3:58
@Shahab: Thanks for spotting the typo. Indeed it is $m2^{m-1}$. And yes, we get, in my notation, $N2^m -(3m)2^{m-1}$, which, in terms of $k$, is what you wrote above. – André Nicolas May 12 '12 at 4:45