Consider the sequence $a_1 = 3$ and $a_{n + 1} =\frac{3a_n^2+1}{2}-a_n$ for $n = 1 ,2 ,...$. Prove that if $n$ is a power of $3$ then $n$ divides $a_n$ .
Problem
Source: 2010 Saudi Arabia IMO TST IV p3
Tags: recurrence relation, divides, number theory
28.12.2021 19:14
I wonder if $a_n=1, \forall n=1,2,...$ ?
28.12.2021 19:21
IMOStarter wrote: I wonder if $a_n=1, \forall n=1,2,...$ ? It seems so?
28.12.2021 19:26
parmenides51 wrote: Consider the sequence $a_1$ = 1 and $a_{n + 1} =\frac{3a_n^2+1}{2}-a_n$ for $n = 1 ,2 ,...$. Prove that if $n$ is a power of $3$ then $n$ divides $a_n$ . I could explain this because it's equivalent to $a_{n+1}-\frac 13=\frac 32 .(a_n-\frac 13 )^2 = (\frac 32)^{1+2^1}. (a_n -\frac 13)^{2^2}=...=(\frac 32)^{1+2^1+...+2^{n-2}} .(a_1-\frac 13)^{2^{n-1}}=(\frac 32)^{2^{n-1}-1}. (\frac 23)^{2^{n-1}} = \frac 23 \Rightarrow a_n =1 \forall n\geq 1$
28.12.2021 21:44
in the official solution $a_n$ is not constant
30.12.2021 19:31
parmenides51 wrote: in the official solution $a_n$ is not constant Could you attach said solution? I am curious if the provided problem in this thread is different.
30.12.2021 19:39
It looks like $a_1 = 3$ in this solution, which is strange. (From $x_1 = 8$, $x_n = 3a_n-1$) EDIT 2: The rest checks out. The last line should be
Very nice problem!
31.12.2021 06:20
Smileyklaws wrote: It looks like $a_1 = 3$ in this solution, which is strange. (From $x_1 = 8$, $x_n = 3a_n-1$) EDIT 2: The rest checks out. The last line should be
Very nice problem! I have the same idea by using LTE, at first I still curious why $a_n=1$. But it still a good problem btw P/s: I wonder if you have another solution without LTE, because it quite waste time to reprove the lemma in the competitions like national ones...
31.12.2021 07:34
Here $a_1=3$ becuase $a_1=1$ looks to be incorrect. First we will give this recurrence a better form so let $a_n=\frac{b_n}{3}$ and replacing we get $$a_{n+1}=\frac{3a_n^2+1}{2}-a_n \implies 2b_{n+1}=b_n^2+3-2b_n \implies 2(b_{n+1}-1)=(b_n-1)^2$$Now setting $b_n=c_n+1$ we get that $c_n^2=2c_{n+1}$ and now we show by induction that $c_n=2^{2^n+1}$ the base case is clear and now we begin with hypotesis, assume that it holds for $n=k$ then we show it for $n=k+1$ $$2^{2^{k+1}+2}=2c_{k+1} \implies c_{k+1}=2^{2^{k+1}+1}$$Meaning that $a_n=\frac{2^{2^n+1}+1}{3}$ using the previous definitions to get $a_n$. Now letting $n=3^k$ we are trying to show that $3^{k+1} \mid 2^{2^{3^k}+1}+1$ but by LTE $$v_3(2^{2^{3^k}+1}+1)=v_3(2^{3^k}+1)+1=k+2 \ge k+1=v_3(3^k)$$Hence we are done
31.12.2021 11:10
I am changing the condition $a_1=1$ to $a_1=3$ in order problem to be correct.