How prove this $ a_{n+3}=8a_{n+2}-8a_{n+1}+a_{n}$

Question

Define the sequence of integers $\{a_{n}\}$ as: $$\begin{cases} a_{1}=33,a_{2}=49,a_{3}=177\\ a_{n+3}=8a_{n+2}-8a_{n+1}+a_{n} \end{cases}$$

show that $a_{n}$ is not divisible by $2013(=61\times 33)$.

my idea $$r^3-8r^2+8r-1=0$$ $$\Longrightarrow (r-1)(r^2+r+1)-8r(r-1)=0\Longrightarrow (r-1)(r^2-7r+1)=0$$ so $$a_{n}=A\cdot 1^n+B\left(\dfrac{7+3\sqrt{5}}{2}\right)^n+C\left(\dfrac{7-3\sqrt{5}}{2}\right)^n$$ and for $$a_{1}=33,a_{2}=49,a_{3}=177$$ then $$\Longrightarrow A=,B=,C=$$

and I have see this same problem,But following for this problem,I can't prove it.Thank you everyone

and this same problem :http://www.artofproblemsolving.com/Forum/viewtopic.php?p=2144391

Answer 1

Modulo $61$ you get a cycle of period $15$, none of whose values are $0$.

Spelling this out, for a term to be a multiple of $2013$, it must also be a multiple of $61$, so we only need to consider the remainders when each term is divided by $61$. For example $147 = 2\times 61 + 25$ so $147 \equiv 25 \pmod {61}$.

The next term is equivalent to $8\times 25 - 8 \times 49 + 33 \equiv 24 \pmod {61}$ and so on.

Continuing the process gives the sequence of remainders $33, 49, 25, 24, 41, 39, 8, 37, 27, 50, 38, 53, 48, 59, 19, 33, 49, 25, 24, 41, \ldots$ and the cycle repeats indefinitely. So $0$ never appears in the remainders, meaning no term is divisible by $61$ and so no term is divisible by $2013$.

Answer 2

First find the maximum periodicity of the sequence $r^n$ mod $p$ for $p \in 3,11,61$. Because $45$ is a square mod all three values of $p$, the characteristic polynomial factors completely.

Mod $3$, $r \in \pm 1$ with periods $1,2$.
Mod $11$, $r \in 1,3,4$ with periods $1,5,5$.
Mod $61$, $r \in 1,12,56$ with periods $1,15,15$.

(I used commands like diophantine ((3^n mod 11) = 1) in Wolfram alpha to get the periods)

Conclusions:

• mod $2013$, any integer sequence that satisfies the recurrence has period dividing $30$.

• This question can be answered for any sequence that satisfies the recurrence, by computing the first $2$ terms mod $3$, the first $5$ terms mod $11$, and the first $15$ terms mod $61$.

The key fact leading to small periodicity was

Because $45$ is a square mod all three values of $p$, the characteristic polynomial factors completely.

If this had not been not true, the period mod $p$ could have been approximately $p^2$ (when the characteristic polynomial has a quadratic factor) or $p^3$ when the polynomial does not factorize mod $p$.