"chess" problem Suppose that we have a cheespiece that can move either to the left or upwards. How many possibilities are there on a $n^2$ board to come from the bottom right square to the upper left square of the board.
I tried to show that this in fact is $2^{2n-1}$ but I don't get the induction right.
 A: Consider the fact that no matter which path the piece takes, it must go left $n$ times and up $n$ times. Thus the number of all possible paths is all the possible permutations of the multiset $\{n \cdot \operatorname{up},n \cdot \operatorname{left}\}$ which has a closed form formula.
A: Added:  This assumed that the piece could start on any square on the right and end on any square on the left, including moving up as many spaces along the left edge as desired.  It appears this is not what was wanted.
If the piece starts in the top row, there is only $1$ way to get there-always go left.  If it starts one row below the top, it can go up in any column, or not at all, for a total of $n+1$ paths.  If it starts two rows below the top, you can choose any two rows to go up in with replacement, $\frac 12 n(n+1)$, go up only once, $n+1$, or not at all, $1$, for a total of $1+n+{n+1 \choose 2}$.  For row $i$, we have $\sum_{j=1}^i{n+j-1\choose j-1}$, so summing over all rows we have $$\sum_{i=1}^n \sum_{j=1}^i{n+j-1\choose j-1}=\sum_{i=1}^n \frac i{n+1}{n+i \choose i}=\frac n{n+2} {2n+1 \choose n+1}=\frac n{2(n+1)^2}\frac {(2n+2)!}{(n+1)!^2}$$
with the sum evaluations done by Alpha 1 and Alpha 2
