How to prove that the number of diagonals of a $M \times N$ matrix is $M+N-1$?

Question

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>N$ and $M<N$. But I don't know how to do it.

Answer 1

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$

Answer 2

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)$.