I would love to learn techniques for solving the following, but I can't seem to identify this type of sequence: let $N > 0$ and let $k$ be an arbitrary positive integer between $0$ and $N-1$ (inclusive) and consider the sequence:
$$\lambda_k = \frac1{N-k} - \sum_{j=0}^{k-1}\binom{k}{k-j} \lambda_j\;.$$
$\lambda_0 \equiv 1/N$. This generates sequences like:
$$\frac1N,\frac1{N-1}-\frac1N = \frac1{N(N-1)},\frac1{N-2} - 2\left(\frac1{N-1} - \frac1N\right) - \frac1N =\frac2{N(N-1)(N-2)},\dots$$
it seems that $\lambda_k$ is always equal to an integer divided by $N(N-1)(N-2)\dots(N-k)$ (believe me, I understand how dangerous the word seems can be). In fact, I wrote a small recursive C program to test the sums (for small $C,k$ otherwise it takes forever) and it also seems that $\lambda_{N-1} = 1/N$, but I can't see how to prove that in general.
Any replies pointing me to references about these types of sequences (if they exist) would be appreciated.
It turns out that
$$\lambda_k=\frac{k!}{N^\underline{k+1}}\;,$$
where $x^{\underline k}=x(x-1)\dots(x-k+1)$ is the falling factorial. This can be proved by induction on $k$. Assuming that it’s true below $k$, we have
$$\begin{align*} \lambda_k&=\frac1{N-k}-\sum_{j=0}^{k-1}\binom{k}{k-j}\frac{j!}{N^{\underline{j+1}}}\\\\ &=\frac1{N-k}-\sum_{j=0}^{k-1}\frac{k!}{(k-j)!N^{\underline{j+1}}}\\\\ &=\frac1{N-k}-\sum_{j=0}^{k-1}\frac{k^{\underline j}}{N^{\underline{j+1}}}\\\\ &=\frac{N^{\underline k}}{N^{\underline{k+1}}}-\sum_{j=1}^k\frac{k^{\underline{j-1}}}{N^{\underline j}}\\\\ &=\frac{N^{\underline k}}{N^{\underline{k+1}}}-\sum_{j=1}^k\frac{k^{\underline{j-1}}(N-j)^{\underline{k+1-j}}}{N^{\underline{k+1}}}\\\\ &=\frac1{N^{\underline{k+1}}}\left(N^{\underline k}-\sum_{j=1}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}\right)\;, \end{align*}$$
so we want to show that
$$N^{\underline k}-\sum_{j=1}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}=k!\;.$$
Now
$$\begin{align*} N^{\underline k}-\sum_{j=1}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}&=N^{\underline k}-(N-1)^{\underline k}-\sum_{j=2}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}\\\\ &=\Big(N-(N-k)\Big)(N-1)^{\underline{k-1}}-\sum_{j=2}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}\\\\ &=k(N-1)^{\underline{k-1}}-\sum_{j=2}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}\\\\ &=k(N-1)^{\underline{k-1}}-k(N-2)^{\underline{k-1}}-\sum_{j=3}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}\\\\ &=k\Big((N-1)-(N-k)\Big)(N-2)^{\underline{k-2}}-\sum_{j=3}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}\\\\ &=k^{\underline 2}(N-2)^{\underline{k-2}}-\sum_{j=3}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}\\\\ &\;\vdots\\\\ &=k^{\underline\ell}(N-\ell)^{\underline{k-\ell}}-\sum_{j=\ell+1}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}\\\\ &\;\vdots\\\\ &=k^{\underline{k-1}}(N-k+1)-k^{\underline{k-1}}(N-k)\\\\ &=k^{\underline{k-1}}\\\\ &=k!\;. \end{align*}$$
Added: I had some time and recast this computation as a proper proof by induction.
Claim: For $\ell=0,\dots,k-1$,
$$N^{\underline k}-\sum_{j=1}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}=k^{\underline\ell}(N-\ell)^{\underline{k-\ell}}-\sum_{j=\ell+1}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}\;.\tag{1}$$
Proof. For $\ell=0$ there is nothing to prove: the righthand side of $(1)$ is the lefthand side. Now assume that $(1)$ holds for some $\ell<k-1$. For typographical convenience let $$S(\ell)=\sum_{j=\ell+1}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}\;.$$
Then
$$\begin{align*} N^{\underline k}-\sum_{j=1}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}&=k^{\underline\ell}(N-\ell)^{\underline{k-\ell}}-S(\ell)\\\\ &=k^{\underline\ell}(N-\ell)^{\underline{k-\ell}}-k^{\underline\ell}\big(N-(\ell+1)\big)^{k-\ell}-S(\ell+1)\\\\ &=k^{\underline\ell}\Big((N-\ell)-(N-k)\Big)\big(N-(\ell+1)\big)^{\underline{k-(\ell+1)}}-S(\ell+1)\\\\ &=k^{\underline\ell}(k-\ell)\big(N-(\ell+1)\big)^{\underline{k-(\ell+1)}}-S(\ell+1)\\\\ &=k^{\underline{\ell+1}}\big(N-(\ell+1)\big)^{\underline{k-(\ell+1)}}-S(\ell+1)\;, \end{align*}$$
and the induction goes through. $\dashv$
In particular, taking $\ell=k-1$, we have
$$\begin{align*} N^{\underline k}-\sum_{j=1}^kk^{\underline{j-1}}(N-j)^{\underline{k+1-j}}&=k^{\underline{k-1}}(N-k+1)-k^{\underline{k-1}}(N-k)\\ &=k^{\underline{k-1}}\\ &=k!\;. \end{align*}$$