Working out recursive functions

Question

I know that a function is defined recursively when it calls itself to progressively converge on a solution based on an initial condition. For example if we consider the function defined by $$Sq(1) = 1$$ $$Sq(n) = Sq(n-1) + 2*n - 1 \quad \text{ for } n > 1$$

The part I am struggling with is working out what $Sq(2)$ and $Sq(3)$ would be (and so on)?

Answer 1

To find out what $Sq(3)$ is, we need to first find out what $Sq(2)$ is, and to find out what $Sq(2)$ is, we first need to find out what $Sq(1)$ is. This is the nature of the recursive definition. Luckily, we already know what $Sq(1)$ is. So

$$Sq(3) = Sq(2) + 2*3 - 1$$ $$Sq(2) = Sq(1) + 2*2 - 1$$ and $$Sq(1) = 1.$$

Now we plug this value back into $Sq(2)$ and find

$$Sq(2) = 1 + 4 - 1 = 4$$ $$Sq(3) = 4 + 6 - 1 = 9.$$

Answer 2

Firstly, I'm denoting sq$(n)$ by $f(n)$. The given recurrence is,

$$f(n)-f(n-1)=2n-1~\forall~n\gt 1~\land~f(1)=1$$

Now, note that the difference between $f(n)$ and $f(n-1)$ is a function in $n$ which is $2n-1$. So, we can make a closed form by "piling up the differences" as,

$$f(n)=c_1+\sum_{i=1}^n (2n-1)~,~\textrm{where }c_1\textrm{ is some constant.}$$

The sum is easy to evaluate and you'll get,

$$f(n)=c_1+n(n+1)-n=c_1+n^2$$

Use the initial value given, $f(1)=1$ to conclude that $c_1=0$. Hence,

$$f(n)=n^2$$

Answer 3

Note that

$$sq(n)=n^2$$

satisfies the conditions, since

$$n^2=(n-1)^2+2n-1$$

and

$$1^2=1$$

To prove that this is the only possible solution, we can use induction. Assume $sq(n-1)=(n-1)^2$. Then we get:

$$sq(n)=(n-1)^2+2n-1=n^2$$