2
$\begingroup$

My question is to find an explicit formula for $N_{k,n}$, if the following recursive one is known:

$$ \left\{ \begin{align} \begin{split} N_{1,n} &= 1 \text{,} \\ N_{k+1,n} &= \sum_{i = k+1}^{n-1} N_{k,i} \end{split} \end{align} \right. $$ $$ \text{for } n \in \{\,2, 3, \dots\,\}, k \in \{\,n+1, n+2, \dots\,\} \text{.} $$

I can calculate a few first terms ($N_{1,n} = 1$, $N_{2,n} = n-2$, $N_{3,n} = \frac{(n-2)(n-3)}{2}$), but unfortunately I cannot find the general solution.

New contributor
Peter is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
$\begingroup$

As mentioned in comments, one way is to notice the Hockey stick identity in the definition and then prove it matches for rest of your definition, giving the closed form $N_{k,n}=\binom{n-2}{k-1}$.

If you don't notice that at first, you can simplify the recurrence $$N_{k+1,n+1} - N_{k+1,n} = \sum_{i=k+1}^{n}N_{k,i}-\sum_{i=k+1}^{n-1}N_{k,i} = N_{k,n},$$ hence $$ N_{k+1,n+1} = N_{k+1,n} + N_{k,n}. $$ Now add base cases such as $N_{1,n}=1$ and $N_{k,2}=0$ for $k\geq 2$, which follow trivially from definitions. Again you can notice that the recurrence definition resembles Pascal's formula and you can go from there.

Eventually if all that fails, you can use a generic method for solving the last recurrence. For example, using generating functions as in the answer Solving two-dimensional recurrence relation $a_{i,\ j}\ =\ a_{i,\ j-1}\ +\ a_{i-1,\ j-1}$, you should get $f(x,y)=\sum_{k\geq 1, n \geq 2}N_{k,n}x^k y^n=\frac{xy^2}{1-y-xy}$. This in turn simplifies using geometric series into $$f(x,y)=xy^2\sum_{n=0}^{\infty}y^n(1+x)^n=xy^2\sum_{n=0}^{\infty}y^n\sum_{k=0}^{n}\binom{n}{k}x^k = \sum_{n\geq 0, k \geq 0}^{\infty}\binom{n}{k}x^{k+1}y^{n+2},$$ and so finally $$ f(x,y)=\sum_{n\geq 2, k \geq 1}^{\infty}\binom{n-2}{k-1}x^{k}y^{n}. $$ Now just read off the coefficient of $x^k y^n$.

$\endgroup$

Your Answer

Peter is a new contributor. Be nice, and check out our Code of Conduct.

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.