2.3

$f(n)=(((n^{2})(n+1)^{2})/8)+n(n+1)(2n+1)/12$

---

This problem does appear to break down into a series of nested summations:

$\displaystyle \sum _{i=1}^{n}{\text{ }}\displaystyle \sum _{j=1}^{i}{\text{ }}\displaystyle \sum _{k=j}^{i+j}{\text{ }}\displaystyle \sum _{l=1}^{j+i-k}1$

In the last summation, the formula is independent of the iterator, which translates into adding the value 1, $j+i-k$ times:

$\displaystyle \sum _{i=1}^{n}\displaystyle \sum _{j=1}^{i}\displaystyle \sum _{k=j}^{i+j}(j+i-k)$

Now the third summation goes from $j$ to $i+j$ the formula on closer examination reveals that

$\displaystyle \sum _{k=j}^{i+j}(j+i-k)$ is $\displaystyle \sum _{k=1}^{i}(k)$ which is equal to $i*(i+1)/2$

Since $\displaystyle \sum _{k=start}^{end}(end-k)=\displaystyle \sum _{k=1}^{end-start}(k)$

So the summation boils down to

$\displaystyle \sum _{i=1}^{n}\displaystyle \sum _{j=1}^{i}(i*(i+1)/2)$

The formula in the second summation is independent of the iterator, which translates to adding $i*(i+1)/2$, $i$ times.

$\displaystyle \sum _{i=1}^{n}(i^{2}*(i+1)/2)$

which is

$\displaystyle \sum _{i=1}^{n}((i^{3}+i^{2})/2)$

${\frac {1}{2}}\left(\Sigma r^{3}+\Sigma r^{2}\right)={\frac {1}{2}}\left({\frac {n^{2}\left(n+1\right)^{2}}{4}}+{\frac {n\left(n+1\right)\left(2n+1\right)}{6}}\right)={\frac {n^{2}\left(n+1\right)^{2}}{8}}+{\frac {n\left(n+1\right)\left(2n+1\right)}{12}}$

Time Complexity = O$({n}^{4})$

---

Back to Chapter 2