Let $\{a_n\}_{n\geq 1}$ be a sequence with $a_1=1$, $a_2=4$ and for all $n>1$, \[ a_{n} = \sqrt{ a_{n-1}a_{n+1} + 1 } . \] a) Prove that all the terms of the sequence are positive integers. b) Prove that $2a_na_{n+1}+1$ is a perfect square for all positive integers $n$. Valentin Vornicu
Problem
Source: Romanian IMO TST 2006, day 2, problem 1
Tags: induction, quadratics, algebra, algebra proposed
Valentin Vornicu
22.04.2006 13:55
Okay first thing to admit is that this problem (point a) ) follows from one implication of BMO 1986 / problem 3. I found this out after creating the problem. Also point b) is rather similar with BMO 2002 / problem 2. However, given all these facts, the problem was still though enough for most of the students not to solve it or make mistakes at it.
Flatter
22.04.2006 15:31
The main idea to a) and b) is to find out that $a_{n+1}=4a_n-a_{n-1}$
jin
23.04.2006 11:51
Then we can prove $a_{n+1}^2-4a_{n+1}a_n+a_n^2=1$ by induction. So $2a_na_{n+1}+1=(a_{n+1}-a_n)^2$.is a perfect square.
bui_haiha2000
08.09.2006 19:03
Flatter wrote: The main idea to a) and b) is to find out that $a_{n+1}=4a_{n}-a_{n-1}$ How did you introduce this ? Please tell me ,Flatter or someone can help me this
Xixas
13.01.2007 21:23
My solution also uses several inductions: 1. By induction show that $a_{n-1}^{2}\equiv 1 \mod a_{n}$ and $a_{n}^{2}\equiv 1 \mod a_{n-1}$ simultaneously. Deduce a). 2. By induction show that $a_{n+1}=4a_{n}-a_{n-1}$ and $a_{n}^{2}=4a_{n}a_{n-1}-a_{n-1}^{2}+1$ simultaneously. Deduce b). I wonder how one comes up with such problems (a weird recurrence + initial terms = something is always integer/square)? Does it follow from some deeper theory which suggests more ingenious ways leading to soution than dumb induction (e.g. Pell equations or something)?
d.edgar
14.01.2007 10:50
Hi, Xixas! I didn't solve the problem in the contest, but after that I found something interesting: different types of recurrence relations that are in fact equivalent. (1) $x_{n}^{2}=x_{n-1}x_{n+1}+k$ (2) $x_{n+1}=2x_{n}+\sqrt{3x_{n}^{2}+k}\implies{x_{n+1}^{2}-4x_{n}x_{n+1}+x_{n}^{2}=k}$ (3) $x_{n+1}=4x_{n}-x_{n-1}$ In a contest you usually are given one of these recurrences, and must use the other . eg. prove that all of the terms of a type 1 or 2 recurrent sequence are integer. Here are the methods: (1)$\implies$(3): write (1) for $n,n+1$ substract, get ${\frac{x_{n}}{x_{n+1}+x_{n-1}}=constant}$. To determine the constant, use the initial conditions. (1)$\implies$(3): write (3) in the form ${\frac{x_{n}}{x_{n+1}+x_{n-1}}=4}$ so ${\frac{x_{n}}{x_{n+1}+x_{n-1}}=\frac{x_{n-1}}{x_{n}+x_{n-2}}}$ equivalent to $x_{n}^{2}-x_{n-1}x_{n+1}=constant$. (1)(3)$\implies$(2): substitute $x_{n+1}$ from (3) into (1). (2)$\implies$(1)(3): write (2) for $n,n+1$, consider it as a quadratic equation which roots are $x_{n+2},x_{n}$. Use Viete's relations.
quangminhltv99
22.04.2018 12:03
a) By calculating with small values, I claim that $a_{n+1}=4a_n-a_{n-1}$, then the statement trivially follows. I'll prove this by induction.
Base case: For $n=2$, $a_2^2=a_1\cdot a_3+1\implies a_3=15=4a_2-1.$
Inductive step: Assume that this holds for all positive integers less than or equal to $n$. Now, we first prove that for all postitive integers $n$, we have $a_{n+1}^2=4a_{n+1}a_n-a_n^2+1$ by... induction.
Base case: For $n=1$, we have $a_2^2=4=4\cdot 4\cdot 1-1+1$.
Inductive step: Assume that this holds for all positive integers less than or equal to $n$. Then
\begin{align*}
a_n^2&=4a_na_{n-1}-a_{n-1}^2+1\\
\iff 9a_n^2-6a_na_{n-1}+a_{n-1}^2&=8a_n^2-2a_na_{n-1}+1\\
\iff (3a_n-a_{n-1})^2&=2a_n(4a_n-a_{n-1})+1\\
\iff (a_{n+1}-a_n)^2&=2a_{n+1}a_n+1\\
\iff a_{n+1}^2&=4a_{n+1}a_n-a_n^2+1.
\end{align*}
Ok now let's prove $a_{n+2}=4a_{n+1}-a_{n}$. Indeed, we have
\begin{align*}
a_{n+1}^2-1&=a_na_{n+2}\\
\iff 4a_{n+1}a_n-a_n^2&=a_na_{n+2}\\
\iff a_{n+2}&=4a_{n+1}-a_{n}
\end{align*}Done.
b) Indeed, since $a_n^2=4a_na_{n-1}-a_{n-1}^2+1$, hence $2a_na_{n+1}+1=(a_{n+1}-a_n)^2$.