Finding the kth term of an iterated sequence The sequence $x_0, x_1, \dots$ is defined through $x_0 =3, x_1 = 18$ and $x_{n+2} = 6x_{n+1}-9x_n$ for $n=0,1,2,\dots\;$. What is the smallest $k$ such that $x_k$ is divisible by $2013$?
 A: HINT:
Using Characteristic equation, $$r^2-6r+9=0$$
So, $r=3,3$
$$\text{So,}x_n=(An+B)3^n$$ where $A,B$ are arbitrary constants
$3=x_0=B\implies B=3$ and $18=(A+3)\cdot3\implies A=3\implies x_n=(n+1)3^{n+1}$
Now, $2013=3\cdot11\cdot 61$
As $(3,61)=(3,11)=1\implies (n+1)$ must be divisible by $11\cdot 61=671$
and $(n+1)3^{n+1}$ must be divisible by $3$ which is true if $n\ge0$
So, $n=671\cdot a-1$ where $a$ is any integer
The minimum positive value of $n$ will be $671\cdot1-1=670$
A: You can tackle this by defining $X(z) = \sum_{n \ge 0} x_n z^n$, multiply the recurrence by $z^n$ and add for $n \ge 0$:
$$
\frac{X(z) - x_0 - x_1 z}{z^2} = 6 \frac{X(z) - x_0}{z} - 9 X(z)
$$
Plugging in the values and solving for $X(z)$:
$$
X(z) = \frac{3}{(1 - 3 z)^2}
$$
By the binomial theorem:
$$
(1 - u)^{-m} = \sum_{n \ge 0} \binom{-m}{n} (-u)^n
             = \sum_{n \ge 0} \binom{n + m - 1}{m - 1} u^n
$$
In our case:
$$
x_n = 3 \binom{n + 1}{1} \cdot 3^n = (n + 1) \cdot 3^{n + 1}
$$
The rest of the job was explained by lab bhattacharjee's answer.
