Brazilian Math Olympiad

Let $(a_n^{(i)})$ be the sequence of integers obtained by shifting $a_n$ by $i$ positions, i.e., $a_n^{(i)} = a_{n+i}$. Then
$$(a_n^{(0)}), (a_n^{(1)}), \dots, (a_n^{(k)})$$
is a basis for the $k$-dimensional $C$-vector space of sequences $(b_n)$ satisfying
$$b_{n+k} = c_{k-1}b_{n+k-1} + \dots + c_0b_n \quad (n \ge 0) \quad (*)$$
In fact, any non-trivial $C$-linear relation among $(a_n^{(0)}, \dots, a_n^{(k-1)})$ would
imply that $k$ is not minimal.

Now let
$$f(x) = x^k - c_{k-1}x^{k-1} - \dots - c_0$$
and
$\alpha_1, \dots, \alpha_k$
be the roots of $f(x)$ (listed with multiplicity). First, observe that all coefficients $c_i$ are rational since they are solutions to the linear system with integer coefficients
$$\begin{pmatrix} a_0 & a_1 & \dots & a_{k-1} \\ a_1 & a_2 & \dots & a_k \\ \vdots & \vdots & \ddots & \vdots \\ a_{k-1} & a_k & \dots & a_{2k-2} \end{pmatrix} \begin{pmatrix} c_0 \\ c_1 \\ \vdots \\ c_{k-1} \end{pmatrix} = \begin{pmatrix} a_k \\ a_{k+1} \\ \vdots \\ a_{2k-1} \end{pmatrix}$$

$$t_n = \alpha_1^n + \alpha_2^n + \dots + \alpha_k^n \quad (n \ge 0)$$
Then all $t_n \in \mathbb{Q}$ (they are symmetric expression on the roots of $f(x) \in \mathbb{Q}[x]$) and the $t_n$ satisfy $(*)$, hence there are $r_i$ such that
$$t_n = r_0 a_n^{(0)} + r_1 a_n^{(1)} + \dots + r_{k-1} a_n^{(k-1)}$$

To sum up, if $d > 0$ is an integer such that $dr_i \in \mathbb{Z}$, $i = 0, 1, \dots, k-1$, then
$$dt_n \in \mathbb{Z}$$
for all $n$. Next, we show that this implies that the $\alpha_i$ are algebraic integers, which in turn implies that all the $c_i$ are integers, finishing the problem.
By Newton's identities, we may write the elementary symmetric polynomials in $\alpha^n$ as polynomials with rational coefficients of
$$\begin{align*} t_n &= \alpha_1^n + \dots + \alpha_k^n \\ t_{2n} &= \alpha_1^{2n} + \dots + \alpha_k^{2n} \\ &\vdots \\ t_{kn} &= \alpha_1^{kn} + \dots + \alpha_k^{kn} \end{align*}$$
Therefore the minimal polynomials of $\alpha_i^n$ over $\mathbb{Q}$ have coefficients with bounded denominators, independent of $n$ (they depend only on $d$ and $k$). Hence there exists an integer $\Delta > 0$ such that $\Delta \cdot \alpha_i^n$ are algebraic integers for all $n$. But that implies that the ring $\mathbb{Z}[\alpha_i]$ is contained in the finitely generated $\mathbb{Z}$-module $\frac{1}{\Delta}\mathcal{O}_{\mathbb{Q}(\alpha_i)}$, where $\mathcal{O}_{\mathbb{Q}(\alpha_i)}$ is the ring of algebraic integers in the field $\mathbb{Q}(\alpha_i)$. Therefore $\mathbb{Z}[\alpha_i]$ itself is finitely generated as a $\mathbb{Z}$-module (use the fact that $\mathbb{Z}$ is noetherian or that $\mathcal{O}_{\mathbb{Q}(\alpha_i)}$ is a free $\mathbb{Z}$-module, together with the structure theorem of finitely generated modules over a PID). Hence $\alpha_i$ is an algebraic integer, as required.

Alternatively, suppose that $\alpha_i$ is not an algebraic integer, so that it has prime ideal factorization
$$(\alpha_i) = p_1^{e_1} \dots p_s^{e_s}$$
with $e_i < 0$ for some $i$, say $e_1$.
Then
$$(\Delta \alpha_i^n) = (\Delta) \cdot p_1^{ne_1} \dots p_s^{ne_s}$$
would have a negative $p_1$-exponent for $n$ sufficiently large, contradicting the fact that $\Delta \cdot \alpha_i^n$ is an algebraic integer for all $n \ge 0$.