How to find the initial terms of the recurrence relation if you know the nth term?

Question

Given the recurrence relation $a_n = 2a_{n-1} - a_{n-2}$ how can I find the initial terms if $a_9 = 30$?

For which $x$ are there initial terms which make $a_9 = x$?

I know that there is no solution to the recurrence relation if $a_0 = 1$ and $a_1 = 2$ using the Characteristic Root Technique:

$ x^2 -2x +1 = 0$ which results in $r_1 = 1$ and $r_2 = 1$.

$a_n = ar_1^n + br_2^n$

$a_n = a(1)^n + b(1)^n$

$a_0 = a(1)^0 + b(1)^0$ which results in $1 = a + b$.

$a_1 = a(1)^1 + b(1)^1$ which results in $2 = a + b$.

Obviously $1 != 2$ resulting in no solution.

Answer 1

$$a_9=2a_8-a_7=2(2a_7-a_6)-a_7=3a_7-2a_6=3(2a_6-a_5)-2a_6=4a_6-3a_5=\cdots$$

and in the end

$$a_9=pa_1+qa_0.$$

$$a_9=9a_1-8a_0.$$

This linear equation in two unknowns has an infinity of solutions.

Answer 2

With repeated roots, you're supposed to use $a_n = ar^n+bnr^n$. So if $a_0=1$ and $a_1=2$, then you have

$a_0 = 1a +0b = 1$

$a_1 = 1a + 1b = 2$

So $a=1$, $b = 1$ and $a_n = 1+n$.

You can check this with

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

If you're just given $a_9=30$, that's insufficient to find the initial terms, as you have two unknowns but only one equation.

Also, if you're using MathJax, typing != will result in a space between ! and =. Use \neq instead.

Answer 3

One way is to use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, shift the recurrence by two, multiply by $z^n$ and sum over $n \ge 0$, recognize sums:

$\begin{align*} \sum_{n \ge 0} a_{n + 2} z^n &= 2 \sum_{n \ge 0} a_{n + 1} z^n - \sum_{n \ge 0} a_n z^n \\ \frac{A(z) - a_0 - a_1 z}{z^2} &= 2 \frac{A(z) - a_0}{z} - A(z) \end{align*}$

Solve for $A(z)$:

$\begin{align*} A(z) &= \frac{a_0 + (a_1 - 2 a_0) z}{(1 - z)^2} \end{align*}$

Using the general binomial theorem:

$\begin{align*} (1 + u)^{-m} &= \sum_{n \ge 0} \binom{-m}{n} u^n \\ &= \sum_{n \ge 0} (-1)^n \binom{n + m - 1}{m - 1} u^n \end{align*}$

you have the coefficients:

$\begin{align*} a_n &= [z^n] A(z) \\ &= (a_0 [z^n] + (a_1 - 2 a_0) [z^{n - 1}]) (1 - z)^{-2} \\ &= a_0 \binom{n + 2 - 1}{2 - 1} + (a_1 - 2 a_0) \binom{n - 1 + 2 - 1}{2 - 1} \\ &= (a_1 - a_0) n + a_0 \end{align*}$

Sadly you only know $a_9$, that doesn't determine the two required initial values.