How to prove that the number of diagonals of a $M \times N$ matrix is $M+N-1$? Given a matrix $M \times N$, how to prove that the number of diagonals that can be drawn, like in the figure below, is equal to $M + N - 1$?



My idea would be to prove it with induction and consider the 3 possible cases: $M=N$, $M&gt;N$ and $M&lt;N$. But I don't know how to do it.
This is a counting problem.

Start at the first row and count diagonals passing through elements on the first row. You get $N$ of those.

Now go down through the last column and you get $M$ of those.

There is one which is counted twice, so the total is $M+N-1$
Each entry of the matrix is given by the row number $i$ and the column number $j$, and we say that $(i,j)$ is the index of this entry.  Notice that the $k$-th diagonal is defined by $(i,j)$-entries with $i+j=k+1$.  Since $i\in\{1,2,\ldots,M\}$ and $j\in\{1,2,\ldots,N\}$, we see that
$$k=i+j-1\in\{1,2,\ldots,M+N-1\}\,.$$

Each $k\in\{1,2,\ldots,M+N-1\}$ corresponds to a nonempty diagonal line.  For $k=1,2,\ldots,M$, the $k$-th diagonal contains the entry indexed by $(k-1,1)$.  For $k=M+1,M+2,\ldots,M+N-1$, the $k$-th diagonal contains the entry indexed by $(M,k+1-M)$.