Oh, so this problem is the one like do you have enough terms or not? Suppose that for some $1\leq k\leq 3029$, we have $a_k$ is odd. Then, we get that \[a_{k+1}=\dfrac{a_k}{2}+2a_{k-1}\]so thus we have that $a_k$ is even in these cases. Now, consider $1\leq k\leq 3028$ and suppose $a_k$ is $2\pmod 4$. Then, we can get that \[a_{k+1}=\dfrac{a_k}{2}+2a_{k-1}\]which is odd, a contradiction. Thus, for all $1\leq k\leq 3028$, we have $4\mid a_k$. Now, consider the sequence $\{b_i\}_{i=0}^{3027}$ satisfying \[b_i=\dfrac{a_{i+1}}{4}\]This satisfies the same recurrence, so if we show that $2^k\mid b_i$ for some $i$, we get $2^{k+2}\mid a_{i+1}$ . Then, the problem is very easily trivialized by repeating this algorithm $1010$ times (in all) so that we get some $c_0$. Then, we get that we can iterate backwards to get $2020\mid a_k$ for some $k$. This can be formally written by considering arbitrary $a_0,\ldots,a_{3n}$ and then inducting.

Note: I originally made a mistake in this solution, fixing it pretty much makes it the same as solutions already presented, please ignore lol

adamisntdead wrote:

It's not necessarily true that $a_{3030}$ is a multiple of $4$, or even $2$. There aren't any restrictions on it.

Replace $1010$ by $N$ in the obvious way and proceed by induction on $N \ge 0$ with the base case $N = 0$ being vacuous. Notice that for any index $k \ne 0, 3N-1, 3N$ we have \[ a_k = 2a_{k+1} - 4a_{k-1} = 2(a_{k+2}-4a_k)-4a_{k-1} = 4(a_{k+2}-2a_k-a_{k-1}) \]so it follows that $(a_1, a_2, \dots, a_{3N-2})$ are all divisible by $4$ and satisfy the same relations. But then $(a_1/4, a_2/4, \dots, a_{3N-2}/4)$ has length $3(N-1)+1$ and so one of them is divisible by $4^{N-1}$; hence some term of our original sequence is divisible by $4^N$.

Suppose the contrary. Then there exists some integer $k$ between $0$ and $1009$ such that $\nu_2(a_{k+1}) - \nu_2(a_k) < 2$ (else $\nu_2(a_{1010})$ is at least $2\cdot 1010 = 2020$.) This means $\nu_2(a_{k+1}) < \nu_2(4a_k)$, and so \[ \nu_2(2a_{k+2}) = \min(\nu_2(a_{k+1}),\nu_2(4a_k)) = \nu_2(a_{k+1}), \]i.e. $\nu_2(a_{k+2}) = \nu_2(a_{k+1}) - 1$. Proceeding inductively, $\nu_2(a_{k+n+1}) = \nu_2(a_{k+1}) - n$ for all $n$. But then $a_{k+\nu_2(a_k)+1}$ is odd, and \[ k + \nu_2(a_k) < 1009 + 2020 = 3029. \]In particular, $a_{3030}$ is not an integer.

naman12 wrote: It's not necessarily true that $a_{3030}$ is a multiple of $4$, or even $2$. There aren't any restrictions on it. Yeah my bad my solution pretty much goes 'the wrong way' will fix

Now that Evan Chen has created EGMO (Euclidean Geometry for Mathematical Olympiads), it is hard to differentiate European Girls' Mathematical Olympiad and Evan Chen's EGMO.

lamphead wrote: Now that Evan Chen has created EGMO (Euclidean Geometry for Mathematical Olympiads), it is hard to differentiate European Girls' Mathematical Olympiad and Evan Chen's EGMO. I hope it is usually clear from context I had chosen the letters to acronym to GEOM, so I havea justification...

We prove the following claim through induction on $N\geq 0$. The problem is just $N=1010$. Claim: The positive integers $a_0, a_1, a_2, \ldots, a_{3N}$ satisfy$$2a_{n + 2} = a_{n+ 1} + 4a_n \text{ for } n = 0, 1, 2, \ldots, 3N-2.$$Prove that at least one of the numbers $a_0, a_1, a_2, \ldots, a_{3N}$ is divisible by $4^N$. Proof: The case $N=0$ is vacuous. Now we suppose that this is true for $N-1$ and prove that for $N$. We note the following two steps. Since $a_1 = 2(a_2-2a_0)$, $a_2=2(a_3-2a_1)$,...,$a_{3N-1} = 2(a_{3N}-2a_{3N-2})$ thus $a_1,a_2,\hdots,a_{3N-1}$ are all even. However, we get $a_i= 2a_{i+1}-4a_{i-1}$, both terms are divisible by $4$ when $i=1,2,\hdots,3N-2$.Thus $a_1,a_2,\hdots,a_{3N-2}$ are all divisible by $4$. Thus apply the induction hypothesis on $\tfrac{a_1}{4},\tfrac{a_2}{4},\hdots,\tfrac{a_{3N-2}}{4}$. In fact, we found that $2^{2N}\mid a_{N}$.

Let $ \nu_2(n) $ the exponent of 2 in the prime factorization of n and recurrence relation from statement be $ (P) $. Claim 1 : $ \nu _2(a_n)\ge1 \text{ for } n = 0, 1, 2, ..., 3029$ Proof: For $ n=0$ we get $ 2a_2-4a_0 =a_1 $ .Thus $ \nu_2(a_1)\ge 1$ . Easy we obtain $ \nu _2(a_n)\ge 1 \text{ for } n = 0, 1, 2, …3029$ (we make the remark that the initial number $n=3031 $ of number decrease with $2 $ ,more precisely after this step we will not work with $a_0$ and $a_{3030}$ ,the "extremely" numbers of the sequence Claim 2 : $ \nu _2(a_n)\ge 2 \text{ for } n = 0, 1, 2, …, 3028$. Proof:We make the substitution $a_{n}=2b_{n} $ for $ n=0,1,2,..,3029$.Then $ 2b_2-2a_0=b_1 $ which implies $\nu_2(b_1)\ge1 $,so $\nu_2(a_1)\ge2$ easily applying for all $ n=0,1,2,..,3027$ that $\nu_2(a_n)\ge2$ (we remark that the total number $n=3029$ decrease with $1$ at the right "extremely" number of the sequence) Thus,applying step $1$ and $2$ we obtain $\nu_2(a_1)\ge2 $.Inductevely,applying this algorithm results every sequence $a_k,a_{k+1},..,a_{3030-2k}$ has the exponent of $ 2$ is greater than or equal $ 2k $ Clearly, $k=1010 $ finishes this proof.

Can somebody please check my solution??

claim:For all $n=1,2,...3028$ We have $a_n$ even. proof: we have $2a_{n + 2}-4a_n = a_{n + 1}$ so we have $2|a_{n+1}$. Now As $2a_{n + 2} = a_{n + 1} + 4a_n$ we have $ min [\nu _2(a_{n+1}),2+\nu_2(a_n)]= 1+\nu_2(a_{n+2})$ which implies $\nu_2(a_{n+2})+1\le \nu _2(a_{n+1})$ Again,from $a_{n+2}-2a_{n}=\frac{a_{n+1}}{2}$ we have $\nu_2(a_{n+1})-1=min[\nu _2(a_{n+2}),\nu _2(a_{n})+1]\le \nu_2(a_{n+2})$. Together implies $\nu _2(a_{n+2})=\nu _2(a_{n+1})-1$. Now say $\nu _2(a_{n})= b_n$ so for $n=0,1,...3028$ we have $b_{n+2}=b_{n+1}-1$ and from the first claim $b_n\ge 1$.So we have inductively $1\le b_{2021} = b_1-2020$ so $b_1\ge 2020$. Ignore,wrong solution

This definitely isn't the easiest way to solve the problem, but I think this is different enough to be worth showcasing. Let $\alpha, \beta = \frac{1\pm\sqrt{33}}{4}$ be the roots of $2x^2-x-4$, so that $a_n=c_0\alpha^n+c_1\beta^n$ for some constants $c_0, c_1$. Note that $\alpha+\beta=\frac{1}{2}$ and $\alpha\beta=-2$. Lemma. Let $d$ be a positive integer and \[y=\alpha^d+\beta^d+k_1(\alpha^{d-1}\beta+\alpha\beta^{d-1})+\dotsb\]be a homogenous symmetric polynomial in $\alpha$ and $\beta$ with degree $d$, integer coefficients, and coefficient $1$ on $\alpha^d$. Then $y$ is rational and $\nu_2(y)=-d$.

Now, with \begin{align*} a_0 &= c_0+c_1 \\ a_{1010} &= c_0\alpha^{1010}+c_1\beta^{1010} \\ a_{3030} &= c_0\alpha^{3030}+c_1\beta^{3030} \end{align*}we can compute \[a_{1010}=\left[\frac{(\alpha\beta)^{1010}(\alpha^{1010}+\beta^{1010})}{\alpha^{2020}+\alpha^{1010}\beta^{1010}+\beta^{2020}}\right]a_0+\left[\frac{1}{\alpha^{2020}+\alpha^{1010}\beta^{1010}+\beta^{2020}}\right]a_{3030}.\]Replace $\alpha\beta$ by $-2$. By the lemma, each bracketed term is a rational number with $2$-valuation equal to $2020$. Therefore $\nu_2(a_{1010})\geq 2020$.

Posting for storage; solved with TheUltimate123 and eisirrational. We begin with the following claim. Claim. If $\nu_2(a_k) - \nu_2(a_{k-1}) < 2$, then $\nu_2(a_{k+1}) = \nu_2(a_{k}) - 1$. Proof. The condition implies $\nu_2(a_k) < \nu_2(4a_{k-1})$, and so their sum $\nu_2(a_k + 4a_{k-1}) = \nu_2(a_k)$ as desired. $\square$ Now let $d$ be the least integer for which $\nu_2(a_d) - \nu_2(a_{d-1}) < 2$. If $d > 1010$, then we are done as $\nu_2(a_{1010}) \geq 2 \cdot 1010 = 2020$. If $d \leq 1010$, then $\nu_2(a_{n+1}) = \nu_2(a_{n}) - 1$ for all $n \geq k$. In particular, $\nu_2(a_{3030}) = \nu_2(a_d) - (3030-d) \geq 0$ or $\nu_2(a_d) \geq 3030 - d \geq 2020$. We thus have the desired.

i think it's also true that $a_2020$ is divisible by 2^2020

g123678 wrote: i think it's also true that $a_2020$ is divisible by 2^2020 Not necessarily. There isn't a guarantee of symmetry.

So we divide the both sides by two and get that $a_{n+2}=\frac{1}{2}a_{n+1}+2a_n$ From here e clearly see that $a_{n+1}$ is even for $\forall n \in \{1,2,...,3029\}$ But let's claim that $a_{n} \equiv 2 (mod \;4)$. Then we would get that $a_{n+1} \equiv 1 + 2.2 \equiv 1 (mod \; 4)$, a contradiction!!! (if $n\in\{1,2,3,...,3028\}$) So now we got that $ 4 \mid a_n $ So we can express $a_n = 4t_n$, where $\{t\}_{i=1}^{3028}$ is a sequence of positive integers. So now we create an algorithm, where he will input our new sequnce, and do the same for $t_n$ as we did for $a_n$. The algorithm always creates a new sequence of positive integers after a finished cycles. We see that the algorithm always tightens the gap of allowed members in the new sequence by two. So now we see that the algorithm will always generate subsequences in $4^k\mathbb{Z}^+$, where $k$ denotes the current cycle of the algorithm , and the total number of cycles is 1009. But the total number of cycles is 1010, because we forgot to count in for the work we did for $a_n$, our starting sequence. So the we got that the minimum highest power of 2 that divides at least one element of the sequence $a_n$ is $2.1010=2020$. So we got that $\exists i \; s.t. \; 2^{2020} \mid a_i$, where $i \in \{0,1,....3030\}$.....

a1267ab wrote: This definitely isn't the easiest way to solve the problem, but I think this is different enough to be worth showcasing. Let $\alpha, \beta = \frac{1\pm\sqrt{33}}{4}$ be the roots of $2x^2-x-4$, so that $a_n=c_0\alpha^n+c_1\beta^n$ for some constants $c_0, c_1$. Note that $\alpha+\beta=\frac{1}{2}$ and $\alpha\beta=-2$. Lemma. Let $d$ be a positive integer and \[y=\alpha^d+\beta^d+k_1(\alpha^{d-1}\beta+\alpha\beta^{d-1})+\dotsb\]be a homogenous symmetric polynomial in $\alpha$ and $\beta$ with degree $d$, integer coefficients, and coefficient $1$ on $\alpha^d$. Then $y$ is rational and $\nu_2(y)=-d$.

Now, with \begin{align*} a_0 &= c_0+c_1 \\ a_{1010} &= c_0\alpha^{1010}+c_1\beta^{1010} \\ a_{3030} &= c_0\alpha^{3030}+c_1\beta^{3030} \end{align*}we can compute \[a_{1010}=\left[\frac{(\alpha\beta)^{1010}(\alpha^{1010}+\beta^{1010})}{\alpha^{2020}+\alpha^{1010}\beta^{1010}+\beta^{2020}}\right]a_0+\left[\frac{1}{\alpha^{2020}+\alpha^{1010}\beta^{1010}+\beta^{2020}}\right]a_{3030}.\]Replace $\alpha\beta$ by $-2$. By the lemma, each bracketed term is a rational number with $2$-valuation equal to $2020$. Therefore $\nu_2(a_{1010})\geq 2020$. could someone give me an article about the fundamentla theorem of symmetric polynomials

We proceed inductively; in particular, we show that one of the numbers $a_0, a_1, \cdots, a_{3n}$ is divisible by $2^{2n}$. To do so, observe that $2 \mid a_{3n-1}$, and $4 \mid a_i$ for $1 \leq i \leq 3n-2$ by repeatedly looking at the $\nu_2$ of both sides of the equation. However, by the inductive hypothesis, the sequence defined by $b_i = \frac{a_i}4$ for $1 \leq i \leq 3n-2$ contains a term divisible by $2^{2n-2}$ as it has $3n-2$ terms, so one of the $a_i = 4b_i$ is divisible by $2^{2n}$, as required.

EGMO 2020 P1. The positive integers $a_0, a_1, \dots, a_{3030}$ satisfy \[2a_{n+2}=a_{n+1}+4a_n\text{ for }n=0, 1, \dots, 3028.\]Prove that at least one of the numbers $a_0, a_1, \dots, a_{3030}$ is divisible by $2^{2020}$. Solution. We claim a claim that will imply the problem by substituting $N=1010$: Claim. For any integer $N\ge 0$, for positive integers $a_0, a_1, \dots, a_{3N}$ satisfying \[2a_{n+2}=a_{n+1}+4a_n\]for $n=0, 1, \dots, 3N-2$, at least one of $a_0, \dots, a_{3N}$ is divisible by $2^{2N}$. Proof. We proceed by induction on $N$. For $N=0$, it is trivial. Assume the claim is true for $N=M$ for some integer $M\ge 0$, i.e. for positive integers $a_0, a_1, \dots, a_{3M}$ satisfying $2a_{n+2}=a_{n+1}+4a_n$ for $n=0, 1, \dots, 3M-2$, at least one of $a_0, \dots, a_{3M}$ is divisible by $2^{2M}$. Now consider any positive integers $a_0, a_1, \dots, a_{3M+3}$ satisfying $2a_{n+2}=a_{n+1}+4a_n$ for $n=0, 1, \dots, 3M+1$. Then, \[\begin{cases}2a_2&=a_1+4a_0\\2a_3&=a_2+4a_1\\2a_4&=a_3+4a_2\\2a_5&=a_4+4a_3\\\dots\\2a_{3M}&=a_{3M-1}+4a_{3M-2}\\2a_{3M+1}&=a_{3M}+4a_{3M-1}\\2a_{3M+2}&=a_{3M+1}+4a_{3M}\\2a_{3M+3}&=a_{3M+2}+4a_{3M+1}\end{cases}.\]Note that $2\mid a_1, a_2, \dots, a_{3M+2}$, so we let $a_i=2b_i$, for $1\le i\le 3M+2$, where $b_i$ are integers for $1\le i\le 3M+2$. Then the system becomes \[\begin{cases}4b_2&=2b_1+4a_0\\4b_3&=2b_2+8b_1\\4b_4&=2b_3+8b_2\\4b_5&=2b_4+8b_3\\\dots\\4b_{3M}&=2b_{3M-1}+8b_{3M-2}\\4b_{3M+1}&=2b_{3M}+8b_{3M-1}\\4b_{3M+2}&=2b_{3M+1}+8b_{3M}\\2a_{3M+3}&=2b_{3M+2}+8b_{3M+1}\end{cases}.\]Equivalently, this is \[\begin{cases}2b_2&=b_1+2a_0\\2b_3&=b_2+4b_1\\2b_4&=b_3+4b_2\\2b_5&=b_4+b_3\\\dots\\2b_{3M}&=b_{3M-1}+4b_{3M-2}\\2b_{3M+1}&=b_{3M}+4b_{3M-1}\\2b_{3M+2}&=b_{3M+1}+4b_{3M}\\a_{3M+3}&=b_{3M+2}+4b_{3M+1}\end{cases}.\]Then we know that \[2\mid b_1, b_2, \dots, b_{3M+1}.\]Hence \[4\mid a_1, \dots, a_{3M+1}.\]Now note that the integers the $3M+1$ integers \[c_1=\frac{a_1}4, c_2=\frac{a_2}4, \dots, c_{3M+1}=\frac{a_{3M+1}}4\]also satisfy $2c_{n+2}=c_{n+1}+4c_n$ for $n=1, \dots, 3M-1$, so by induction hypothesis, at least one of $c_1, \dots, c_{3M-1}$ is divisible by $2^{2M}$, so at least one of $a_1, \dots, a_{3M-1}$ is divisible by $2^{2M+2}$, this completes the induction step. Remark 1. An alternative but less straightforward inductive step is to note that \[a_n=2a_{n+1}-4a_{n-1}=2(2a_{n+2}-4a_n)-4a_{n-1}=4(a_{n+2}-2a_n-a_{n-1})\]for any $1\le n\le 3M+1$ so $\frac{a_i}4$ is an integer for any $1\le n\le 3M+1$, from here we can apply the inductive hypothesis. Remark 2. In fact, it must follow that $2^{2N}\ge a_N$, and $a_N$ is the only number from $a_0$ to $a_{3N-2}$ whose $2$-adic valuation can be confirmed to be bounded below by $2N$. Actually, we can even show that \[\nu_2(a_n)\ge 2n\]for all $0\le n\le N$ and \[\nu_2(a_n)\ge 3M-n\]for all $N+1\le n\le 3M$. Furthermore, these bounds are the best possible in a sense that there exist $3M+1$ integers $a_0, \dots, a_{3M}$ such that some $\nu_2(a_n)$ is nothing higher than the prescribed lower bound.

We can see that $v_2(a_{n+2}) = \min(v_2(a_{n+1}), v_2(a_n) +2)$. Or we have that $v_2(a_{n+2}) \geq v_2(a_{n+1})$ if $v_2(a_{n+1}) + 2 = v_2(a_n)$. This means that the first time where we have $v_x +2 \neq v_{x-1}$. We have at most $v_x$ more integers in the sequence. This is because of our first identity. FTSOC, assume that we cannot. We can thus see that we have at most $1009$ terms on the ascent (we could have $0$ or something). We also have at most $2020$ terms on the descent. This gives $3029$ terms as the maximum. $\blacksquare$

Why can't I ever stop making sillies? Sometimes I just lose the motivation to live upto my goals and desire to give up everything but something still calls me back. Made my entire team shameful for the silly I made in a contest. Anyways, rants aside, here is the solution. I literally was stuck at the finish for $30$ minutes thinking $\nu_{2}(n)\ge k\implies n\ge 2k$ bruhh... Firstly if we have that $\nu_{2}(a_{n+1})\not=\nu_{2}(4a_n)$ for any $n\in\{0,1,\ldots,1009\}$ note that we will have $\nu_{2}(a_{n+2})=\min\{\nu_{2}(a_{n+1}),\nu_{2}(4a_n)\}-1\le\nu_{2}(a_{n+1})-1<\nu_{2}(a_{n+1})+2=\nu_{2}(4a_{n+1})$. So we won't have the equality in any of the further terms. So we can then have \begin{align*} 0&\le\nu_{2}(a_{3030})=\min\{\nu_{2}(a_{3029}),\nu_{2}(4a_{3028})\}-1\\ &\le\nu_{2}(a_{3029})-1=\min\{\nu_{2}(a_{3028}),\nu_{2}(4a_{3027})\}-2\\ &\le\nu_{2}(a_{3028})-2\\ &\le\cdots\\ &\le\nu_{2}(a_{n+1})-(3029-n) \end{align*}which then forces $\nu_{2}(a_{n+1})\ge 3029-n\ge 2020$. Now if the contrary happens that is $\nu_{2}(4a_n)=\nu_{2}(a_{n+1})$ for all $n\in\{0,1,\ldots,1009\}$, then we will have that $\nu_{2}(a_{1010})=\nu_{2}(a_{1009})+2=\cdots=\nu_{2}(a_0)+2\cdot 1010\ge 2020$ and we are done again.

Can somebody point out where is the mistake in this reasoning? The formula $2a_{n+2}=a_{n+1}+4a_n$ implies $a_n$ is even $\forall 1\le n\le 3029$ so for $1\le n\le 3029 $ let $a_n=2b_n$ then we get $2b_{n+2}=b_{n+1}+4b_n$ but that means $b_n$ is even $\forall 1\le n\le 3029$ so can’t we just keep going like that?

@above: djmathman wrote: That doesn't work because the sequence $(a_n)_{n\geq 0}$ is not infinite. More specifically, you claim that $2\mid a_n$ for all $n > 0$. But recall that the sequence is only defined up to $n = 3028$, so plugging in this value of $n$ yields $2\mid a_{3029}$, not $2\mid a_{3030}$. This means that $2\mid a_n$ for $n = 1,2,\ldots, 3029$. (In particular, $a_{3030}$ does not have to be even.) If my calculations are correct, the way that you extend this to higher powers of $2$ implies $4\mid a_n$ for $n = 2, 3,\ldots, 3028$, that $8\mid a_n$ for $n=3,4,\ldots, 3027$, and so on. You won't make it to $2020$ if you keep doing this.

hello , can anyone give me a source to learn about latex

$a_{n+2}=\frac{a_{n+1}}{2}+2a_n$. Since all $a_{n+2}$ are integers, $\nu_2(a_{n})\geq1$ and $2\mid{a_n}$ for all $1\leq{n}\leq3028$. Then, $\nu_2(a_{n})\geq2$ for $1\leq{n}\leq3027$. Suppose $\nu_2(a_{n})=1$ where $1\leq{n}\leq3027$, then $\frac{a_{n+1}}{2}$ is odd, making $a_{n+1}$ odd. From here, we can deduce that if $\nu_2(a_n), \nu_2(a_{n+1}), \nu_2(a_{n+2})\geq{x}$, then $\nu_2(\frac{a_{n+1}}{2})\geq{x} \Longrightarrow \nu_2(a_{n+1})\geq{x+1}$. Plugging $n=3025$ and $x=2$ from before, we get $\nu_2(a_n)\geq3$ where $1\leq{n}\leq3026$. Now it is clear that as we descent one term, we know that for all of the previous terms and itself $\min\nu_2(a_n)$ increases by one. This ascension is much greater than $2022$ so it guarantees that at least one of the numbers divides $2^{2020}$.

We will generalize the problem. Claim: If positive integers $a_0, a_1, a_2, \ldots, a_{3N}$ satisfy. \[2a_{n + 2} = a_{n + 1} + 4a_n \text{ for } n = 0, 1, 2, \ldots, 3N-2\] then at least one of the numbers $a_0, a_1, a_2, \ldots, a_{3N}$ is divisible by $4^N$. Proof: We will use proof by induction. The $N=0$ case is trivial, so we will suppose that our claim is correct up to $N=k-1$. We wish to prove that the claim still holds for $N=k$. Then, for any index $i$ from $1$ to $3k-1$, we have \[ a_i = 2a_{i+1} - 4a_{i-1} = 2(a_{i+2}-4a_i)-4a_{i-1} = 4(a_{i+2}-2a_i-a_{i-1}) \] meaning we can use the induction claim on $\left( \frac{a_1}{4}, \frac{a_2}{4}, \dots, \frac{a_{3N+2}}{4} \right)$ and one of them must be divisible by $4^{N-1}$, so one of the terms in our original sequence must be divisible by $4^N$. $\square$ The problem simply becomes plugging in $N=1010$ to our claim. $\square$

We claim that $v_{2}(a_{2020}) \geq 2020$. We prove this with the claim that \[v_{2}(a_{\lceil \frac{n}{2}\rceil}), v_{2}(a_{\lceil \frac{n}{2}\rceil+1}), \cdots, v_{2}(a_{3030-n}) \geq n\]Note when $n = 2020$, then we have that $v_{2}(a_{2020})\geq 2020$. We use induction. The base case of $n = 0$, is true because they're all integers. We assume that the property is true for all integers $\leq n$. Note that \[v_{2}(a_{k}) = v_{2}(2a_{k+1}-4a_{k-1}) \geq \min(v_{2}(a_{k+1}), v_{2}(a_{k-1}))+1\]We split this into two cases, $n$ even or $n$ odd. If $n$ even, then we have that \[v_{2}(a_{\frac{n}{2}+1}) \geq \min(v_{2}(a_{ \frac{n}{2}+2}), v_{2}(a_{\frac{n}{2}})+1)+1 \geq n + 1\]We can repeat this process until it works. If $n$ odd, then it's basically the same thing, but $a_{\lceil \frac{n}{2}\rceil} \geq n+1$. Thus, we are done.

Let $v_i$ denote $v_2 (a_i)$. If for some $n$, $v_2 \left( a_{n+1} \right) \neq v_2 \left( 4a_n \right)$, taking $v_2$ of our recurrence yields \[v_{n+2} = \min \left( v_{n+1} - 1, v_n + 1 \right) \leq v_{n+1}-1.\]So, $v_2 \left( a_{n+2} \right) \neq v_2 \left( 4a_{n+1} \right)$, and repeating the same reasoning inductively gives us that \[v_{n+1} \geq v_{3030} + 3029-n \geq 3029-n.\]So, if $v_2 \left( a_{n+1} \right) \neq v_2 \left( 4 a_n \right)$ for some $n \leq 1009$, we have $v_{n+1} \geq 2020$ and we are done. Otherwise, if $v_2 \left( a_{n+1} \right) = v_2 \left( 4a_n \right)$ for all $0 \leq n \leq 1009$, we are saying that \[v_{n+1} = v_n + 2\]for $0 \leq n \leq 1009$ which implies $v_{1010} = 2020+v_0 \geq 2020$ and we are done. (In particular, $a_{1010}$ is always a multiple of $2^{2020}$.)

Write $a_{n + 1} = a_{n + 1}/2 + 2a_n$, and define the sequence $(b_n)_{n \ge 0}$ as $b_n = \nu_2(a_n)$ for all $n$. Then it suffices to show that the difference between the maximum and minimum $b_i$ for $0 \le i \le 3030$ is at least $2020$. Also, we have $$b_{n + 2} \ge \min\{b_{n + 1} - 1, b_n + 1\},$$with equality only when $b_{n + 1} \neq b_n + 2$. If that is the case for any $n$, then after that point it's easy to see that $b_n$ will decrease by $1$ every time. Else, we have $b_{n + 2} \ge b_{n + 1} = b_n + 2$. Taking cases on $b_{n + 2}$, we find that: If $b_{n + 2} > b_{n + 1} + 2$, then $b_{n + 3} = b_{n + 1} + 1$ and $b_{n + 3}, b_{n + 4}, \ldots$ will be an arithmetic sequence with common difference $-1$ If $b_{n + 2} = b_{n + 1} + 2$, then $b_{n + 3} > b_{n + 2}$ If $b_{n + 2} < b_{n + 1} + 2$, then $b_{n + 3} = b_{n + 2} - 1 = b_{n + 1} - 3$ and $b_{n + 3}, b_{n + 4}, \ldots$ will be an arithmetic sequence with common difference $-1$ Let $k$ be the number of times that two consecutive $b_i$ differ by $2$. Then from the above, we can see that these pairs must be consecutive; that is, $b_0, b_1, \ldots, b_k$ will be an arithmetic sequence with common difference $2$. If $k \ge 1010$ then $b_{1010} \ge b_0 + 2020$, which implies the conclusion. Else, we can see that after $b_{1010}$, the $b_i$ will decrease by $1$ every time, so $b_{1010} \ge b_{3030} + 2020$, and we are done.

Solved with Om245

Claim ($\star$): For all positive integers $i \le 1010$, all the numbers $a_{i}, a_{i+1}, \dots, a_{3030-2i}$ are divisible by $4^i$. Proof: The proof is by induction. Base case($i = 1$): Analyse the given relation$\pmod{2}$. We get $a_{n +1} \equiv 0 \pmod{2}$ for $n = 0, 1, \dots, 3028$. Now analyse mod 4 to get $4 \mid a_{n+1}$ for $n = 0, 1, ..., 3027$, which is effectively the same as $a_1, a_2, \dots, a_{3028}$ all being divisible by 4 , which is what we had to prove. $\square$ Inductive step: Assume that $\star$ holds for $i = k$. We prove it holds for $i = k+1$. Define $b_n = \frac{a_{n-k}}{4^{k}} \iff a_n = 4^{k}b_{n+k}$ Observe that $b_n$ also satisfies the given relation, and in a similar manner to the base case, $4 \mid b_i \forall i \in \{ 1, \dots, 3028-3k\}$ $\implies 4^{k+1} \mid a_i \forall i \in \{ k+1, \dots, 3030 - 2(k+1) \}$, which is what we had to prove. $\square$ Now putting $i = 1010$ in $\star$, we get $4^{1010} = 2^{2020} \mid a_{1010}$, so we are done. $\square$ Remark: The problem holds if $3030$ be replaced by $3n$, and $2020$ by $2n$. In that case, $2^{2n} \mid a_n$.

We show that in the sequence $(a_1, a_2, \ldots, a_{3n})$, there exists some $a_i$ which is divisible by $2^{2n}$. Note that to finish from here, we just put $n=1010$. We proceed by using induction for $n\ge 2$. The case for $n = 2$ can be worked out by using $\pmod{16}$. Now we assume using the induction hypothesis that it holds true for $n$. We prove that the condition also holds true for $n+1$. Firstly, from the condition $2a_{n+2} = a_{n+1} + 4a_n$, it is easy to note that all the terms must be even except possibly the first and the last term of the sequence. We select the sequence $(a_2, a_3, \ldots, a_{3n-2})$. Note in this sequence, all the terms must be divisible by $2$. We divide all the terms by $2$. Also note that the equation $2\cdot\left(\dfrac{a_{n+2}}{2}\right) = \dfrac{a_{n+1}}{2} + 4\cdot\left(\dfrac{a_n}{2}\right)$ still holds. This gives us that $(\frac{a_2}{2}, \frac{a_3}{2}, \ldots, \frac{a_{3n-2}}{2})$ also satisfies the properties of the original sequence. This must mean that all the terms in this sequence except from $a_2$ and $a_{3n-2}$ must be multiples of $4$. But by using the same logic on the subsequence $(\frac{a_3}{2}, \frac{a_4}{2}, \ldots, \frac{a_{3n-1}}{2})$, we get that $a_{3n-2}$ is also a multiple of $4$. Now if $a_2$ is $\equiv 2 \pmod{4}$, then we get that $a_3 = \dfrac{a_2 + 4a_1}{2} = \dfrac{a_2}{2} + 2a_1$ which is odd which gives a contradiction since $a_3$ cannot be odd. Thus must mean that $a_2$ is divisible by $4$. Now to finish, we focus on the sequence $(a_2, a_3, \ldots, a_{3n-2})$. As we just found out that all the terms of the sequence are divisible by $4$, we get a new sequence by dividing all the terms by $4$, that is $b_i = \frac{a_i}{4}$. This gives us that the sequence $(b_2, b_3, \cdots, b_{3n-2})$ also follows the equation $2b_{n+2} = b_{n+1} + 4b_n$. This means that there is a term $b_i$ which is divisible by $2^{2n}$ which further means that $a_i$ is divisible by $2^{2n} \cdot 4 = 2^{2(n+1)}$ and are induction is complete.