1

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?

CSch of x
  • 1
draw electric
  • 55
  • I think induction is the right track, but instead of proving for $U_{n+1}$ when its true for $U_n$, you have to consider $U_{n+2}$. – nicomezi Oct 22 '20 at 06:21

2 Answers2

1

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 !

Fred
  • 77,394
0

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$

CSch of x
  • 1