$u_{2018}= 5\,.2^{2018}$

Question

The sequence $\left ( u_{n} \right )$ is determined as follows:

$$u_{1}= 14\,,u_{2}= 20\,,u_{3}= 32\,,u_{n+ 2}= 4\,u_{n+ 1}- 8\,u_{2}+ 8\,u_{n-1}$$

with $n\geqq 2$

Prove: $$u_{2018}= 5\,.2^{2018}$$

First, I have realized that $u_{1}= 7\,.2^{1}\,,u_{2}= 5\,.2^{2}\,,u_{3}= 4\,.2^{3}\,,u_{4}= 5\,.2^{4}\,,u_{5}= 7\,.2^{5}\,...\,,u_{2018}= 7\,.2^{2018}$

I think the generlization sequence is: $u_{n}=a\,.2^{n}$

But how I can prove it. Help me! Thanks!

Answer 1

Hint: Try setting $u_n=b \times a^n$, substitute into your equation and solve for $a$. You can estimate $b$ from the intial conditions or set it at first to be $1$.

Answer 2

The characteristic polynomial of the recurrence is $$ x^3 - 4x^2 + 8x - 8 $$ whose roots are $2$, $2\xi$, and $2\xi^{-1}$, where $\xi=\frac{1+\sqrt3 i}2$ is a primitive sixth root of unity. So every solution is a linear combination of the sequences $$ (2^n)_n \qquad (\xi^n2^n)_n \qquad (\xi^{-n}2^n)_n $$ In particular you always have $$ \tag{*} u_{n+6} = 2^6u_n $$

If you don't know enough theory of linear recurrences to derive (*) as slickly as this, you can also get it by throwing enough high-school algebra at the original recurrence, producing $u_{n+6}$ as a function of $u_n$, $u_{n+1}$, and $u_{n+2}$. Or by computing $$ \begin{pmatrix} 4 & -8 & 8 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^{\textstyle 6} $$

Answer 3

Nice observation! But you need to go further to see the pattern. Indeed, the sequence $a_n=\dfrac{u_n}{2^n}$ is $$ 7,5,4,5,7,8,7,5,4,5,7,8,7,5,4,5,7,8,7,5,\dots $$ Therefore, $a_n$ is periodic of period $6$, not $4$. You can prove this by induction.

Since $2018 = 6 \cdot 336 + 2$, we get $ a_{2018} = a_2 = 5 $ and so $u_{2018} = a_{2018} 2^{2018} = 5 \cdot 2^{2018}$.