If $a_1=a_2=a_3=1$ then if $n>3$ show that $2^{\gcd(a_{n-2},a_{n-3})}+a_{n-1}=2n-5.$

Question

Question: I write $a_1=a_2=a_3=1$ and set $a_n=2^{\gcd(a_{n-2},a_{n-3})}+a_{n-1}.$ For $n>3$ is it true and how can I show that $a_n=2n-5$ ? In particular I would like to show that that the sequence $\{a_n\}_{n=1}^\infty$ is the sequence $1,1,1,3,5,7,9,11,13,15,\ldots$

For example if $n=7$ then $a_7=2^{\gcd(a_5,a_4)}+a_6=2^{\gcd(3,5)}+2=2^1+7=9.$ And $2*7-5=14-5=9.$

Answer 1

We show that $$\gcd(a_n,a_{n-1})=1$$first notice that all the terms of the sequence are odd (because $2^{\gcd(a,b)}$ is always even and $a_1$ and $a_2$ are odd and non-zero) therefore $$\gcd(a_n,a_{n-1})=\gcd(2^{\gcd(a_{n-2},a_{n-3})}+a_{n-1},a_{n-1})=\gcd(2^{\gcd(a_{n-2},a_{n-3})},a_{n-1})=1$$since $2^{\gcd(a_{n-2},a_{n-3})}$ is a power of $2$ and has no odd component. Therefore $\gcd(a_n,a_{n-1})=1$ which leads to $$a_n=2+a_{n-1}$$or $$a_n=2n-5$$

Answer 2

@lulu per you comment (sort of) I have the following as a possible solution:

By definition $2^{\gcd(a_{n-2},a_{n-3})}+a_{n-1}=a_n$ and so $2^{\gcd(a_{n-2},a_{n-3})}=a_n-a_{n-1} $ for every $n$. I can take "logs" on the LHS and RHS of the equality to get $\gcd(a_{n-2},a_{n-3})\log2=\log(a_n-a_{n-1})$ consequently $$\gcd(a_{n-2},a_{n-3})={\log(a_n-a_{n-1})\above 1.5pt \log2}$$ If ${\log(a_n-a_{n-1})\above 1.5pt \log2}=2x$ for some $x\in \mathbb{N}$ then $\log(a_n-a_{n-1})=2x\log2$ and so $a_n-a_{n-1}=4^x$ which is a contradiction. So I must have ${\log(a_n-a_{n-1})\above 1.5pt \log2}=2x+1$ in which case $a_n-a_{n-1}=2^{2x+1}$ which is a contradiction for $x>1$. So $x=0$ and ${\log(a_n-a_{n-1})\above 1.5pt \log2}=1.$ By equality $\gcd(a_{n-2},a_{n-3})=1.$ So I have shown that $a_n=2+a_{n-1}.$ I know that $a_4=3$ and so I have shown that $\{a_n\}_{n=1}^\infty$ is the sequence $1,1,1,3,5,7,\ldots$ Now by recursion I have that

\begin{align} a_n&=2+a_{n-1}\\ &=2+2+a_{n-2}\\ &=2+2+2+a_{n-3}\\ &=\underbrace{2+2+2+\ldots+2}_{\text{$n-4$ } times}+1+1+1\\ &=2(n-4)+3\\ &=2n-5 \end{align}

Answer 3

Use induction and lulu's hint:

Base case: for $n = 4$ we have $a_4 =2^{\gcd a_2, a_3}+a_{n-1} = 2^{\gcd(1,1)} +1 = 3 = 2*4-5$

Induction step: Assume to for all $4\le = n\le k$. Then $\gcd (a_{k-1},a_{k-2})=$ either:

$\gcd(1,1) = 1$ if $k = 4$

$\gcd(1,3) = 1$ if $k = 5$

$\gcd(2(n-1)-5, 2(n-2)-5)= \gcd (2n-7, 2n -9)= \gcd(2n-7, (2n-9) - (2n-7)) = \gcd(2n-7, 2)=\gcd(2n-7-2n, 2)=\gcd(-7,2) =1$ if $k> 5$.

So $\gcd (a_{k-1},a_{k-2})=1$

So $a_{k+1} = 2^{\gcd (a_{k-1},a_{k-2})} + a_k$

$=2^1 + (2k -5)$

$= 2k - 3$

$= 2(k+1) -5$.

So it is true for $n = k+1$.

So by induction it is true for all natural numbers.