Finding the kth term of an iterated sequence

Question

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$?

Answer 1

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$

Answer 2

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.