Write recurrence relation for above algorithm and solve it using Iteration Method.

Question

Consider the following recursive algorithm for computing the sum of the first $n$ squares: $\sum \limits _{i=1} ^n i^2 = 1^2 + 2^2 + \cdots + n^2$.

Algorithm:

SUM(n) if n = 1 return 1 else return SUM(n − 1) + n ∗ n

Write the recurrence relation for above algorithm and solve it using the iteration method.

Answer 1

HINT The result will look like a poylnomial of third degree:

$$ \sum_{i=0}^n i^2 = an^3+bn^2+cn+d $$ Calculate three more values by hand (you already have $n=1$) and find the coefficients...

Answer 2

The given pseudo code

SUM(n)
if n = 1 return 1
else return SUM(n − 1) + n ∗ n

directly translates into the mathematical function definition \begin{align} s(1) &= 1 \\ s(n) &= s(n-1) + n^2 \end{align}

which is a recurrence relation \begin{align} x_1 &= 1 \\ x_n &= x_{n-1} + n^2 \end{align}

The method of iteration seems to be looking at a couple of values and then deducing a closed form, which has to be proofed by some means like induction.

Inserting values for $n$ gives \begin{align} x_1 &= 1 \\ x_2 &= 1 + 2^2 \\ x_3 &= 1 + 2^2 + 3^2 \\ x_4 &= 1 + 2^2 + 3^2 + 4^2 \end{align} and leads to the assumption $$ x_n = \sum_{k=1}^n k^2 $$ as expected.