## Sequence : S_{n+3} = 2(S_{n+2}) + 2(S_{n+1}) – S_{n}

The sequence   $F_{n}$   of Fibonacci numbers is defined by the recurrence relation

$F_{n} = F_{n-1} + F_{n-2}$

with seed values
$F_1 = F_2 = 1$,    or
$F_0 = 0$,    $F_1 = 1$

Let   $S_1 = S_2 = 1$,    $S_3 = 4$,   and

$S_{n+3} = 2 \cdot S_{n+2} + 2 \cdot S_{n+1} - S_{n}$     for   $n \geq 1$

$S_1 = S_2 = 1^2 = ( \,F_1 \,)^2 = ( \,F_2 \,)^2$     $S_3 = 2^2 = ( \,F_3 \,)^2$

$S_4 = 2 \cdot S_{3} + 2 \cdot S_{2} - S_{1} = 2(2^2) + 2(1^2) - 1^2 = 3^2 = ( \,F_4 \,)^2$
$S_5 = 2 \cdot S_{4} + 2 \cdot S_{3} - S_{2} = 2(3^2) + 2(2^2) - 1^2 = 5^2 = ( \,F_5 \,)^2$
$S_6 = 2 \cdot S_{5} + 2 \cdot S_{4} - S_{3} = 2(5^2) + 2(3^2) - 2^2 = 8^2 = ( \,F_6 \,)^2$
$S_7 = 2 \cdot S_{6} + 2 \cdot S_{5} - S_{4} = 2(8^2) + 2(5^2) - 3^2 = 13^2 = ( \,F_7 \,)^2$
$S_8 = 2 \cdot S_{7} + 2 \cdot S_{6} - S_{5} = 2(13^2) + 2(8^2) - 5^2 = 21^2 = ( \,F_8 \,)^2$
$S_9 = 2 \cdot S_{8} + 2 \cdot S_{7} - S_{6} = 2(21^2) + 2(13^2) - 8^2 = 34^2 = ( \,F_9 \,)^2$

Is   $S_{p}$   always a perfect square?   Yes.

Suppose this is true for   $p \; \leq \; (n+2)$.
Let’s prove that this result also holds for   $p \; = \; n+3$

$F_{n+2} \; = \; F_{n+1} \; + \; F_{n}$

$S_{n+3}$
$= 2 \cdot S_{n+2} + 2 \cdot S_{n+1} - S_{n}$
$= 2( \,F_{n+2} \,)^2 + 2( \,F_{n+1} \,)^2 - ( \,F_{n} \,)^2$
$= 2( \,F_{n+2} \,)^2 + 2( \,F_{n+1} \,)^2 - ( \,F_{n+2} - F_{n+1} \,)^2$
$= 2( \,F_{n+2} \,)^2 + 2( \,F_{n+1} \,)^2 - ( \,F_{n+2} \,)^2 - ( \,F_{n+1} \,)^2 + 2 \cdot F_{n+2} \cdot F_{n+1}$
$= ( \,F_{n+2} \,)^2 + ( \,F_{n+1} \,)^2 + 2 \cdot F_{n+2} \cdot F_{n+1}$
$= ( \,F_{n+2} + F_{n+1} \,)^2$
$= ( \,F_{n+3} \,)^2$

$S_{p}$   is a perfect square for all   $p$.