1

Suppose we have to square upper triangular matrices that we want to multiply using the following code:

enter image description here

The question is to find the total number of multiplications. I noticed that every time the number of multiplications get decreased by 1 in each run. So the total number of multiplication is as follows:

$$[1+2+\cdots+n] + [1+2+\cdots+(n-1)] + \cdots + [1]$$

Question: In a solution, they say the total number of multiplications is $n(n + l)(n + 2)/6$, can you please explain how they got this number?

Avv
  • 1,159

1 Answers1

1

You should know that $[1+2 + \dots + n] = \frac{n(n+1)}2.$ To prove that $\sum_{k=1}^n \frac{k(k+1)}2 = \frac{n(n+1)(n+2)}6$ you need to know how to sum the squares of the first $n$ natural numbers.

Igor Rivin
  • 25,994
  • 1
  • 19
  • 40
  • Thank you professor. Can you please add more steps to show how $[1+2+\cdots+n] + [1+2+\cdots+(n-1)] + \cdots + [1] = \sum_{k=1}^n \frac{k(k+1)}2$ – Avv Mar 13 '21 at 15:07