Why is the below statement true?
$$\sum_{j=0}^{n}\left(-\sum_{t=0}^{k}{{k+1}\choose {t}}j^t(-1)^{k+1-t}\right) = -\sum_{t=0}^{k}{{k+1}\choose {t}}(-1)^{k+1-t}\left(\sum_{j=0}^{n}j^t\right)$$
More generally, under what conditions are we allowed to bring the outer summation inside, and if possible maybe a simple example to provide an intuitive understanding of why it works under those conditions (if any).
I know that when a term in the inner summation doesn't depend on the index of the inner summation, we can bring since it is like a constant, but this is not the case since $j^t$ depends on both $t$ and $j$. The only other questions I have found related to this topic were regarding infinite sums, so help would be appreciated. Thanks!
Best Answer
Let's simplify your question first. What you have is:
$$\sum_{j=0}^n \left(-\sum_{t=0}^k f(k,t) g(j,t)\right)$$ for some function $f$ (in your particular case: $f(k,t) = {k+1\choose t}(-1)^{k+1-t}$ and $g$ (in your case, $g(j, t) = j^t$.
Let's forget what $g$ and $g$ are for the moment because it's not relevant.
The sum $$S=\sum_{j=0}^n \left(-\sum_{t=0}^k f(k,t) g(j,t)\right)$$ can be first rewritten as
$$S=-\sum_{j=0}^n \left(\sum_{t=0}^k f(k,t) g(j,t)\right)$$
Now, let's reverse the order of summing. In the original case, you sum something from $j=0$ to $j=n$, and for every $j$, you sum the inner sum from $t=0$ to $t=k$, which means you cover the whole square $\{(j,t)\in\mathbb Z^2| 0\leq j\leq n\land 0\leq t\leq k\}$.
You can cover the same square by summing first over $t$ and then over $j$, so you get
$$S=-\sum_{t=0}^k \left(\sum_{j=0}^n f(k,t) g(j,t)\right)$$
Now, for every value of $t$, you can see that
$$\sum_{j=0}^n f(k, t)g(j,t) = f(k,t)\sum_{j=0}^n g(j,t)$$
because you are just factoring out the common factor $f(k,t)$. It becomes ogvious if you write it as
$$\sum_{j=0}^n f(k, t)g(j,t) = f(k,t) g(0,t) + f(k,t)g(1,t) + \dots + f(k,t)g(n,t) = f(k,t) (g(0,t) + g(1,t) + \dots + g(n,t)) = f(k,t)\sum_{j=0}^n g(j,t)$$
So now you get
$$S=-\sum_{t=0}^k \left(f(k,t)\sum_{j=0}^n g(j,t)\right)$$
which is what you wanted to have in the first place.