# 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:

$a) a_n = n + (-1)^{n}$
$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:

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

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

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

So:

$
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:

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

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

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

then:

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

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

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

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

$b_n=a_n+2,$

so:

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

RonL

4. Hello, robocop_911!

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

. . $\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: . $a_n \;=\;a_{n-1} + 1 + 2(-1)^n$

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

. . $\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 $n.$

The recurrence is: . $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:

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

so:

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

. . $\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: . $a_n \;=\;a_{n-1} + 1 + 2(-1)^n$

We have:

. . $\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 $n.$

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

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

What to do then?

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

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

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

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

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

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

The only thing I can do for b) is by a similar division process but I get
$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