For $a,b\in\mathbb{N}$, it is well known that $2^a+1|2^{ab}+1$ if $2\not|b$, and that $2^a-1|2^{ab}-1$. We will prove the result by induction. Note that $\nu_2(a_i)=1$, so $\frac{a_{n-1}}{a_{n-2}}$ is odd. Also, note that $a_1|a_2$, as $2|6$, and $a_2|a_3$, as $6|66$. $a_n|a_{n+1}\Longleftrightarrow 2^{a_{n-1}-1}+1|2^{a_n-1}+1 \Longleftarrow a_{n-1}-1|a_n-1 \Longleftrightarrow 2^{a_{n-2}}+1|2^{a_{n-1}}+1 \Longleftarrow a_{n-2}|a_{n-1}$ Thus $a_{n-2}|a_{n-1}\implies a_n|a_{n+1}$, and starting with either $a_1|a_2$ or $a_2|a_3$, we can prove by induction that $a_i|a_{i+1}$ for all $i\in\mathbb{N}$.

I hope it's right.

(This is pretty much the same as Flake's, but might as well post my solution for a slightly different viewpoint....)

I missed 2 points because I didn't clarify that $b$ had to be odd in Flake's "well known" fact Merp. 21--->19

As an interesting sidenote, this problem came out of a failed attempt to solve a troll APMO 1997 problem.

This is my solution . It is basically the same as MSTang. $a_n|a_{n+1}\Longleftrightarrow a_n|2^{a_n}+2\Longleftrightarrow 2^{a_n-1}+2|2^{2^{a_{n-1}}+2}+2\Longleftrightarrow a_{n-1}|2^{a_{n-1}}$+ & $\frac{2^{a_{n-1}}+2}{a_{n-1}}$ is odd $\Longleftrightarrow a_{n-1}|a_{n}$ and $\frac{a_{n}}{a_{n-1}}$ is odd. See that $\nu_2(a_i)=1$ . This proves the oddness of the quotient. The remaining can be done by induction as we now only have to show $a_n|a_{n+1}\Longleftrightarrow a_{n-1}|a_{n}$.This can be done by inducting downward on $n$.

Wolstenholme wrote: As an interesting sidenote, this problem came out of a failed attempt to solve a troll APMO 1997 problem. That's exactly what I thought when I first saw the problem! I was like, isn't that related to that annoying $n | 2^n + 2$ APMO problem that I spent hours on before finally finding a terribly unsatisfying bashy solution to arrive at $n=946$?

It was just a direct application of the lemma $2^m+1 | 2^n+1$ iff $m|n$ & $\frac{n}{m}$ is odd......along with induction........

My solution: Lemma 1: Let $a,b$ be integers such that $2^a+1|2^b+1$. Now we have $2^a+1|2^a(2^{b-a}-1)$ $\implies$ $2^a+1|2^{b-2a}+1$ so if $b=ka+r$ where $a>r\ge 0$ we have $2^a+1|2^r+1$ or $2^a+1|2^r-1$ since $2^a+1>2^r+1$ we have $2^a+1|2^r-1$ so $r=0$ so $2^a+1|2^b+1$ $\longleftrightarrow$ $a=kb$ and $k$ odd. Now consider sequence, and induct on $n$: $b_n=\frac{a_n}{2}$ which is $b_{n+1}=2^{2b_n-1}+1$. Now that $a_k|a_j$$\longleftrightarrow$ $b_k|b_j$. Now We have $b_n|b_{n+1}$ is equivalent to by Lemma 1 $2b_{n-1}-1|2b_n-1$ and obvious $k$ here is odd. But$2^{a_{n-2}}+1=a_{n-1}-1=2b_{n-1}-1|2b_n-1=a_n-1=2^{a_{n-1}}+1$ which is by Lemma 1 equivalent to $a_{n-2}|a_{n-1}$ and that $k$ here is odd which is by Induction hypothesis true since $a_1|a_2|a_3$.

@jashblued take x = 3, y = 6 and a =2

Just curious, why is this an A1 (and not, say, an N1)?

ELMO has somewhat higher standards for a problem to be classified as N, you need to actually do some nontrivial number theory (e.g. use the word "prime" in a non-stupid way). This problem doesn't; it's a recurrence that happens to use the word "divides".

Show $a_{n-1}-1|a_n-1$ by inductions and Lemma let $a,b$ be odds , $2^a+1|2^b+1$ if only if $a|b$. So $2^{a_{n-1}-1}+1|2^{a_n-1}+1 -> a_n|a_{n+1}$

We will prove this result by strong induction. For the base case, we can easily find that $a_1=2, a_2=6$ and $a_3=66$. Since $2|6$ and $6|66$, this is true. Now suppose that $a_{i-1}|a_i$ for all of $i = 2,3,...,k$. Clearly $\tfrac{a_i}{a_{i-1}}$ is odd since $a_i$ and $a_{i-1}$ are both $2\pmod{4}$. Thus if $a_{k-2}|a_{k-1}$, then $$2^{a_{k-2}}+1|2^{a_{k-1}}+1.$$We know that $2^{a_{k-2}}+2=a_{k-1}$ and $2^{a_{k-1}}+2=a_k$ so our condition is equivalent to $$a_{k-1}-1|a_k-1.$$Using this, we have that $$2^{a_{k-1}-1}+1|2^{a_k-1}+1.$$Multiplying by $2$, we get $$a_k|a_{k+1}.$$Thus, our induction is complete.

Solved with rama1728 We use induction on $n$. Base cases are $a_1=2, a_2=6, a_3=66$. Suppose it is true for everything up to $k$ (as in $a_{k-1}\mid a_k, a_{k-2}\mid a_{k-1},\ldots$) We want to show that $a_{k}\mid a_{k+1}$, or equivalently \[2^{a_{k-1}}+2\mid 2^{a_k}+2\iff 2^{a_{k-1}-1}+1\mid 2^{a_k-1}+1\] Since both $a_{k-1}-1$ and $a_k-1$ are odd, it suffices to show that $a_{k-1}-1\mid a_k-1$. Now, \[a_{k-1}-1=2^{a_{k-2}}+1 \text{ and }a_k-1=2^{a_{k-1}}+1\] By the induction hypothesis, $a_{k-2}\mid a_{k-1}$. $a_{k-2}\equiv a_{k-1}\equiv 2\pmod 4$, $\frac{a_{k-2}}{a_{k-1}}$ is odd. Thus, \[2^{a_{k-2}}+1\mid 2^{a_{k-1}}+1\implies a_{k-1}-1\mid a_k-1,\]as desired.

megarnie wrote: Solved with rama1728 We use induction on $n$. Base cases are $a_1=2, a_2=6, a_3=66$. Suppose it is true for everything up to $k$ (as in $a_{k-1}\mid a_k, a_{k-2}\mid a_{k-1},\ldots$) We want to show that $a_{k}\mid a_{k+1}$, or equivalently \[2^{a_{k-1}}+2\mid 2^{a_k}+2\iff 2^{a_{k-1}-1}+1\mid 2^{a_k-1}+1\] Since both $a_{k-1}-1$ and $a_k-1$ are odd, it suffices to show that $a_{k-1}-1\mid a_k-1$. Now, \[a_{k-1}-1=2^{a_{k-2}}+1 \text{ and }a_k-1=2^{a_{k-1}}+1\] By the induction hypothesis, $a_{k-2}\mid a_{k-1}$. $a_{k-2}\equiv a_{k-1}\equiv 2\pmod 4$, $\frac{a_{k-2}}{a_{k-1}}$ is odd. Thus, \[2^{a_{k-2}}+1\mid 2^{a_{k-1}}+1\implies a_{k-1}-1\mid a_k-1,\]as desired. wait can i group solve with you guys

pi271828 wrote: megarnie wrote: Solved with rama1728 We use induction on $n$. Base cases are $a_1=2, a_2=6, a_3=66$. Suppose it is true for everything up to $k$ (as in $a_{k-1}\mid a_k, a_{k-2}\mid a_{k-1},\ldots$) We want to show that $a_{k}\mid a_{k+1}$, or equivalently \[2^{a_{k-1}}+2\mid 2^{a_k}+2\iff 2^{a_{k-1}-1}+1\mid 2^{a_k-1}+1\] Since both $a_{k-1}-1$ and $a_k-1$ are odd, it suffices to show that $a_{k-1}-1\mid a_k-1$. Now, \[a_{k-1}-1=2^{a_{k-2}}+1 \text{ and }a_k-1=2^{a_{k-1}}+1\] By the induction hypothesis, $a_{k-2}\mid a_{k-1}$. $a_{k-2}\equiv a_{k-1}\equiv 2\pmod 4$, $\frac{a_{k-2}}{a_{k-1}}$ is odd. Thus, \[2^{a_{k-2}}+1\mid 2^{a_{k-1}}+1\implies a_{k-1}-1\mid a_k-1,\]as desired. wait can i group solve with you guys if rama1728 is okay with it

pi271828 wrote: megarnie wrote: Solved with rama1728 We use induction on $n$. Base cases are $a_1=2, a_2=6, a_3=66$. Suppose it is true for everything up to $k$ (as in $a_{k-1}\mid a_k, a_{k-2}\mid a_{k-1},\ldots$) We want to show that $a_{k}\mid a_{k+1}$, or equivalently \[2^{a_{k-1}}+2\mid 2^{a_k}+2\iff 2^{a_{k-1}-1}+1\mid 2^{a_k-1}+1\] Since both $a_{k-1}-1$ and $a_k-1$ are odd, it suffices to show that $a_{k-1}-1\mid a_k-1$. Now, \[a_{k-1}-1=2^{a_{k-2}}+1 \text{ and }a_k-1=2^{a_{k-1}}+1\] By the induction hypothesis, $a_{k-2}\mid a_{k-1}$. $a_{k-2}\equiv a_{k-1}\equiv 2\pmod 4$, $\frac{a_{k-2}}{a_{k-1}}$ is odd. Thus, \[2^{a_{k-2}}+1\mid 2^{a_{k-1}}+1\implies a_{k-1}-1\mid a_k-1,\]as desired. wait can i group solve with you guys sure

rama1728 wrote: pi271828 wrote: megarnie wrote: Solved with rama1728 We use induction on $n$. Base cases are $a_1=2, a_2=6, a_3=66$. Suppose it is true for everything up to $k$ (as in $a_{k-1}\mid a_k, a_{k-2}\mid a_{k-1},\ldots$) We want to show that $a_{k}\mid a_{k+1}$, or equivalently \[2^{a_{k-1}}+2\mid 2^{a_k}+2\iff 2^{a_{k-1}-1}+1\mid 2^{a_k-1}+1\] Since both $a_{k-1}-1$ and $a_k-1$ are odd, it suffices to show that $a_{k-1}-1\mid a_k-1$. Now, \[a_{k-1}-1=2^{a_{k-2}}+1 \text{ and }a_k-1=2^{a_{k-1}}+1\] By the induction hypothesis, $a_{k-2}\mid a_{k-1}$. $a_{k-2}\equiv a_{k-1}\equiv 2\pmod 4$, $\frac{a_{k-2}}{a_{k-1}}$ is odd. Thus, \[2^{a_{k-2}}+1\mid 2^{a_{k-1}}+1\implies a_{k-1}-1\mid a_k-1,\]as desired. wait can i group solve with you guys sure o poggers

Edit:-Finally!!!!!! 100 posts completed!!Let's gooo!

Call $P(n)$ the statement $a_{n-1} \mid a_n$ and $Q(n)$ the statement $a_{n-1}-1 \mid a_n-1$. We will induct on $n$ to show both are true, base cases easy. Assume $P(n-1)$ and $Q(n-1)$ are true. We will show $P(n)$ and $Q(n)$ are true from this information. If $x=a_{n-2}$, then $a_{n-1}=2^x+2$, so we know $x\mid 2^x+2$ and $x-1\mid 2^x+1$. First, we show $P(n)$, i.e. $2^x+2 \mid 2^{2^x+2}+2$. Since $x-1\mid 2^x+1$, taking both sides of $2^{x-1} \equiv -1 \pmod{2^{x-1}+1}$ to the power of the odd number $\tfrac{2^x+1}{x-1}$ (since numerator odd) gives $2^{2^x+1} \equiv -1 \pmod{2^{x-1}+1}$. Rewriting this, $2^x+2 \mid 2^{2^x+2}+2$, as needed. Next, we show $Q(n)$, i.e. $2^x+1 \mid 2^{2^x+2}+1$. Taking $2^x\equiv -1\pmod{2^x+1}$ to the power of $\tfrac{2^x+2}{x}$ (which is odd since $\nu_2(a_i)=1$ for all $i$, so $\nu_2(a_{i+1}/a_i)=0$) on both sides gives $2^{2^x+2} \equiv -1 \pmod{2^x+1}$. This rearranges to the desired. The induction is complete, so $P(n)$ is true for all $n$.

Let $P(n)$ be the statement "$a_{n-1} \mid a_n$" We're going to use strong induction on $n$ Basis step : Obviously, $P(2)$ and $P(3)$ are true. Inductive step : Assume $P(2),...,P(k)$ is true ; $k\geq 3$ We're going to prove that $P(k+1)$ is true. Observe that $\nu_2(a_i)=1$ for all $i$. Because $P(k-1)$ is true. So, $a_{k-2} \mid a_{k-1}$. $\implies 2^{a_{k-2}}+1\mid 2^{a_{k-1}}+1$ ($\nu_2(a_{k-1}/a_{k-2})=0$) $\implies a_{k-1} -1 \mid a_{k} -1$ and both are odd $\implies 2^{a_{k-1}-1}+1\mid 2^{a_{k}-1}+1$ $\implies 2^{a_{k-1}}+2\mid 2^{a_{k}}+2$ $\implies a_{k} \mid a_{k+1}$ $\implies$ $P(k+1)$ is true as desired $\blacksquare$

We will do strong induction $n\to n+2$ that $a_{n-1}\mid a_n$ with the base case $n=2,3$ being evident. Now, suppose that $a_{n-3}\mid a_{n-2}$. Note that $v_2(a_{n-3})=v_2(a_{n-2})=1$ so $a_{n-2}/a_{n-3}$ is an odd integer. $$2^{a_{n-2}}+1\equiv (2^{a_{n-3}})^{\frac{a_{n-2}}{a_{n-3}}}+1\equiv (-1)^{\frac{a_{n-2}}{a_{n-3}}}+1\equiv 0\pmod{2^{a_{n-3}}+1}$$Thus, $2^{a_{n-3}}+1\mid 2^{a_{n-2}}+1$ so $a_{n-2}-1\mid a_{n-1}-1$. Similarly, both $a_{n-1}-1$ and $a_{n-2}-1$ is positive integer so $(a_{n-1}-1)/(a_{n-2}-1)$ is an odd integer. We have $2^{a_{n-2}-1}+1\mid 2^{a_{n-3}-1}+1$. $$2^{a_{n-2}-1}+1\mid 2^{a_{n-3}-1}+1\implies 2^{a_{n-2}}+2\mid 2^{a_{n-3}}+2\implies a_{n-1}\mid a_n.$$This complete the induction, and we're done.

Wow. Nice problem Lemma (which I call the ascension trick): if $x$ and $y$ are positive integers such that $x|y$ and $y/x$ is odd, then $$2^x+1|2^y+1.$$This is simply due to the sum of odd powers factorization. Note that all terms of the sequence are 2 mod 4, so if $a_n|a_{n+1}$ then $a_{n+1}/a_n$ is odd. Claim: If $a_n|a_{n+1}$, then $a_{n+2}|a_{n+3}$. Let $a_n=m$. Then, $$m|2^m+2$$$$2^m+1|2^{2^m+2}+1 (\text{Ascension~trick~since~the~ratio~is~odd})$$$$2^{2^m+1}+1|2^{2^{2^m+2}+1}+1(\text{Ascension~trick~again},2^{2^m+2}+1\text{is~odd })$$$$2^{2^m+2}+2|2^{2^{2^m+2}+2}+2 \text{(2~times~previous)}$$$$a_{n+2}|a_{n+3}.$$ We have $a_1=2,a_2=6,a_3=66$, $a_1|a_2|a_3$, so by induction we are done. remark: motivation for the ascension trick was from like if you're trying to do induction, a way to exponentiate things and retain divsibility would be nice I think the tricky part (and the part that took me the longest) was realizing that I had to do the ascension trick twice, and I think the motivation for doing so was after getting $$2^m+1|2^{2^m+2}+1,$$it would really nice if you were allowed to add 1 to both, but of course divisibility doesn't work that way, so then I thought what if you exponentiated and then doubled (which is similar to adding 1 before) and then that works