Problem 1545

1. Define the sequences and initial conditions:
We are given the sequences $a_n$ and $b_n$ with initial conditions:
$$a_0 = 1, \quad a_1 = 4, \quad a_2 = 49$$
and the recurrence relations:
$$\begin{cases} a_{n+1} = 7a_n + 6b_n - 3, \\ b_{n+1} = 8a_n + 7b_n - 4. \end{cases}$$

2. **Express $a_{n+1}$ in terms of previous terms:**
We start by expressing $a_{n+1}$ in terms of $a_n$ and $b_n$:
$$a_{n+1} = 7a_n + 6b_n - 3$$
We also have:
$$7a_n = 49a_{n-1} + 42b_{n-1} - 21$$
Subtracting the second equation from the first:
$$a_{n+1} - 7a_n = (7a_n + 6b_n - 3) - (49a_{n-1} + 42b_{n-1} - 21)$$
Simplifying, we get:
$$a_{n+1} - 7a_n = 6b_n - 3 - 49a_{n-1} - 42b_{n-1} + 21$$

3. **Use the recurrence relation for $b_n$:**
We know:
$$b_n - 7b_{n-1} = 8a_{n-1} - 4$$
Substituting this into the previous equation:
$$a_{n+1} - 7a_n = 6(7b_{n-1} + 8a_{n-1} - 4) - 3 - 49a_{n-1} - 42b_{n-1} + 21$$
Simplifying further:
$$a_{n+1} - 7a_n = 42b_{n-1} + 48a_{n-1} - 24 - 3 - 49a_{n-1} - 42b_{n-1} + 21$$
$$a_{n+1} - 7a_n = -a_{n-1} - 6$$
Rearranging, we get:
$$a_{n+1} = 14a_n - a_{n-1} - 6$$

4. Form the characteristic equation:
The recurrence relation is:
$$a_{n+1} - 15a_n + 15a_{n-1} - a_{n-2} = 0$$
The characteristic equation is:
$$x^3 - 15x^2 + 15x - 1 = 0$$

5. Solve the characteristic equation:
One root is obviously $x = 1$. The other roots can be found by factoring or using the quadratic formula:
$$(x - 1)(x^2 - 14x + 1) = 0$$
Solving the quadratic equation:
$$x = \frac{14 \pm \sqrt{196 - 4}}{2} = 7 \pm 4\sqrt{3}$$
So the roots are $1, 7 + 4\sqrt{3}, 7 - 4\sqrt{3}$.

6. Form the general solution:
The general solution to the recurrence relation is:
$$a_n = A \cdot 1^n + B \cdot (7 + 4\sqrt{3})^n + C \cdot (7 - 4\sqrt{3})^n$$
Using the initial conditions $a_0 = 1$, $a_1 = 4$, and $a_2 = 49$, we solve for $A$, $B$, and $C$:
$$a_n = \frac{1}{2} + \frac{(7 + 4\sqrt{3})^n}{4} + \frac{(7 - 4\sqrt{3})^n}{4}$$
Simplifying, we get:
$$a_n = \left( (2 + \sqrt{3})^n + (2 - \sqrt{3})^n \right)^2 \cdot \frac{1}{4}$$

7. **Prove $a_n$ is a perfect square:**
Notice that:
$$a_n = \left( (2 + \sqrt{3})^n + (2 - \sqrt{3})^n \right)^2$$
Since $(2 + \sqrt{3})^n + (2 - \sqrt{3})^n$ is an integer for all $n$, $a_n$ is a perfect square.

$\blacksquare$