0

So I have the below recurrence relation.

the difference of the delta values is 4x

If you write out some terms you get the following

a(0) = 2

a(1) = 13

a(2) = 57

a(3) = 233

a(4) = 937

the delta values are as follows

a(0-1) = 11

a(1-2) = 44

a(2-3) = 176

a(3-4) = 704

Simple algebra tells that you can find the next term by multiplying by 4 so the difference is 4x. Now my question is, how can I use this knowledge to find a closed form? The formula of a geometric sequence (a(n)=a(0)r^n) doesn't seem to work here and that's the most similar closed form formula I can think of.

Legion Daeth
  • 265
  • 3
  • 4
  • 15
  • 2
    Since you give no context as to what you know or can use about linear recurrences, the following might as well qualify as a hint: $$a_n+\frac{5}{3} = 4\left(a_{n-1} + \frac{5}{3}\right)$$ – dxiv Mar 17 '17 at 06:51

1 Answers1

2

If $a_n = ua_{n-1}+v$, then it looks like $a_n$ is about $u$ times $a_{n-1}$, but not quite.

So, let's see if we can perturb $a_n$ to get something that does get multiplied by $u$ each time.

The simplest perturbation is by a constant. So, let $a_n = b_n+c$.

Then $a_n = ua_{n-1}+v$ becomes $b_n+c = u(b_{n-1}+c)+v =ub_{n-1}+uc+v $ or $b_n =ub_{n-1}+uc+v-c =ub_{n-1}+c(u-1)+v $.

Therefore, if we choose $c$ so that $c(u-1)+v=0$, or $c = \dfrac{v}{1-u}$, then $b_n = ub_{n-1}$, which is easy to solve.

The only case where we can not do this is $u=1$, but in this case the recurrence is $a_n = a_{n-1}+v$, where $a_n$ grows linearly rather than exponentially.

In all other cases, we get $b_n = u^nb_0$ or $a_n-c = u^n(a_0-c)$ or $a_n = u^n(a_0-c)+c = u^na_0-cu^n+c $.

marty cohen
  • 107,799