Answer : $ n=2^l-1$ Induction !

Proposed by Niranjan Balachandran, SS Krishnan, and Prithwijit De.

$2^n$ - 1

Consider the sequence $b_n=2n-a_n$.

solved in contest

Simple strong induction to show (observable) n < an <= 2an which does the trick and the equality case is the easier part of the problem when 2^k - 1. n= 2^l-1 works which is also doable with induction. Losing marks (maybe) on missing the basic equality case (just induct lil bro) makes me wanna kms

Posting for storage.

Easy peasy, firstly you can see that $a_{2k}$ is odd. Now calculate some values for $a_{2k+1}$ you can see that for $2^p - 1$ type numbers $\frac{a_n}{n}$ is an integer. Then just simple induction proves the result.

Pls check this solution We first show a((2^n)-1)=(2^(n+1))-2 by induction. Then we show a(2^n)=(2^(n+1)-1) again by induction Then we show a((2^n)+(2^(n-1))-1)=(2^(n+1))+(2^(n-1))-2 Then we show that a(n+1)-an=1 or 3 And using all three claims we show that m=2^n -1 are the only solutions. My idea is that the difference pattern goes like 1,3,1,1,3,3,1,1,1,1,3,3,3,3 in powers of 2.

I did it like this in exam: Like i first proved a_odd is even,a_even is odd Proof by induction Then i proved a(2^x-1)=2(2^x-1) satisfies Proof by induction Then i proved a(n)>n Proof by induction Then i proved a(n)≤2n where equality hold when n=2^x-1 Proof by induction And done

WhT do u guys think about cutoff

The only problem in exam that can take atmost 30 mins.

Can anyone solve that problem without the 2? Let me rewrite Consider the sequence defined by \(a_1 = 2\), \(a_2 = 3\), and \[ a_{2k+1} = 2 + a_k, \quad a_{2k+2} = 2 + a_k + a_{k+1}, \]for all integers \(k \geq 1\). Determine all positive integers \(n\) such that \[ \frac{a_n}{n} \]is an integer. Edit: Actually I misread the problem statement and tried that problem instead for some times and couldn’t get how to prove that 2k+2 doesn’t divide (a_(2k+2)) and I even dont know if this claim is true. And I got a lot of bounding for other cases

GMMeowChand wrote: Can anyone solve that problem without the 2? Let me rewrite Consider the sequence defined by \(a_1 = 2\), \(a_2 = 3\), and \[ a_{2k+1} = 2 + a_k, \quad a_{2k+2} = 2 + a_k + a_{k+1}, \]for all integers \(k \geq 1\). Determine all positive integers \(n\) such that \[ \frac{a_n}{n} \]is an integer. Edit: Actually I misread the problem statement and tried that problem instead for some times and couldn’t get how to prove that 2k+2 doesn’t divide (a_(2k+2)) and I even dont know if this claim is true. And I got a lot of bounding for other cases I am hacking this idea from other post above of this problem or this particular thread. (No Offense Lol!!!) Show that $\frac{a_n}{n}\leq 2$ for all $n$ , then only possible integer solution for $a_n$ is $n$ or $2n$. I think this is the shorter way to kill your problem and also the original problem. BTW the bound I wrote for $\frac{a_n}{n}$ is obvious , due to the solution present by others, also values of new sequence you give will be smaller than or equal to the original sequence.

Safal wrote: $\text{Also a small comment:}$ Hatt's off to the proposer of Problem 6 in INMO 2025. The only problem I fail to solve in the whole paper. I was near but didn't observe certain things. I only solved the case when $b=2$ but couldn't go further and finally saw the solution in aops. Fr p6 is an amazing problem, tho personally I think solving the reformulated version of the problem is doable and getting to the reformulated version from the original problem is kinda hard.

We claim that the answer is all positive integers of the form $n=2^r-1$ for all $r \ge 1$. The following is the key claim. Claim : For all positive integers $n$, \[n<a_n \le 2n\] Proof : We show this via induction. When $n=1,2$ trivially, $1<a_1 \le 2$ and $2<a_2\le 4$ so the base cases are clear. Now, say the claim holds for all $1\le n \le 2k$ for some $k \ge 1$. Then, \[2k+1 < 2+2k<2+2a_k=a_{2k+1} = 2+2a_k \le 2+2(2k)=2(2k+1)\]with equality on the upper bound if and only if $a_k=2k$. Similarly, \[2k+2 < 2+k + (k+1) < 2 + a_k + a_{k+1} = a_{2k+2} = 2 + a_k + a_{k+1} \le 2+2k + 2(k+1)= 2(2k+2)\]with equality on the upper bound if and only if $a_k=2k$ and $a_{k+1}=2(k+1)$. Now, if $\frac{a_n}{n}$ is an integer, the claim implies that we require $a_n = 2n$. Now, consider the minimal even $n>2$ such that $a_n =2n$. As a result of the equality condition noted above, we require $a_{\frac{n-2}{2}}=n-2$ and $a_{\frac{n-2}{2}+1}=n$ (since $n>2$ both of these are indeed valid terms). But these are consecutive terms, so one of them must have an even index. But since \[\frac{n-2}{2} < \frac{n-2}{2}+1 < n\]for all $n>2$, this implies that there exists a smaller even indexed term $a_m=2m$ which is a contradiction. Thus, for all even $n$ , $\frac{a_n}{n}$ is not an integer. For odd $n$, $a_n=2n$ if and only if $a_{\frac{n-1}{2}}=n-1$ as a result of the equality condition. We again resort to induction. Say the only integers $n \le 2^k-1$ for some $k\ge 1$ such that $a_n=2n$ are those of the form $n=2^r-1$ for $1 \le r \le k$. Then, for $2^k -1 < n \le 2^{k+1} -1$, $a_n=2n$ if and only if $a_{\frac{n-1}{2}}=n-1$. But, \[2^{k-1}-1=\frac{2^k -2}{2}<\frac{n-1}{2} \le \frac{2^{k+1}-2}{2}=2^k -1\]and the only such term in this range is $a_{2^k-1}$ by assumption. Thus, the only such term in the range $2^k -1 < n \le 2^{k+1} -1$ is $a_{2^{k+1}-1}=2^{k+2}-2$ which completes the induction.

OG! \paragraph{¶ Solution:} We claim the answer is all $n=2^x-1$ for some positive integer $x$. We have the following main claim: \begin{myclaim} $n < a_n\leq 2n$ for all positive integers $n$ \end{myclaim} Proof: We use strong induction on $n$ $n=1,2$, the claim holds true, Assume the claim is true for $n=k$ where $k\geq 2$. If $k$ is odd then, $$k<k+1=2+2(\frac{k-1}{2})<2+2a_{\frac{k-1}{2}}=a_k\leq 2+2(k-1)=2k$$by our inductive hypothesis If $k$ is even then, $$k<k+1=2+\frac{k-2}{2}+\frac{k}{2})<a_k=2+a_{\frac{k-2}{2}}+a_{\frac{k}{2}}\leq 2+k-2+k=2k$$\hline Now, $n|a_n$ $\implies$ $a_n=2n$. Now we have the following claim: \begin{myclaim} $a_n=2n \implies n=2^x-1$ for some positive integer $x$. \end{myclaim} Proof: \begin{OGmysubclaim} $a_n$ is even if $n$ is odd and odd if $n$ is even. \end{OGmysubclaim} Proof: We use strong induction on $n$, with the base case $n=1,2$ being obvious. If $n$ is odd, then $a_n=2(1+a_{\frac{n-1}{2}})$is even. If $n$ is even then $ a_n =2+a_{\frac{n}{2}}+a_{\frac{n+2}{2}}$. $\frac{n+2}{2}-\frac{n}{2}=1$, so one of $\frac{n+2}{2},\frac{n}{2}=1$ is even and other is odd, so by our inductive hypothesis, one of $a_{\frac{n}{2}},a_{\frac{n+2}{2}}$ is odd and the other is even. $$ a_n \equiv 2+a_{\frac{n}{2}}+a_{\frac{n+2}{2}} \equiv 2+0+1 \equiv 1 \pmod2$$. Hence our induction is complete. Call $n$ a good integer if and only if $a_n=2n$. It is clear that $n|a_n$ if and only if $n$ is good. Since $a_n$ is even, $n$ is odd, so... $a_n=2n=2+2a_{\frac{n-1}{2}} \iff a_{\frac{n-1}{2}}=n-1= 2(\frac{n-1}{2})$ Hence $n$ is good if and only if $n$ is odd and $\frac{n-1}{2}$ is good. Let $f(n)= \frac{n-1}{2}$ Let $\underbrace{f(f(f(.....(f(x)))...)}_{k-times} = f^k(x)$. We define $f^0(n)=n$ Consider a good integer $n$, so $f(n)$ must be good, similarly $f(f(n))$ must also be good and so on....... We have that $f(n)<n$ for all $n>1$. Consider the infinite sequence ... $$n,f(n),f(f(n)),f(f(f(n))) \cdots.... $$. If none of the terms in the sequence were 1, then we would have a infinte decreasing sequence of positive integers which is impossible. Hence, we must have a $k$ such that $f^k(n)=1$ \begin{OGmysubclaim} $f^k(n)=\frac{n-2^{k}+1}{2^{k}}$ \end{OGmysubclaim} Proof: Induction on $k$, base case $k=1$ is clear by definition of $f(x)$. Assume it is true for some $k$, then $f^{k+1}(n)=f(f^k(n))=\frac{\frac{n-2^{k}+1}{2^{k}}-1}{2}=\frac{n-2^{k+1}+1}{2^{k+1}}$. Hence our induction is complete. Since we have $f^k(n)=1$, so $\frac{n-2^{k}+1}{2^{k}}=1$, hence $n=2^{k+1}-1$ as desired, so our claim is proved. \hline Hence only integers of the form $n=2^x -1$ work. Now it remains to show that all such integers work, we proceed with the following claim, \begin{myclaim} $a_{2^x-1}=2(2^x-1)$ for all positive integers $x$ \end{myclaim} we use induction on $x$. Base Case: $x=1$, it is trivial that $a_1=2$. Inductive step: assume the claim is true for all $x$ in $[1,i]$. For $x=i+1$, $$a_{2^{i+1}-1}=2+2a_{2^i-1}=2+2(2)(2^i-1)=2(2^{i+1}-1)$$by our hypothesis. Hence we proved the claim. So $2^x-1|a_{2^x-1}=2(2^x-1)$. Hence, we are done. \begin{OGOG} Thhis problem is a perfect example of induction-bash. Other solutions that do not use such rigorous induction tend to miss minor or major details or cases. \end{OGOG}

Safal wrote: GMMeowChand wrote: Can anyone solve that problem without the 2? Let me rewrite Consider the sequence defined by \(a_1 = 2\), \(a_2 = 3\), and \[ a_{2k+1} = 2 + a_k, \quad a_{2k+2} = 2 + a_k + a_{k+1}, \]for all integers \(k \geq 1\). Determine all positive integers \(n\) such that \[ \frac{a_n}{n} \]is an integer. Edit: Actually I misread the problem statement and tried that problem instead for some times and couldn’t get how to prove that 2k+2 doesn’t divide (a_(2k+2)) and I even dont know if this claim is true. And I got a lot of bounding for other cases I am hacking this idea from other post above of this problem or this particular thread. (No Offense Lol!!!) Show that $\frac{a_n}{n}\leq 2$ for all $n$ , then only possible integer solution for $a_n$ is $n$ or $2n$. I think this is the shorter way to kill your problem and also the original problem. BTW the bound I wrote for $\frac{a_n}{n}$ is obvious , due to the solution present by others, also values of new sequence you give will be smaller than or equal to the original sequence. Actually i have got that like i got $a_{2k+1}<2k+1$ for some bigger k and the k is not that much big and $a_{2k+2}<4k+4$ so the only thing that I have to care is that $2k+2=a_{2k+2}$ and yeah that's the place where I stuck how to prove if that is true or false. If it is false then how can I get to the contradiction

I got it right but afraid of losing some marks. In the claim of even n not being a solution I used descent but mistakenly wrote (infinite descent). A little tensed.

It was a pain to write this up in-contest, but fortunately no one is going to dock me for less details here