Verifying that a computed density is a probability density Question:
Let $n\in\Bbb N$. I want to show (or disprove) that for fixed $i\in \{1, \ldots ,n-1\}$ and $N\in\Bbb N$ we have
$$\sum_{m=i}^{n-1} \binom{m-1}{i-1} \sum_{k=i}^{m} (-1)^{i+k} \lambda_{k}^N \binom{m-i}{k-i} = \sum_{k=i}^{n-1} (-1)^{i+k}\lambda_k^N \binom{k-1}{i-1}\binom{n-1}{k}, $$
where $\lambda_\ell^N = \left(\frac{n-\ell}n \right)^N$ for $k\in\{1,\ldots , n-1\}$ and $\lambda_n^N = 1$.
Background:
The quantity above is supposed to be the sum over the probabilities of being in state $m \in \{i, \ldots , n -1\}$ started from $i$ after $N$ steps for the simple Markov chain on the state space $\{1, \ldots ,n\}$ with the transition matrix
$$p(i,m) = \begin{cases} \frac{n-i}n &: m=i \neq n ,\\ \frac i n&:m=i+1,\\ 1 &: m=i=n,\\ 0&: \text{else}\end{cases}$$
I calculated the probability of the $N$th step by computing the Jordan decomposition matrices. More precisely, a Jordan decomposition is then $D^N = \text{diag}( \left( \frac{n-1}n\right)^N , \ldots , \left( \frac{1}n\right)^N , 1)$ and $V = (v_{i,k})_{i,k}$ with $v_{i,k} = (-1)^{i-1} \binom{k-1}{i-1} 1_{i\leq k < n} +1_{k=n}$ as eigenvector matrix and $V^{-1} = \tilde V$ with $\tilde v_{i,k} = v_{i,k}1_{k<n} + (-1)^k \binom{n-1}{k} 1_{k=n}$.
To check this result I wanted to verify that the probabilities add up to $1$, but could not get it done yet. Here the left-hand side of the equation is $p^N (i, \{i, \ldots ,
 n-1\})$ and the right-hand side is $1-p^N (i,n)$.
 A: Let $(a_{k})_{k\in\Bbb N}$ be arbitrary numbers. We make the following claim: For $n\in\Bbb N$ holds for all $i\in\{1,\ldots , n\}$
$$\sum_{k=i}^n (-1)^{i+k} a_k \binom{k-1}{i-1} \binom{n}{k} = \sum_{m=i}^n \binom{m-1}{i-1} \sum_{k=i}^m (-1)^{i+k} a_k \binom{m-i}{k-i}$$
For the proof assume this holds for $n-1$. Then for $i\leq n-1$ holds
$$\sum_{k=i}^n (-1)^{i+k} a_k \binom{k-1}{i-1} \binom{n}{k} = \sum_{k=i}^{n-1} (-1)^{i+k} a_k \binom{k-1}{i-1} \binom{n}{k} + (-1)^{i+n} a_n \binom{n-1}{i-1}\\
= \sum_{k=i}^{n-1} (-1)^{i+k} a_k \binom{k-1}{i-1} \binom{n-1}{k} + \sum_{k=i}^{n-1} (-1)^{i+k} a_k \binom{k-1}{i-1} \binom{n-1}{k-1} + (-1)^{i+n} a_n \binom{n-1}{i-1}\\
=\sum_{m=i}^{n-1} \binom{m-1}{i-1} \sum_{k=i}^m (-1)^{i+k} a_k \binom{m-i}{k-i}+\sum_{k=i}^{n} (-1)^{i+k} a_k \binom{k-1}{i-1} \binom{n-1}{k-1}\\
=\sum_{m=i}^{n-1} \binom{m-1}{i-1} \sum_{k=i}^m (-1)^{i+k} a_k \binom{m-i}{k-i}+ \binom{n-1}{i-1}\sum_{k=i}^{n} (-1)^{i+k} a_k  \binom{n-i}{k-i}\\
=\sum_{m=i}^{n} \binom{m-1}{i-1} \sum_{k=i}^m (-1)^{i+k} a_k \binom{m-i}{k-i}
$$
Since for $n=1$ or $i=n$ the statement is clear the claim follows by induction.
From the claim the desired follows for $n$ by choosing $a_k = \lambda_k^N$. (I went the way with abitrary $a_k$ because the $\lambda_k^N$ depend on $n$.)
