8
$\begingroup$

I hope this question isn't too simple for MO. Combinatorics is not my forte.

I have two positive integers $n,k$ that define a resultant integer. I am running an experiment and I have a collection of sequences of integers as follows. For each $n$ I list the results for $k = 1,\dots 20$ although there are more integers that follow the same pattern.

  • $n = 2$ gives 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11.

This is a simple sequence with an obvious pattern.

  • $n = 3$ gives 1, 3, 5, 8, 11, 15, 19, 24, 29, 35, 41, 48, 55, 63, 71, 80, 89, 99, 109, 120

The differences between consecutive numbers is exactly the sequence for $n = 2$ (excluding the first number $1$ in the preceding sequence.

  • $n = 4$ gives $1, 4, 9, 17, 28, 43, 62, 86, 115, 150, 191, 239, 294, 357, 428, 508, 597, 696, 805, 925$.

Again the differences between consecutive numbers is exactly the sequence for $n = 3$ (excluding the first number $1$ in the preceding sequence).

And it continues this way for larger values of $n$.

Assuming this is indeed the general rule, how could one find a closed form formula for arbitrary positive $n ,k$ (with $n \geq 2$).

$\endgroup$
  • $\begingroup$ You have $k/2 + (3+(-1)^k)/4$ for $n=2$. For $n=3$, you can find the formula of the cumulative sum, and then again for $n=4$ etc. For example David Gleich: "Finite Calculus: A Tutorial for Solving Nasty Sums" might help in finding nice forms of the formulas, but I don't know if there's anything that could qualify as "closed form" for general $n$. $\endgroup$ – Janne Kokkala Apr 20 '17 at 10:48
  • $\begingroup$ oeis.org/A005744 is a good place to start $\endgroup$ – Matt F. Apr 20 '17 at 13:09
14
$\begingroup$

It's worth to consider the sequence for $n=1$: $$1,1,0,1,0,1,0,\dots$$ Let $s_k^n$ denote the $k$-th term of the $n$-th sequence. In particular, $s_1^1=1$ and for $k>1$, $s_k^1$ equals 1 if $k$ is even and $0$ if $k$ is odd.

Then for $n>1$, we have $$s_k^{n} = \sum_{i_{n-1}=1}^k s_{i_{n-1}}^{n-1} = \cdots = \sum_{i_{n-1}=1}^k \sum_{i_{n-2}=1}^{i_{n-1}} \cdots \sum_{i_1=1}^{i_2} s_{i_1}^1=\sum_{i_1,i_2,\dots,i_{n-1}\atop 1\leq i_1\leq i_2\leq \dots \leq i_{n-1}\leq k} s_{i_1}^1$$ $$ = \sum_{i_1=1}^{k} s_{i_1}^1 \sum_{i_2,i_3,\dots,i_{n-1}\atop i_1\leq i_2\leq \dots \leq i_{n-1}\leq k} 1 = \sum_{i_1=1}^{k} s_{i_1}^1 \left(\!\!\binom{k-i_1+1}{n-2}\!\!\right) = \sum_{i_1=1}^{k} s_{i_1}^1 \binom{k-i_1+n-2}{n-2},$$ where $\left(\!\!\binom{k-i_1+1}{n-2}\!\!\right) = \binom{k-i_1+n-2}{n-2}$ gives the number of combinations with repetitions $(i_2,i_3,\dots,i_{n-1})$ from the set $\{t_1,i_1+1,\dots,k\}$ of size $k-i_1+1$.

Recalling the formula for $s_{i_1}^1$, we have $$s_k^n = \binom{k+n-3}{n-2} + \sum_{\ell=1}^{\lfloor k/2\rfloor} \binom{k+n-2-2\ell}{n-2},$$ which holds for all $n>1$ and $k\geq 1$.

UPDATE. Noticing that $\binom{k+n-2-2\ell}{n-2}$ is the coefficient of $x^{n-2}$ in $(1-x)^{-(k+1-2\ell)}$, the formula above can be further reduced to the sum of $O(n)$ terms (which may be preferable when $k$ is large as compared to $n$): $$s_k^n = \binom{k+n-3}{n-2} + \frac{(k+1)\bmod 2}{2^{n-1}} + \sum_{i=1}^{n-1} \binom{k-2+i}{i}\frac{1}{2^{n-i}}.$$

$\endgroup$
  • 3
    $\begingroup$ I understand that Anush asked for a closed form, but the generating function $\sum s_k^n x^n y^k$ is just too nice: $$-\frac{{\left(x^{2} - x - 1\right)} y^{2}}{{\left(x + y - 1\right)} {\left(x + 1\right)} {\left(x - 1\right)}}$$ $\endgroup$ – Martin Rubey Apr 20 '17 at 14:00
  • $\begingroup$ @MartinRubey: Indeed. Its "niceness" essentially follows from that of the g.f. for combinations with repetitions: $$\frac{1-x}{1-x-y}.$$ $\endgroup$ – Max Alekseyev Apr 20 '17 at 14:08
  • $\begingroup$ I think this means $\frac12 \binom{n+k-2}{k-1} \le s^n_k \le \binom{n+k-2}{k-1}$ which is very useful. $\endgroup$ – Anush Apr 22 '17 at 5:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.