Find a recurrence relation that counts the number of off-diagonal elements of an $n+1 × n+1$ matrix. Solve this recurrence relation for an expression of the number of off diagonal entries as a function of $n$.
-For the first part of the question I got $M(n+1) = M(n) + 2n$.
-I am unsure how to solve this as a function of $n$, first off I am unsure if what I came up with is correct for first part and if so how to proceed with this. I am familiar with the auxiliary equation method but i am unsure how to approach this with a non-homogeneous piece $(2n)$. Any help is appreciated.
Your recursion is indeed correct.
To get a closed-form answer, write the recursion for different values of $n$ and sum them up, as follows: \begin{align} M(n+1) &= M(n) + 2n \\ M(n) &= M(n-1) + 2(n-1) \\ M(n-1) &= M(n-2) + 2(n-2) \\ \dots & \\ M(3) &= M(2) + 2(2) \\ M(2) &= M(1) + 2(1) \\ M(1) &= 0 \end{align}
After summing these up you get: \begin{align} & M(n+1) = 2\sum_{i=1}^n i = n(n+1) \\ \Rightarrow &M(n) = n(n-1) \end{align}