0
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ It is a strange detour to find a recurrence relation for this. Plainly there are $(n+1)^2=n^2+2n+1$ elements in the matrix, of which $n+1$ are on the diagonal. Those remaining, $n^2+n=n(n+1)$ in all, are the off-diagonal elements. $\endgroup$
    – hmakholm left over Monica
    Dec 5, 2015 at 21:54
  • $\begingroup$ I see what you mean, unfortunately this is on my final review and i just don't really see how to proceed but i want to know how to solve it in case something similar pops us. $\endgroup$
    – Pablo Sanchez
    Dec 5, 2015 at 22:09
  • $\begingroup$ Well, recurrences of the form $a_{n+1}=a_n+f(n)$ are extremely common -- in fact so common that there's a special notation for them: $$ a_{n+1} = \sum_{k=0}^n f(n) $$ and you may be better acquainted with techniques for solving them in that notation ... $\endgroup$
    – hmakholm left over Monica
    Dec 5, 2015 at 23:05
  • $\begingroup$ I'm sorry I don't know the technique you're referring to, could you elaborate please? $\endgroup$
    – Pablo Sanchez
    Dec 5, 2015 at 23:26

1 Answer 1

Reset to default
0
$\begingroup$

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}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .