# help with recurrence relations

• Aug 11th 2008, 02:11 PM
dixie
help with recurrence relations
Solve the following recurrence relation for a

a) an=3an-1-3an-2+an-3 a0=a1=1, a2=2

then

b) find and solve a recurrence relation for the number of ways to make a pile of n chips using red, white and blue chips and such that no two red chips are together.

Thanks for your help, i keep getting stuck
• Aug 11th 2008, 06:07 PM
Soroban
Hello, dixie!

Here's the first part . . .

Quote:

Solve the following recurrence relation for $a.$

. . $a_n\:=\:3a_{n-1}-3a_{n-2}+a_{n-3} \qquad a_0 = a_1 = 1,\;\;a_2=2$

We conjecture that: $a(n) = X^n$, an exponential function.

Then we have: . $X^n \:=\:3X^{n-1} - 3X^{n-2} + X^{n-3}$

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

. . . . . . . $(X - 1)^3 \:=\:0\quad\Rightarrow\quad X \:=\:1,1,1$

The function is of the form: . $a(n) \;=\;A + Bn + Cn^2$

. . $\begin{array}{cccccccc}
a(0) = 1\!: & A+B(0) + C(0^2) &=& 1 & \Rightarrow & A &=&1 \\
a(1) = 1\!: & A + B(1)+C(1^2) &=&1 & \Rightarrow & A + B + C &=&1 \\
a(2) = 2\!: & A + B(2)+C(2^2) &=&2 & \Rightarrow & A + 2B + 4C &=&2 \end{array}$

Solve the system of equations: . $A = 1,\;\;B = \text{-}\frac{1}{2},\;\;C = \frac{1}{2}$

Therefore: . $a(n) \;=\;1 - \frac{1}{2}n + \frac{1}{2}n^2 \quad\Rightarrow\quad\boxed{ a(n) \;=\;\frac{n^2 - n + 2}{2}}$