A periodic sequence with period $P$ can always be written as a trigonometric polynomial $$a_n = \sum_{j=0}^{P-1} b_j \cos(2 \pi j n/P) + \sum_{j=1}^{P-1} c_j \sin(2 \pi j n/P)$$
for some coefficients $b_j$ and $c_j$ (look up Finite Fourier Transform).
Thus your first example can be written as
$$a_n = 4-\cos \left( \pi\,j/2 \right) -\cos \left( \pi\,j \right) -\cos
\left( 3\,\pi\,j/2 \right) -\sin \left( \pi\,j/2 \right) +\sin
\left( 3\,\pi\,j/2 \right)
$$
I finally solved the question.
Here is the if part.
Suppose that
$$
\Delta =
\det {
\begin{bmatrix}
A & B & D \\
B & C & E \\
D & E & F \\
\end{bmatrix}
}
= ACF + 2BED - (AE^2 + CD^2 + FB^2) = 0.
$$
The proof splits into a few cases.
(a)
$A = B = C = 0$.
Then
$$
\begin{aligned}
f(x, y)
= 2Dx + 2Ey + F
= (0x + 0y + 1)(2Dx + 2Ey + F).
\end{aligned}
$$
(b)
$A = C = 0$, but $B \neq 0$.
Then
$$
\begin{aligned}
f(x, y)
= {} & 2Bxy + 2Dx + 2Ey + F \\
= {} & \frac{2}{B}(Bx \cdot By + D \cdot Bx + E \cdot By) + F \\
= {} & \frac{2}{B}(Bx \cdot By + D \cdot Bx + E \cdot By + DE - DE) + F \\
= {} & \frac{2}{B}(Bx \cdot By + D \cdot Bx + E \cdot By + DE) - \frac{2}{B} \cdot DE + F \\
= {} & \frac{2}{B}(Bx + E)(By + D) - \frac{2ED - FB}{B} \\
= {} & \left(1x + 0y + \frac{E}{B}\right)(0x + 2By + 2D) - \frac{2BED - FB^2}{B^2}.
\end{aligned}
$$
Since $\Delta = 0$ and $A = C = 0$,
$$
\begin{aligned}
\Delta = 0 + 2BED - (0 + 0 + FB^2) = 2BED - FB^2 = 0.
\end{aligned}
$$
We conclude that
$$
\begin{aligned}
f(x, y) = \left(1x + 0y + \frac{E}{B}\right)(0x + 2By + 2D).
\end{aligned}
$$
(c)
$A \neq 0$.
Then
$$
\begin{aligned}
& f(x, y) \\
= {} & Ax^2 + 2(By + D)x + (Cy^2 + 2Ey + F) \\
= {} & \frac{(Ax + By + D)^2 - (By + D)^2}{A}
+ (Cy^2 + 2Ey + F) \\
= {} & \frac{1}{A} (Ax + By + D)^2 + \frac{1}{A}((AC - B^2)y^2 + 2(AE - BD)y) + \frac{AF - D^2}{A}.
\end{aligned}
$$
The case splits into two subcases.
(c.1)
$AC - B^2 = 0$.
Hence $C = \frac{B^2}{A}$.
Hence
$$
\begin{aligned}
\Delta
= {} & A \cdot \frac{B^2}{A} \cdot F + 2BED - AE^2
- \frac{B^2 D^2}{A} - FB^2 \\
= {} & {-\frac{1}{A}}
(A^2 E^2 - 2AE BD + B^2 D^2) \\
= {} & {-\frac{1}{A}} (AE - BD)^2.
\end{aligned}
$$
Since $\Delta = 0$,
we have $AE - BD = 0$.
Hence
$$
\begin{aligned}
f(x, y) = \frac{(Ax + By + D)^2 - (D^2 - AF)}{A}.
\end{aligned}
$$
There exists a complex number $d$ such that $d^2 = D^2 - AF$.
Hence
$$
\begin{aligned}
f(x, y) = \frac{1}{A} (Ax + By + D + d)(Ax + By + D - d),
\end{aligned}
$$
which is
$$
\begin{aligned}
f(x, y) = \left( 1x + \frac{B}{A} y + \frac{D+d}{A} \right) (Ax + By + (D - d)).
\end{aligned}
$$
(c.2)
$AC - B^2 \neq 0$.
Then
$$
\begin{aligned}
& (AC - B^2) y^2 + 2(AE - BD)y
\\
= {} & \frac{1}{AC - B^2} ((AC - B^2)y + (AE - BD))^2 - \frac{(AE - BD)^2}{AC - B^2}.
\end{aligned}
$$
Hence
$$
\begin{aligned}
f(x, y)
= {} & \frac{(Ax + By + D)^2}{A} - \frac{((B^2 - AC)y + (BD - AE))^2}{A(B^2 - AC)}
\\
& \quad
+ \frac{AF - D^2}{A} - \frac{(AE - BD)^2}{A(AC - B^2)},
\end{aligned}
$$
which is just
$$
\begin{aligned}
f(x, y) = \frac{(Ax + By + D)^2}{A} - \frac{((B^2 - AC)y + (BD - AE))^2}{A(B^2 - AC)} + \frac{\Delta}{AC - B^2}.
\end{aligned}
$$
Since $\Delta = 0$,
$$
\begin{aligned}
f(x, y) = \frac{(Ax + By + D)^2}{A} - \frac{((B^2 - AC)y + (BD - AE))^2}{A(B^2 - AC)}.
\end{aligned}
$$
There exists a complex number $e$ such that $e^2 = B^2 - AC$.
Put $f = \frac{BD-AE}{e}$.
Then
$$
\begin{aligned}
f(x, y)
= {} & \frac{(Ax + By + D)^2}{A} - \frac{(e^2 y + ef)^2}{Ae^2} \\
= {} & \frac{(Ax + By + D)^2}{A} - \frac{(ey + f)^2}{A} \\
= {} & \frac{1}{A}(Ax + By + D + ey + f)(Ax + By + D - ey - f) \\
= {} & \left( 1x + \frac{B+e}{A}y + \frac{D+f}{A} \right) (Ax + (B-e)y + (D-f)).
\end{aligned}
$$
(d)
$C \neq 0$.
We rewrite $f(x, y)$ as
$$
\begin{aligned}
Cy^2 + 2Byx + Ax^2 + 2Ey + 2Dx + F.
\end{aligned}
$$
Put
$$
\begin{aligned}
g(x, y) = Cx^2 + 2Bxy + Ay^2 + 2Ex + 2Dy + F,
\end{aligned}
$$
which means that for any ordered pair of complex numbers $(z, w)$,
$$
\begin{aligned}
g(z, w) = f(w, z).
\end{aligned}
$$
A straightforward computation show that
$$
\begin{aligned}
\Delta'
= {} &
\det {\begin{bmatrix}
C & B & E \\
B & A & D \\
E & D & F \\
\end{bmatrix}} \\
= {} & CAF + 2BDE - (CD^2 + AE^2 + FB^2) \\
= {} & ACF + 2BED - (AE^2 + CD^2 + FB^2) \\
= {} & \Delta.
\end{aligned}
$$
By (c), there exist six complex numbers
$a_1$, $a_2$, $a_3$, $a_4$, $a_5$, $a_6$
such that
$$
\begin{aligned}
g(x, y) = (a_1 x + a_2 y + a_3) (a_4 x + a_5 y + a_6).
\end{aligned}
$$
Hence
$$
\begin{aligned}
&
f(x, y) = g(y, x) = (a_2 x + a_1 y + a_3) (a_5 x + a_4 y + a_6).
\end{aligned}
$$
Best Answer
This question seems pretty tricky! Let's say $x_n$ is the (nonnegative) number such that $x_n^2 + (x_n + 1)^2 = a_n$. My first thoughts were that $x_n$ is roughly $\sqrt{a_n/2}$, and also that $a_n$ grows roughly like $14^n$. Therefore I guessed that $x_n$ should grow roughly like $4^n$. Then if you write down $5$ or $6$ values of $x_{n + 1} - 4 x_n$ (to see what the "error" is in the recurrence $x_{n + 1} = 4 x_n$), you might notice a pattern - $x_{n + 2} = 4 x_{n + 1} - x_n + 1$.
From here I think it's still surprisingly difficult to make progress (at least for me! Perhaps I have missed an easier approach).
When you induct on $n$ to try and show that $a_n = x_n^2 + (x_n + 1)^2$, when you expand you're left with something a bit nasty: \begin{align*} a_{n + 2} - x_{n + 2}^2 - (x_{n + 2} + 1)^2 &= 14 a_{n + 1} - a_n - (4 x_{n + 1} - x_n + 1)^2 - (4 x_{n + 1} - x_n + 1 + 1)^2 \\ &= 14 (x_{n + 1}^2 + (x_{n + 1} + 1)^2) - (x_n^2 + (x_n + 1)^2) - (4 x_{n + 1} - x_n + 1)^2 - (4 x_{n + 1} - x_n + 1 + 1)^2 \\ &= -4[x_n^2 + x_{n + 1}^2 - x_n - x_{n + 1} - 4 x_n x_{n + 1} - 2] \end{align*} I think the fact that this algebra doesn't work itself out immediately is also part of what makes the problem hard - it seems difficult to find the right expression for $x_n$ from just trying the induction and seeing what you need to make the inductive step work.
Nevertheless, we can still proceed from here, if we just believe in ourselves. If we denote this remainder term by $d_n$, what we have to do now is prove by induction that $d_n = 0$ for all $n$. You can sort of predict that this might be fruitful by spotting that $d_{n + 1} - d_n$ will factorise very nicely - you can take out a factor of $x_{n + 2} - x_n$, in fact: \begin{equation*} d_{n + 1} - d_n = (x_{n + 2} - x_n)[x_{n + 2} + x_n - 1 - 4x_{n + 1}] = 0 \end{equation*} by the recurrence for $x_{n + 2}$.
From here it follows that $d_n$ is always $0$ (don't forget to check the base case!)
This definitely involved some guesswork if you don't want to use OEIS. I suspect that this is one of those questions where there's a lot of very serious number theory secretly going on, but if you're learning about induction then that's probably not the way you're supposed to answer. You could be a bit more structured about it and guess something more general like $x_{n + 2}$ being a linear combination of $x_{n + 1}, x_n, 1$.