Sunday, April 24, 2022

Sequence Problem

PROBLEM
Let
X0 = 0,
X1 = 1
and general formula for this sequence is
Xn+2 = 3·Xn+1 − 2·Xn
Prove that
Yn = Xn2 + 2(n+2) are exact squares of some natural numbers.
PROOF
Let's prove by induction that Xn = 2n − 1
(a) For n=0 this is true since x0 = 20 − 1 = 0, as set above
(b) For n=1 this is true since x1 = 21 − 1 = 1, as set above
(c) Assume that Xk = 2k − 1 and Xk+1 = 2k+1 − 1
and, based on that, calculate Xk+2:
Xk+2 = 3·Xk+1 − 2·Xk =
= 3·(2k+1 − 1) − 2·(2k − 1) =
= 3·2k+1 − 3 − 2·2k + 2 =
= 3·2k+1 − 2k+1 − 1 =
= 2·2k+1 − 1 =
= 2k+2 − 1

which corresponds to a formula that we are trying to prove.

Using this general formula for Xk = 2k − 1, we will prove that
Yn = Xn2 + 2(n+2) are exact squares of some natural numbers.
Indeed,
Yn = (2n − 1)2 + 2(n+2) =
= 22n − 2·2n + 1 + 2(n+2) =
= 22n − 2·2n + 1 + 4·2n =
= 22n + 2·2n + 1 =
= (2n + 1)2