1

On an exam of mine, I was asked to find a recurrence relation for the function $f(n) = 5n^2 +3$, where $n \in \mathbb{Z}^+$. I needed to provide a base case and the actual relation itself. I know the base case is for $n = 1$, were $f(1) = 8$, but I have no idea how to derive the relation from here.

The professor's answer key is as follows, but I don't understand where the intuition/motivation comes from for this solution:

$f(1) = 8, f(n) = 5n^2 + 3 = 5(n - 1)^2 + 3 + 5(2n - 1) = f(n - 1) + 10n - 5$

Where do I start? The above steps seem, at least to me, to be arbitrarily and magically plucked from nowhere...

Aleksandr Hovhannisyan
  • 2,983
  • 4
  • 34
  • 59

3 Answers3

2

You are trying to write a recurrence of the form $f(n)=f(n-1)+\text{ something.}$ You can just substitute in to find out what the something has to be. You are given that $f(n)=5n^2+3$, so $f(n-1)=5(n-1)^2+3.$ Then $f(n)-f(n-1)=5n^2+3-5(n-1)^2+3=10n-5$ and you have your something.

Ross Millikan
  • 374,822
1

Another way to work it out is by simple algebraic elimination. Consider two consecutive terms:

$$ \begin{align} f(n) &= 5n^2+3 \\ f(n-1) &= 5(n-1)^2+3 = 5n^2-10n+8 \end{align} $$

Now consider $k = n^2$ as an independent variable:

$$ \begin{align} f(n) &= 5k+3 \\ f(n-1) &= 5k-10n+8 \end{align} $$

Eliminate $k$ between the two equations, and you get the posted recurrence:

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

You can take this one step farther. Write two consecutive terms of the latter recurrence:

$$ \begin{align} f(n) &= f(n - 1) + 10n - 5 \\ f(n-1) &= f(n - 2) + 10(n-1) - 5 = f(n-2) +10 n -15 \end{align} $$

Now eliminate $n$ between these two equations, and you get a standard linear recurrence for $f(n)\,$:

$$ f(n)-f(n-1)=f(n-1)-f(n-2)+ 10 \;\;\iff\;\; f(n)=2 f(n-1)-f(n-2)+10 $$

dxiv
  • 76,497
  • 1
    I think the second order standard recurrence is to be preferred over the professor's answer which is of a "mixed" type, including $n$ both implicitly and explicitly. "Mixed" types require you to separately keep track of $n$ and $f(n)$ when generating the sequence. I also suspect that they are not unique. – WW1 Jul 09 '17 at 19:45
0

The motivation behind rewriting $f(n)$ this way, is to acquire an equation of the form $$f(n)=g(f(n-1)),$$ i.e. we have to rewrite $f(n)$, so that we get some function of $f(n-1)$.
Here, this function is $$g(x)=x+10n-5.$$

Now you can directly deduct the recurrence relation, by plugging $g$ into $x_{n+1}=g(x_n)$.
Here, we get the result $$x_1=8,~~x_{n+1}=x_n+10n-5$$

Eldioo
  • 338
  • 3
  • 8