Question

Let $\left(a_n\right)n\ge 1$ be an increasing sequence of positive integers such that 1.$a_{2n}=a_n+n$ for all $n\ge 1$ 2.if $a_n$ is prime, then n is a prime. Prove that $a_n=n,$ for all $n\ge 1.$

• A. $n\ge 1.$
• B. $n\ne 1.$
• C. $n=1.$
• D. None of the above
  

Answer 1

The correct option is A $n\ge 1.$

Let $a_1=c$. Then $a_2=a_1+1=c+1$,$a_4=a_2+2=c+3$. Since the sequence is increasing,it follows that $a_3=c+2$. We Prove that $a_n=c+n1$ for all $n1$. Indeed, if $n=2k$ for some integer $k$ this follows by induction on $k$. Suppose that $a_{2^k}=c+2^{k}1$. Then $a_{2^{k+1}}=a_{{2.2}^k}=a_{2^k}+2^k=c+2^{k+1}1$. If $2^k<n<2^{k+1}$, then $c+2^{k}1=a_{2^k}<a_{2^k+1}<...<a_n<...<a_{2^k+1}=c+2^{k+1}1$ add this is possible only if $a_n=c+n1$.

Next we prove that $c=1$. Suppose that $c2$ and let $p<q$ be two consecutive prime numbers greater than $c$. We have $a_{qc+1}=c+qc=q$, hence $qc+1$ is a prime and clearly $qc+1p$. It follows that for any consecutive prime numbers $p<q$ we have $qc+1$. The numbers $(c+1)!+2,(c+1)!+\mathrm{3...},(c+1)!+c+1$ are all composite, hence if $p$ and $q$ are the consecutive primes such that $p<(c+1)!+2<(c+1)!+c+1<q$ then $qp>c1$, a contradiction. It follows that $c=0$ and $a_n=n$ for all $n1$.