Show that n(n+1)/2 multiplications are required

Question

$a_{11}x_1$+$a_{12}x_2$+$a_{13}x_3$+ ...+ $a_{1,n-1}x_{n-1}$+$a_{1n}x_n$ =$b_1$

$a_{22}x_2$+$a_{23}x_3$+ ...+ $a_{2,n-1}x_{n-1}$+$a_{2n}x_n$ =$b_2$

$a_{33}x_3$+ ...+ $a_{3,n-1}x_{n-1}$+$a_{3n}x_n$ =$b_3$

...

$a_{n-1,n-1}x_{n-1}$+$a_{n-1,n}x_n$ =$b_{n-1}$

$a_{n,n}x_n$ =$b_{n}$

Show that n(n+1)/2 multiplications are required to solve for $x_n$, $x_{n-1}$,...$x_2$,$x_1$

I have no idea where to start the prove..

Answer 1

For $k\in [1,n]\cap\mathbb{N}$, we have $$ x_{k,k} = \frac{1}{a_{k,k}}\Bigl(b_k - \sum_{i=k+1}^n a_{k,i}x_{i}\Bigr) $$ This formula show that $1 + n - k$ multiplications are required to compute $x_{k,k}$. So to solve the system of equations, $$ \sum_{k=1}^n (1 + n - k) = n(n+1)/2 $$ multiplications are required.

Answer 2

for $n=2$ we have two equations

$a_{11}x_1+a_{12}x_2=b_1$

$a_{22}x_2=b_2$

so to solve we need to find out value of $x_2$ by one multiplication and to get $x_1$ from 1st equation we need to multiply by ${a_{11}}^{-1}$ so 2 multiplication hence total $3$.

similarly if we have $n$ equation we start from last equation and now we have to do $1+2+3+...+n=\frac{n(n+1)}{2}$ multiplication