4

I have the following recurrence: $a_{n+3}=3a_{n+2}-3a_{n+1}+a_n$ with initial values $a_1 = 1, a_2 = 4, a_3 = 9$

I have found the characteristic equation to be $x^3-3x^2+3x-1$ and the root to be 1.

My text book is not helpful in how I should go about solving this when I have a single root and don't have the $a_0$ value given.

Any tips on how I could move forward to solve this?

MrX
  • 77

2 Answers2

5

If the characteristic equation has roots $x_1,x_2,\ldots,x_k$, where ($x_i \neq x_j, \, \forall i \neq j$) the root $x_j$ has multiplicity $m_j$, then the solution is of the form $$a_n = \sum_{j=1}^k P_j(n)x_j^n$$ where $P_{j}(n)$ is a polynomial in $n$ of degree $m_j-1$. Hence, in your case, $$a_n = (c_0 + c_1 n + c_2 n^2) 1^n, \text{i.e., } a_n = c_0 + c_1 n + c_2 n^2$$ With the initial conditions, we get that $$a_n = n^2$$

  • Thanks for the explanation, however I am having trouble seeing how your using the initial conditions to get the final result. – MrX May 26 '13 at 06:16
  • @MrX: You plug them in. So $a_1=1=c_0+c_1\cdot 1 + c_2 \cdot 1^2=c_0+c_1+c_2, a_2=4=c_0+c_1\cdot 2 + c_2 \cdot 2^2=c_0+2c_1+4c_2$ and you can write one for $a_3$. You get three equations in three unknowns to solve. – Ross Millikan May 27 '13 at 16:32
0

Use Wilf's "generatingfunctionology". Define $A(z) = \sum_{n \ge 0} a_n z^n$, multiply your recurrence by $z^n$ and sum over $n \ge 0$ to get: $$ \frac{A(z) - a_0 - a_1 z - a_2 z^2}{z^3} = 3 \frac{A(z) - a_0 - a_1 z}{z^2} - 3 \frac{A(z) - a_0}{z} + A(z) $$ Using the recurrence "backwards" gives $a_0 = 0$. Solving for $A(z)$ and expanding into partial fractions: $$ A(z) = \frac{1}{1 - z} - \frac{3}{(1 - z)^2} + \frac{2}{(1 - z)^3} $$ By the expansions: $$ (1 - u)^{-m} = \sum_{k \ge 0} \binom{-m}{k} (-u)^k = \sum_{k \ge 0} \binom{k + m - 1}{m - 1} u^k $$ (the binomial coeffiecients are just $m - 1$ degree polynomials in $k$) you get: $$ a_n = 1 - 3 \binom{n + 1}{1} + 2 \binom{n + 2}{2} = 1 - 3 \frac{(n + 1)}{1} + 2 \frac{(n + 1) (n + 2)}{2} = n^2 $$

vonbrand
  • 27,812