# How do I do Recursion?

I need help studying for an exam.

Give a recursive form (including bases) for the following functions:

$f(n) = 5 + (-1)^n$

$f(n) = n(n+3)$

Lastly,

$S(0) = 3$

$S(1) = 10$

Derive the closed form for this recursion and prove it true by induction.

-
What have you tried so far? And what is the $S$? Is $S$ specified only at $2$ values? –  user17762 Nov 23 '10 at 2:41
Your information on $S(\cdot)$ is sparse... for the two $f$'s, make a table and note the pattern and the difference between successive members of the sequence... –  Ｊ. Ｍ. Nov 23 '10 at 2:41
Recursion (n) - See: Recursion –  crasic Nov 23 '10 at 2:58
How about (for the second $f$):$$f(n)=\cases{0&\text{for }n=0\\0f(n-1)+n(n+3)&\text{for }n>0}$$Recursive? Check. Includes base case? Check. Equal to the given function? Check. –  Henning Makholm Oct 11 '11 at 15:48

Recursion refers to a method where you figure out the "next" value in terms of previous values. For example, to solve the Towers of Hanoi puzzle, you can explain the solution recursively: to move $n$ disks, first move the top $n-1$ disks to the auxiliary rod, then move the bottom disk to the target rod, then move the other $n-1$ disks to the target rod. The "move the top $n-1$ disks" parts of the instruction are recursive, because you need to know how to solve the $n-1$ case. And you solve that case by solving the $n-2$ case. And you solve that case by solving the $n-3$ case. And you ... etc. Eventually you need to touch bottom, which you do at the $n=1$ case, the base.

So, let's think about $f(n)=5+(-1)^n$. Can you express $f(n+1)$ in terms of $f(n)$? If so, then this expression plus the value of $f(0)$ will give you the recursive forms.

To guide you, let me do a different example. Consider $f(n) = 2^{n}-1$. How do we express it recursively? First, I try to see if I can express $f(n+1)$ in terms of $f(n)$: $$f(n+1) = 2^{n+1}-1 = 2(2^n) - 1 = 2\Bigl((2^n - 1)+1\Bigr) -1 = 2(f(n)+1)-1 = 2f(n)+1.$$ (Why did I do that? Because I need to "find" the expression $2^n-1$ somehow in the expression $2^{n+1}-1$, so that I can replace it with $f(n)$).

This, together with the fact that $f(0)=2^0-1 = 0$ gives me the recursive form: \begin{align*} f(0) &= 0;\\ f(n+1) &= 2f(n) + 1. \end{align*} Try something similar with your two $f(n)$s.

As for your "lastly", I have no idea what you have. Giving just the first two values does not tell you what a "closed form" for $S$ will be (here, "closed form" is the opposite process: if you know the recursive formula, you want to find a formula of the form $S(n) =$blah, where blah depends only on $n$ and not on previous values of $S$).

-

HINT $\rm\ \ (-1)^{n+1}/(-1)^n = -1,\$ so substituting $\rm\ (-1)^n\ =\ f(n)-5\ \Rightarrow\ \ldots$

For the second, note that $\rm\ f(n+1) - f(n)\$ reduces the degree of polynomial $\rm\ f(n)\:$.

-

Finding a recurrence for the first equation should be obvious (just look at the first few values).

For the second function $f(n) = n(n+3)$, here's an approach that seems natural to me.

You want to express $f(n)$ in terms of $f(n-1)$, $f(n-2)$, etc. So start with $f(n)=a f(n-1) + b f(n-2)$ and equate coefficients. That is, we have $n^2+3n=a(n^2+n-2)+b(n^2-n-2)$ so

• $a+b=1$,
• $a-b=3$,
• $-2a-2b=0$.

We observe that this system of linear equations has no solutions (the first and third equations are inconsistent). So, we now consider a deeper recurrence: Let $f(n)=a f(n-1) + b f(n-2) + c f(n-3)$, now solve the resultant system of linear equations.

[Note: in both cases, remember to describe sufficiently many initial values.]

-

I'd look at it this way:
$f(n) -f(n-1) = (n^2 + 3n) - (n^2+n-2) = +2n + 2$
$f(n-1)-f(n-2) = (n^2 + n-2) - (n^2-n-2)= +2n$

So by the first differences the square terms vanish and by the second order differences also the linear terms vanish, so only a constant term remains if second order difference is used, so we can leave this as

$(f(n)-f(n-1)) - (f(n-1)-f(n-2)) = 1*f(n) - 2*f(n-1) + 1*f(n-2) = 2$

and finally get by this

$f(n) = 2*f(n-1)-f(n-2) + 2$

-