<s>[INST] If $k$ is multiple of $3$, then $x_k$ is even. 
Let $ \ (x_k) \in \mathbb{N}^{\mathbb{N}} \ $ be such that $ \ x_0=0 \ $, $ \ x_1=1 \ $ and $$ \ x_k = 3x^3_{k-1}+7x^5_{k-2} \ $$ $ \ \forall k \geq 2 \ $. Prove that $ \, x_k \, $ is even, for all $k$ multiple of $3$.


I tried to use induction with steps of size $3$:
$x_2 = 3 \ \Rightarrow \ x_3 = 3 \cdot 3^3 + 7 = 88 \ $ is even.
Let $k$ be a multiple of $3$ such that $ \, x_k \, $ is even. Then
$x_{k+3} = 3x^3_{k+2} + 7x^5_{k+1} = 3 (3x^3_{k+1}+7x^5_{k}) + 7(3x^3_{k}+7x^5_{k-1}) = \ ...$
I am trying to arrange this recurrence formula in a way to substitute $ \, x_k \, $ for $ \, 2m \, $ and obtaining $ \ x_{k+3} = 2 \cdot ( ...... ) \ $, but failing in the process.
 [/INST] We could show, by modular congruence, that $x_{3m} \equiv 0 \pmod2$. We know that $7 \equiv 3 \equiv1 \pmod2$. We also know that $x^2 \equiv x \pmod2$ in the special case of mod 2 congruence: if $x$ is even, so will be $x^2$; if $x$ is odd, so will be $x^2$. Therefore, we can generalize to $x^n \equiv x \pmod2$. (*)
Finally, all of this translates to:
$$ x_k \equiv 3(x_{k-1})^3+7(x_{k-2})^5\equiv (x_{k-1})^3 + (x_{k-2})^5 \equiv x_{k-1}+x_{k-2} \pmod2 $$
Since $x_{k-1}=3(x_{k-2})^3+7(x_{k-3})^5$, we have that
$$x_{k-1} \equiv x_{k-2}+x_{k-3} \pmod2$$
Therefore,
$$x_k \equiv 2 x_{k-2}+x_{k-3} \equiv x_{k-3} \pmod2 \textrm{ (**)}$$
Using $k=3m$, we can rewrite this as
$$ x_{3m} \equiv x_{3(m-1)} \pmod2 $$
By induction, we see that $x_{3m} \equiv x_{0} \pmod2$ (***). Since $x_0 \equiv 0 \pmod2$, we have that $x_{3m}$ must be even.
Edit for further clarity:
(*):
Let $y$ be any natural number (including $0$). If $y$ is odd, then its remainder upon division by $2$ must be $1$ (by the definition of odd numbers: those which are not divisible by $2$). If $y$ is even, then its remainder upon division by $2$ must be $0$ (by the definition of even numbers: those which are divisible by $2$).
First, if $y$ is odd, we have the following congruence $\pmod2$:
$$y \equiv 1 \pmod2$$
Using the properties of modular congruence, the relation will still be valid upon multiplication of both sides by any integer. If we multiply both sides by $y$:
$$y^2 \equiv y \pmod2$$
Since $y$ is obviously still congruent to $1$, the above equiation can also be written as:
$$y^2 \equiv y \equiv 1 \pmod{2}$$
I can once again multiply all sides by $y$, obtaining:
$$y^3 \equiv y^2 \equiv y \equiv 1 \pmod{2}$$
By induction, then, we arrive at the conclusion that
$$y^n \equiv y \equiv 1 \pmod2$$
for any natural integer $n$.
Repeating the above but when $y$ is even, we would arrive at
$$y \equiv 0 \pmod2 \implies y^2 \equiv 0 \pmod2 \implies y^2 \equiv y \equiv 0 \pmod2$$
which would naturally lead us into
$$y^n \equiv y \equiv 0 \pmod2$$
So, (*) is valid for any natural $y$, as $y^n \equiv y \pmod2$ is valid when $y$ is even and when it's odd.
(**):
$2 \equiv 0 \pmod2$, which means $2x_{k-2} \equiv 0 \pmod2$.
(***):
Note that the congruence relation $x_{3m} \equiv x_{3(m-1)} \pmod2$ can be naturally extended to $x_{3m} \equiv x_{3(m-1)} \equiv x_{3(m-2)} \equiv \ldots \equiv x_{3} \equiv x_0 \pmod2$ by the use of induction. First, it has been already calculated that $x_3 \equiv x_0 \pmod2$ (given that $x_3=88$). Second, notice that $m$ is any given integer (such that $k-1=3m-1\geq2$, as the recurrence formula demands for both $x_k$ and $x_{k-1}$). Therefore, $m-1=m'$ and the modular congruence equiation could be easily re-obtained (as, again, the derivation of this congruence equation involved any given integer $m$ such that $k=3m\geq2$, not a specific $m$):
$$x_{3m'} \equiv x_{3(m'-1)} \pmod2$$
Substituting $m'=m-1$, we would have
$$x_{3(m-1)} \equiv x_{3(m-2)} \pmod2$$
Since $x_{3m'} \equiv x_{3(m'-1)} \pmod2$, the above translates to
$$x_{3m} \equiv x_{3(m-1)} \equiv x_{3(m-2)} \pmod2$$
I can repeat this induction up until $3m=3,m=1$, which means
$$x_{3m} \equiv \ldots \equiv x_3 \equiv x_0 \pmod2$$
Note: I can in fact impose that $x_{3m} \equiv x_0 \pmod2$ based on this induction alone. Remember, this recurrence relation requires that the term on the left (in $x_{3m} \equiv x_{3(m-1)} \pmod2$) respects $3m-1\geq2$, or $m\geq1$. It does not matter if the term on the right respects that condition or not (refer back to the derivation of the recurrence formula): what is truly important is that both $x_k$ and $x_{k-1}$ are greater than $2$. Therefore, $x_3 \equiv x_0 \pmod2$ is correct and does not depend on any previous calculation of the parity of $x_3$.
$$x_{3m} \equiv \ldots \equiv x_3 \equiv x_0 \pmod2$$
</s>