# Recurrence Relation

• Mar 22nd 2009, 07:18 AM
vexiked
Recurrence Relation
Could anyone direct me on how to solve these? Im stuck. (n-1 are subscripts)

An=2An-1 -3, a0 = -1
An=(n+1)An-1, a0=2
An=2nAn-1, a0=3
An=-An-1 + n - 1, a0 = 7

• Mar 22nd 2009, 08:21 AM
vexiked
Even a general method would help! Thanks
• Mar 22nd 2009, 09:46 AM
Soroban
Hello, vexiked!

I'll walk through the first one.

Quote:

Could anyone direct me on how to solve these?

$(1)\;A_n\:=\:2A_{n-1} -3,\quad a_0 = -1$

We conjecture that $A_n$ is of the form: . $X^n$, an exponential expression.

$\begin{array}{ccccc}\text{Then we have:} & X^n &=& 2X^{n-1} - 3 & {\color{blue}[1]} \\
\text{Write the "next" term:} & X^{n+1} &=& 2X^n - 3 & {\color{blue}[2]}\end{array}$

Subtract [2] - [1]: . $X^{n+1} - X^n \:=\:2X^n - 2X^{n-1} \quad\Rightarrow\quad X^{n+1} - 3X^n + 2X^{n-1} \:=\:0$

Divide by $X^{n-1}\!:\;\;X^2 - 3X + 2 \:=\:0 \quad\Rightarrow\quad (X-1)(X-2) \:=\:0 \quad\Rightarrow\quad X \:=\:1,\:2$

. . Hence, the function has: . $1^n\text{ and }2^n$

Form a linear combination of the two roots: . $f(n) \;=\;A\cdot1^n + B\cdot2^n$

. . and we have: . $f(n) \;=\;A + B\!\cdot\!2^n$

Use the first two terms of the sequence:

. . $\begin{array}{ccccccccc}f(0) = \text{-}1\!: & A + B\!\cdot\!2^0 &=& \text{-}1 & \Rightarrow & A + B &=& \text{-}1 & {\color{blue}[3]} \\
f(1) = \text{-}5\!: & A + B\!\cdot\!2^1 &=&\text{-}5 & \Rightarrow & A + 2B &=& \text{-}5 & {\color{blue}[4]} \end{array}$

Subtract [4] - [3]: . $B \:=\:\text{-}4$

Substitute into [3]: . $A - 4 \:=\:\text{-}1 \quad\Rightarrow\quad A \:=\:3$

Therefore: . $f(n) \:=\:3 - 4\!\cdot\!2^n \quad\Rightarrow\quad\boxed{ f(n) \:=\:3 - 2^{n+2}}$