# Thread: recurrence relations of given sequences

1. ## recurrence relations of given sequences

Hi there,

Can anybody give me a brief tutorial on how to find "recurrence relation" of any given sequence...

e.g. take the sequences:

$\displaystyle a) a_n = n + (-1)^{n}$
$\displaystyle b) a_n = n^{2} + n$

What are the recurrence relations of the above examples?

2. Originally Posted by robocop_911
Hi there,

Can anybody give me a brief tutorial on how to find "recurrence relation" of any given sequence...

e.g. take the sequences:

$\displaystyle a) a_n = n + (-1)^{n}$
$\displaystyle b) a_n = n^{2} + n$

What are the recurrence relations of the above examples?
For the first look at $\displaystyle a_{n-1},$

$\displaystyle a_{n-1}=(n-1)+(-1)^{n-1}=n-1+(-1)^{n-1}=a_n-(-1)^n+(-1)^{n-1}-1$$\displaystyle =a_n+2(-1)^{n-1}-1$

So:

$\displaystyle a_n=a_{n-1}-2(-1)^{n-1}+1=a_{n-1}+2(-1)^{n}+1$

Which is not entirly satisfactory as we still hane n appearing other than as a subscript on the right, I will look at it again when I get the chance.

RonL

3. Originally Posted by robocop_911
Hi there,

Can anybody give me a brief tutorial on how to find "recurrence relation" of any given sequence...

e.g. take the sequences:

$\displaystyle a) a_n = n + (-1)^{n}$
$\displaystyle b) a_n = n^{2} + n$

What are the recurrence relations of the above examples?
For the second as $\displaystyle a_n$ is a quadratic in $\displaystyle n$ if we are looking for a linear recurence we know that this must involve two earlier terms in the sequence, so put:

$\displaystyle b_n=Aa_{n-1}+Ba_{n-2}$

then:

$\displaystyle b_n=A[(n-1)^2+(n-1)]+B[(n-2)^2+(n-2)]$

... $\displaystyle = A[n^2-2n+1+n-1]+B[n^2-4n+4+n-2]$

... $\displaystyle =A[a_n-2n]+B[a_n-4n-2]=(A+B)a_n + n(-2A-4B) -2B$

Now let $\displaystyle A=2,\ B=-1$, this becomes:

$\displaystyle b_n=a_n+2,$

so:

$\displaystyle a_n=b_n-2=2a_{n-1}-a_{n-2}$

RonL

4. Hello, robocop_911!

$\displaystyle 1)\;\; a_n \:= \:n + (-1)^n$
Crank out the first few terms . . .

. . $\displaystyle \begin{array}{ccccccc}a_1 &=& 1 + (-1)^1 &=& 0 \\ & & & & \rangle & +3 \\ a_2 &=& 2 + (-1)^2 &=& 3 \\ & & & & \rangle & -1 \\ a_3 &=& 3 + (-1)^3 &=& 2 \\ & & & & \rangle & +3 \\ a_4 &=& 4 + (-1)^4 &=& 5 \\ & & & & \rangle & -1 \\ a_5 &=& 5 + (-1)^5 &=& 4 \\ & & & & \rangle & +3 \\ a_6 &=& 6 + (-1)^6 &=& 7 \end{array}$

We are alternately "adding 3 to" and "subtracting 1 from" the preceding term.

The recurrence is: . $\displaystyle a_n \;=\;a_{n-1} + 1 + 2(-1)^n$

$\displaystyle 2)\;\; a_n \:= \:n^2 + n$
We have:

. . $\displaystyle \begin{array}{ccccccccc} a_1 &=& 1^2+1 &=& 2 \\ & & & & \rangle & +4 &=& 2(2) \\ a_2 &=& 2^2+2 &=& 6 \\ & & & & \rangle & +6 &=& 2(3) \\ a_3 &=& 3^2 + 3 &=& 12 \\ & & & & \rangle & +8 &=& 2(4) \\ a_4 &=& 4^2 + 4 &=& 20 \\ & & & & \rangle & +10 &=& 2(5) \\ a_5 &=& 5^2 + 5 &=& 30\end{array}$

Each term is: the preceding term, plus twice $\displaystyle n.$

The recurrence is: . $\displaystyle a_n \;=\;a_{n-1} + 2n$

5. Originally Posted by CaptainBlack
Which is not entirly satisfactory as we still hane n appearing other than as a subscript on the right, I will look at it again when I get the chance.

RonL
OK here goes:

$\displaystyle a_{n-2}=(n-2)+(-1)^{n-2}=(n-2)+(-1)^n=a_n-2$

so:

$\displaystyle a_n=a_{n-2}+2$

and we need two terms for our initial conditions.

RonL

6. Originally Posted by Soroban
Hello, robocop_911!

Crank out the first few terms . . .

. . $\displaystyle \begin{array}{ccccccc}a_1 &=& 1 + (-1)^1 &=& 0 \\ & & & & \rangle & +3 \\ a_2 &=& 2 + (-1)^2 &=& 3 \\ & & & & \rangle & -1 \\ a_3 &=& 3 + (-1)^3 &=& 2 \\ & & & & \rangle & +3 \\ a_4 &=& 4 + (-1)^4 &=& 5 \\ & & & & \rangle & -1 \\ a_5 &=& 5 + (-1)^5 &=& 4 \\ & & & & \rangle & +3 \\ a_6 &=& 6 + (-1)^6 &=& 7 \end{array}$

We are alternately "adding 3 to" and "subtracting 1 from" the preceding term.

The recurrence is: . $\displaystyle a_n \;=\;a_{n-1} + 1 + 2(-1)^n$

We have:

. . $\displaystyle \begin{array}{ccccccccc} a_1 &=& 1^2+1 &=& 2 \\ & & & & \rangle & +4 &=& 2(2) \\ a_2 &=& 2^2+2 &=& 6 \\ & & & & \rangle & +6 &=& 2(3) \\ a_3 &=& 3^2 + 3 &=& 12 \\ & & & & \rangle & +8 &=& 2(4) \\ a_4 &=& 4^2 + 4 &=& 20 \\ & & & & \rangle & +10 &=& 2(5) \\ a_5 &=& 5^2 + 5 &=& 30\end{array}$

Each term is: the preceding term, plus twice $\displaystyle n.$

The recurrence is: . $\displaystyle a_n \;=\;a_{n-1} + 2n$

Can't we just do $\displaystyle a_n - a_{n-1} = n^2+n - [ (n-1)^2 + (n-1) ]$
i.e. subtract $\displaystyle a_n$ by $\displaystyle a_{n-1}$ we get the answer easily!
But subtracting doesn't seem to work for say...
a) $\displaystyle a_n = 5^n$
b) $\displaystyle a_n = n!$
c) $\displaystyle a_n = 3$

What to do then?

7. Originally Posted by robocop_911
i.e. subtract $\displaystyle a_n$ by $\displaystyle a_{n-1}$ we get the answer easily!
But subtracting doesn't seem to work for say...
a) $\displaystyle a_n = 5^n$
b) $\displaystyle a_n = n!$
c) $\displaystyle a_n = 3$

What to do then?
Its a little different, but the idea is the same... try multiplication!

a) $\displaystyle a_n = 5a_{n-1},\, a_1 = 5$
b) $\displaystyle a_n = na_{n-1}, \, a_1 = 1$
c) $\displaystyle a_n = a_{n-1}, \, a_1 = 3$

8. Originally Posted by robocop_911
Can't we just do $\displaystyle a_n - a_{n-1} = n^2+n - [ (n-1)^2 + (n-1) ]$
i.e. subtract $\displaystyle a_n$ by $\displaystyle a_{n-1}$ we get the answer easily!
But subtracting doesn't seem to work for say...
a) $\displaystyle a_n = 5^n$
b) $\displaystyle a_n = n!$
c) $\displaystyle a_n = 3$

What to do then?
Well, c) is easy since it's a constant.

a) you can do by division:
$\displaystyle \frac{a_{n}}{a_{n - 1}} = \frac{5^n}{5^{n- 1}} = 5$
so
$\displaystyle a_n = 5a_{n - 1}$

The only thing I can do for b) is by a similar division process but I get
$\displaystyle a_n = n \cdot a_{n - 1}$
which is still in terms of n. I doubt this one can be done in another way. (Unless you want to define the "inverse gamma function." Possible I suppose, but I've never seen it.)

-Dan