Proving divisibility for a recurrence relation Given:
$$U_1  = -1 \\ U_n = (U_{n-1})^2 - 8 ~~ \text{for} ~~ n \in \mathbb{N} \setminus\{1\}$$
I need to prove that $U_n$ is divisible by $7$ for all even values. of $n$.
I thought it's proof by induction but I have only used it for numbers greater than $n$, not even numbers for $n$ so I'm not sure how to go about it.
I so far have proven it's true for $U_2$, how would I work it out?
 A: The base case is clear: $U_2=-7$ is divisible by $7$.
Now suppose that $U_{2n}$ is divisible by $7$.
Show that
$$(*) \quad U_{2n+2}= U_{2n}^4-16U_{2n}^2+56.$$
All summands on tht RHS of $(*)$ are divisible by $7$.
We are done !
A: First step: Checking if $7 \mid U_2$ :
$$ U_2 = (U_1)^2 -8 = (-1)^2 -8 = -7 \Rightarrow 7 \mid (-7)$$
Next we assume that $$7 \mid U_{2k} \Rightarrow U_{2k} = 7a, a\in \mathbb{Z}$$
Now we need to prove:
$$ 7 \mid U_{2k+2} \Rightarrow U_{2k+2} = 7j, j \in \mathbb{Z}$$
We know according to the definition of $U_n$:
$$ U_{2k+2} = (U_{2k+1})^2 - 8 \\ U_{2k+1} = (U_{2k})^2-8$$
And thus:
$$ U_{2k+2} = (U_{2k}^2 - 8)^2 - 8$$
We assumed that $U_{2k} = 7a$ and of-course $U_{2k}^2 = 49a$ which is still divisible by 7 (Let's rename for simplicity: $49a = 7m$), and now we can substitute that into this equality:
$$U_{2k+2} = (7m-8)^2 - 8 = 7 \cdot7m^2 - 7 \cdot 2 \cdot 8 \cdot m + 64 - 8 = 7 \cdot7m^2 - 7 \cdot 2 \cdot 8 \cdot a + 7 \cdot 8 $$
And we can see right away this number is divisible by $7$
