Suitable closed form for the A079501

Question

• Let $a(n)$ be A079501 (i.e., number of compositions of the integer $n$ with strictly smallest part in the first position).

• The sequence begins with

$$ 1, 1, 2, 2, 4, 5, 8, 12, 19, 28, 45, 70, 110, 173, 275 $$

• Let

$$ b(n) = 1 + \sum\limits_{i=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\sum\limits_{j=0}^{\left\lfloor\frac{n-2i-1}{i+1}\right\rfloor}\binom{n - i(j+2) - 1}{j} $$

I conjecture that $$b(n)=a(n).$$

Here is the PARI/GP program to compute $b(n)$:

b(n) = 1 + sum(i = 1, n\2, sum(j=0, (n-2*i-1)\(i+1), binomial(n - i*(j+2) - 1, j)))

Is there a way to prove it?

Answer 1

Yes!

• $i$ is the first part in the composition
• $j + 1$ is the number of other parts in the composition
• $+1$ accounts for the case that there is only one part

Summing over $i$ and $j$, we want to count the number of $a_1,...,a_{j + 1}$ such that $$i + (i + 1 + a_1) + \cdots + (i + 1 + a_{j + 1}) = n$$ or equivalently $$a_1 + \cdots + a_{j + 1} = n - (j + 1)\cdot (i + 1) - i$$ which is $$\binom{n - (j + 1)\cdot (i + 1) - i + (j + 1) - 1}{(j + 1) - 1} = \binom{n - (j + 2)\cdot i - 1}{j}$$