3

$a_{n+3}=15a_{n+2}-15a_{n+1}+a_n$, here $a_1=a_2=1,a_3=9$

Prove all numbers in a sequence are perfect squares.

My attempt is first to use the general formula of $a_n$.

It is $a_n=\frac{1}{6}\left((2+\sqrt3)^{2n-3}+(2-\sqrt3)^{2n-3}+2\right)$

But I still cannot prove every number in the sequence is a perfect square.

noname1014
  • 2,513
  • 3
    Needs more context, please provide and attach the source of this problem, thank you for finding the explicit form. Also see this for a similar question, maybe an educated guess using the explicit form might be useful. – Sarvesh Ravichandran Iyer Jan 27 '23 at 06:00

1 Answers1

9

Consider the sequence $(b_n)$ defined by

$$ b_{n+2} = 4b_{n+1} - b_n, \qquad b_1 = b_2 = 1. $$

It is clear that every term of $(b_n)$ is an integer. To prove the claim, it is thus sufficient to establish:

Claim. $a_n = b_n^2$ for all $n$.

Indeed, it is easy to check that the claim is true for $n = 1, 2, 3$. Now suppose the claim is true for $n$, $n+1$, $n+2$. Then

\begin{align*} a_{n+3} &= 15a_{n+2} - 15a_{n+1} + a_n \\ &= 15b_{n+2}^2 - 15b_{n+1}^2 + b_n^2 \\ &= 15b_{n+2}^2 - 15b_{n+1}^2 + (-b_{n+2} + 4b_{n+1})^2 \\ &= 16b_{n+2}^2 + b_{n+1}^2 - 8b_{n+1}b_{n+2} \\ &= (4b_{n+2} - b_{n+1})^2 \\ &= b_{n+3}^2, \end{align*}

and so, the claim is true for $n+3$ as well. Therefore the claim follows by the principle of mathematical induciton.

Motivation. The choice of the sequence $(b_n)$ is motivated by the fact that OP's formula for $(a_n)$ simplifies to

$$ a_{n} = \left[ \frac{\sqrt{3}-1}{2\sqrt{3}}(2+\sqrt{3})^{n-1} + \frac{\sqrt{3}+1}{2\sqrt{3}}(2 - \sqrt{3})^{n-1} \right]^2. $$

Using this, I reverse-engineered the recurrence relation with the characteristic equation having $2\pm\sqrt{3}$ as roots, namely $x^2 - 4x + 1 = 0$.

Angelo
  • 12,328
Sangchul Lee
  • 167,468