5
$\begingroup$

A $k$-term combinatorial progression of order $2$ is defined as a set of positive integers $A=\{x_1 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.

2 Answers 2

1

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.

  • 0
    @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.2012-05-21
1

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!

  • 0
    @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.2012-05-12