In studying for an exam, I had difficulty with these two questions:
Give a recursive form (including bases) for the following functions.
$$f(n) = 5 + (-1)^n$$
$$f(n) = n(n+3)$$
In studying for an exam, I had difficulty with these two questions:
Give a recursive form (including bases) for the following functions.
$$f(n) = 5 + (-1)^n$$
$$f(n) = n(n+3)$$
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)\:$.
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$).
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
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 $