Reindexing double sum where lower limit of inner sum is dependent on lower limit of outer sum I am new to the math world and I am currently struggling with seeing how the reindexing for the following identity works:
$$
\sum_{k=0}^{n}{\sum_{i=k}^{n}{\binom{n}{i}\binom{i}{k}}} = \sum_{i=0}^{n}{\sum_{k=0}^{i}{\binom{n}{i}\binom{i}{k}}}
$$
I see how one of the last steps, changing the order of the sums with
$$
\sum_{k=0}^{i}{\sum_{i=0}^{n}{\binom{n}{i}\binom{i}{k}}} = \sum_{i=0}^{n}{\sum_{k=0}^{i}{\binom{n}{i}\binom{i}{k}}}
$$
works but I am not able to even get to this point. Could somebody please point me into the right direction or even be so kind to explain it to me?
Thanks a lot in advance
 A: The only way that I know of to verify that the LHS double summation equals the RHS double summation is to simply (informally) write out the terms, and manually inspect them.
Typically, in a situation like this, if the equality holds, one of the double summations will represent partitioning the terms row by row, while the other double summation will represent partitioning the terms column by column.  That is the case here.  See the array below.
\begin{array}{ r  r  r  r  r  r  r}
\binom{n}{0}\binom{0}{0} & \binom{n}{1}\binom{1}{0} 
& \binom{n}{2}\binom{2}{0} & \cdots & \cdots & \binom{n}{n-1}\binom{n-1}{0} & \binom{n}{n}\binom{n}{0}\\
& 
\binom{n}{1}\binom{1}{1} 
& \binom{n}{2}\binom{2}{1} & \cdots & \cdots & \binom{n}{n-1}\binom{n-1}{1} & \binom{n}{n}\binom{n}{1}\\
& & 
\binom{n}{2}\binom{2}{2} & \cdots & \cdots & \binom{n}{n-1}\binom{n-1}{2} & \binom{n}{n}\binom{n}{2}\\
& & & \cdots & \cdots & \cdots & \cdots \\
& & & & \cdots & \cdots & \cdots \\
& & & & & 
\binom{n}{n-1}\binom{n-1}{n-1} & \binom{n}{n}\binom{n}{n-1}\\
& & & & & &
\binom{n}{n}\binom{n}{n}\\
\end{array}
In the original posting, the LHS double summation is represented by partitioning the terms row by row, while the RHS double summation is represented by partitioning the terms column by column.  Personally, this is the only way that I know of to verify that the LHS equals the RHS.
That is, you actually have to (somehow) visualize the effects of the LHS double summation, visualize the effects of the RHS double summation, and then (somehow) compare the two visualizations.  If you can do this mentally, okay.  Otherwise, write it out, as I did.
A: You do the inner sum first, then the outer sum second.
Let $\ A=\{0,\ldots, n\},\ $ let $\ S\ $ be a set, and define more generally a function $\ f: A \times A \to S.$
Then,
\begin{align}
\\
\sum_{k=0}^{n}\left({\sum_{i=k}^{n}}\ f(i,k)\right)\\
\\
= \sum_{k=0}^{n} f(k,k) + f(k+1, k) + \ldots + f(n, k)\ \\
\\
= (f(0,0) + f(1,0) + \ldots + f(n,0))\ +\ (f(1,1) + f(2,1) + \ldots + f(n,1))\ +\ \ldots\ +\ (f(n-1, n-1) + f(n, n-1) )\ +\ (f(n,n)) \\
\\
\overset{(*)}{=} (f(0,0))\ +\ (f(1,0) + f(1,1))\ +\ \ldots\ +\ (f(n-1,0) + f(n-1, 1) + \ldots + f(n-1, n-1))\ +\ (f(n,0) + f(n, 1) + \ldots + f(n, n-1), + f(n,n))\\
\\
= \sum_{i=0}^{n} f(i,0) + f(i,1) + \ldots + f(i, i-1) + f(i,i) \\
\\
= \sum_{i=0}^{n}\left(\sum_{k=0}^{i}\ f(i,k)\right).\\
\\
\end{align}
At $\ (*),\ $ we simply rearranged the terms.
A: There is another common notation for double sums which can be conveniently used to see equality of left-hand and right-hand double sum.

We have
\begin{align*}
\sum_{k=0}^{n}{\sum_{i=k}^{n}{\binom{n}{i}\binom{i}{k}}}
=\sum_{\color{blue}{0\leq k\leq i\leq n}}\binom{n}{i}\binom{i}{k}
= \sum_{i=0}^{n}{\sum_{k=0}^{i}{\binom{n}{i}\binom{i}{k}}}
\end{align*}
Looking at the blue marked index region might help to see that LHS and RHS are the same.

Hint: The scope of the index variable $i$ in
\begin{align*}
\sum_{i=0}^{n}\sum_{k=0}^{i}\color{blue}{\binom{n}{i}\binom{i}{k}}
\end{align*}
is the blue marked part right to the summation symbol. It is not admissible to simply change the order of summation symbols (without adaptation) as in
\begin{align*}
\sum_{k=0}^{i}\sum_{i=0}^{n}\color{blue}{\binom{n}{i}\binom{i}{k}}
\end{align*}
Here the upper limit $i$ in the outer sum is not within the scope of the index variable $i$ of the inner sum. It so becomes a free variable independent of the index $i$ of the inner sum.
