Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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... –  J. M. Nov 23 '10 at 2:41
3  
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
add comment

4 Answers

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$).

share|improve this answer
add comment

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)\:$.

share|improve this answer
add comment

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.]

share|improve this answer
add comment

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 $

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.