\[ a_n=\sum_{k=0}^{[(n-1)/2]}C_n^{2k+1}2^k=n+2C_n^3+2^2C_n^5+...\] Therefore $ v_2(a_n)=v_2(n)$.

http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=325639&start=0&

Here is my solution: If we prove that: $\forall k\geqslant 2$, $\forall n\in\mathbb{N}$ $a_{n+2^k}-a_n\equiv 2^k \; mod(2^{k+1})$ Then we are done Let's prove this by induction: For $k=2$ we have to check that $a_{n+4}-a_n\equiv 4 \; mod(8)$. It is easily checked by calculating the sequence mod 8. Suppose it's true for $k$. Then we have: $a_{n+2^{k+1}}-a_{n}=(a_{n+2^{k+1}}-a_{n+2^{k+1}-2})+(a_{n+2^{k+1}-2}-a_{n+2^{k+1}-4})+\ldots+(a_{n+2}-a_n)$ $=2(a_{n+2^{k+1}-1}+a_{n+2^{k+1}-3}+\ldots+a_{n+1})$ By the induction hypothesis we have $a_{n+2^{k+1}-i}\equiv a_{n+2^k-i}+2^k \; mod(2^{k+1})$ for $1\leqslant i\leqslant 2^k-1$. And so we have: $a_{n+2^{k+1}}-a_{n}\equiv 2(2(a_{n+2^k-1}+a_{n+2^k-3}+\ldots+a_{n+1})+2^k\times 2^{k-1}) \; mod(2^{k+2})$ By the same manipulation that above we have: $2(a_{n+2^k-1}+a_{n+2^k-3}+\ldots+a_{n+1})=a_{n+2^k}-a_n$ Moreover, because $k\geqslant 2$, we have $2^{2k}\equiv 0 \; mod(2^{k+2})$. And so: $a_{n+2^{k+1}}-a_{n}\equiv 2(a_{n+2^k}-a_n) \; mod(2^{k+2})$ Again, by the induction hypothesis we have $a_{n+2^k}-a_n\equiv 2^k \; mod(2^{k+1})$, and we get the result.

First verify that $a_{2n+1} \equiv 1 \pmod{4}$ for all $n$. Now one can check by induction on $t \ge 0$ that $a_{n+t} = a_{t+1}a_n + a_ta_{n-1}$; in particular, $a_{2n} = a_n\left( a_{n+1} + a_{n-1} \right)$ and the conclusion is immediate.

v_Enhance wrote: First verify that $a_{2n+1} \equiv 1 \pmod{4}$ for all $n$. Now one can check by induction on $t \ge 0$ that $a_{n+t} = a_{t+1}a_n + a_ta_{n-1}$; in particular, $a_{2n} = a_n\left( a_{n+1} + a_{n-1} \right)$ and the conclusion is immediate. A constructive way of doing this(in fact this can be generalized): Consider the following two matrix \[A=\begin{pmatrix}2 & 1\\1 & 0\end{pmatrix},F_n=\begin{pmatrix}a_n\\a_{n-1}\end{pmatrix}\] Then, note the following: \[AF_n=\begin{pmatrix}2a_n+a_{n-1}\\a_n\end{pmatrix}=F_{n+1}\] Now, for a square matrix $A$, we know that, $A^{m+n}=A^mA^n$. So, applying this, we get the crucial equation. In this case, \[a_{m+n}=a_ma_{n+1}+a_{m-1}a_n\]

Rust wrote: \[ a_n=\sum_{k=0}^{[(n-1)/2]}C_n^{2k+1}2^k=n+2C_n^3+2^2C_n^5+...\] Therefore $ v_2(a_n)=v_2(n)$. After finding this expression for $a_n$, how does one prove $v_2(a_n)=v_2(n)$ ?

DoubleMint wrote: Rust wrote: \[ a_n=\sum_{k=0}^{[(n-1)/2]}C_n^{2k+1}2^k=n+2C_n^3+2^2C_n^5+...\] Therefore $ v_2(a_n)=v_2(n)$. After finding this expression for $a_n$, how does one prove $v_2(a_n)=v_2(n)$ ? Let $n=2^km,$ were m is odd. If $k=0$ $a_n$ odd too, and $v_2(a_n)=v_2(n)=0$. If $k=1$, then $v_2(a_n-n)\ge 2$, therefore $v_2(a_n)=v_2(n)=1.$ Let $k>1$, then for $1\le k$ $v_2(2^lC_n^{2l+1})=l+v_2(n)+(v_2(n-2)-v_2(2))+...(v_2(n-2l)-v_2(2l))\ge v_2(n)+l>v_2(n)$. For $l>k$ it is obviosly. Therefore always $v_2(a_n-n)>v_2(n)$ or $v_2(a_n)=v_2(n)$.

It also appeared in the INMO some year.This problem can be solved either by finding $a_n$ explicitly in terms of $n$ by the quadratic equation or by induction,though induction is more preferable.

This solution seems to be new. Because $a_0=0$, it suffices to show that $\{a_i\}$ is periodic $\pmod{2^k}$ with period $2^k$. However, we will prove a stronger result, which will prove some other facts about $\{a_i\}$ as well. Claim: $\{a_i\}$ is periodic $\pmod{2^k}$ with period $2^k$, and furthermore, $2^k$ fully divides $a_{2^k}$ (i.e. $\nu_2(a_{2^k}) = k$). $a_{2^k-1} \equiv 1 \pmod{2^k}$. Proof. We induct on $k$, $k=1$ being trivial. We wish to prove the result for $k+1$. Consider $\{a_i\} \pmod{2^k}$ instead. By induction, $a_{2^k-1} \equiv 1 \pmod{2^k}$ and $a_{2^k} \equiv 0 \pmod{2^k}$ (and in fact $2^k$ fully divides $a_{2^k}$). Hence, \[ a_{2^k+1} = 2a_{2^k} + a_{2^k-1} \equiv 1 \pmod{2^k}. \]Therefore, the sequence just repeats $\pmod{2^k}$, since now $(a_{2^k}, a_{2^k+1}) \equiv (0,1) \pmod{2^k}$. We have \[ (a_{2^k-1}, a_{2^k}, a_{2^k+1}) \equiv (1,0,1) \pmod{2^k}. \]But $a_{2^k} = 2^k(2a+1)$, and since the sequence repeated, $a_{2^{k+1}} - a_{2^k} \equiv a_{2^k} - a_0 = 2^k \pmod{2^{k+1}}$, so $a_{2^{k+1}} \equiv 2\cdot 2^k \equiv 0 \pmod{2^{k+1}}$, and in fact $2^{k+1}$ fully divides $a_{2^{k+1}}$ since we only got another factor of 2. So we have \[ (a_{2^{k+1}-1}, a_{2^{k+1}}, a_{2^{k+1}+1}) \equiv (1,0,1) \pmod{2^{k+1}}. \]This completes the induction. $\blacksquare$

orl wrote: An integer sequence is defined by \[{ a_n = 2 a_{n-1} + a_{n-2}}, \quad (n > 1), \quad a_0 = 0, a_1 = 1.\]Prove that $2^k$ divides $a_n$ if and only if $2^k$ divides $n$. Other idea: We write the characteristical equation: $r^2-2r-1=0$, and from here and the initial conditions we get: ${{a}_{n}}=\frac{1}{\sqrt{2}}\left( {{\left( 1+\sqrt{2} \right)}^{n}}-{{\left( 1-\sqrt{2} \right)}^{n}} \right)$, and maybe we can use the induction.

The characteristic equation $x^2 - 2x - 1 = 0$ has roots $1+\sqrt{2},1 - \sqrt{2}$. So for some constants $B,C$ we have $$a_n = B \cdot (1+\sqrt{2})^n + C \cdot (1 - \sqrt{2})^n ~~ \forall ~ n \ge 0$$Plugging in $n=0,1$ we get $B = -C = \frac{1}{2 \sqrt{2}}$. Hence, \begin{align*} a_n &= \frac{1}{2 \sqrt{2}} \left( (1 + \sqrt{2})^n - (1 - \sqrt{2})^n \right) = \frac{1}{2 \sqrt{2}} \left(2 \sum_{i \ge 0} (\sqrt{2})^{2i + 1} \binom{n}{2i+1} \right) = \sum_{i \ge 0} 2^i \binom{n}{2i + 1} \end{align*}Let $v_2(n) = k$. We want to show $v_2(a_n) = k$. Using Legendre's formula it is easy to get $2$-adic valuation of $\binom{n}{2i + 1}$ is $\ge k$ for all $i$. In particular $2^{k+1}$ divides $2^i \binom{n}{2i + 1} ~ \forall ~ i \ge 1$. Thus we get $$a_n \equiv 2^0 \cdot \binom{n}{2(0) + 1} = n \pmod{2^{k+1}}$$which completes the proof. $\blacksquare$

@above exactly my solution

Claim. For nonnegative integers $n,k$ holds $a_{n+k}=a_{k+1}a_n+a_ka_{n-1}$. Proof. Induct on $k;$ base case $k=0$ is obvious since $a_0=0.$ Next we perform an inductive step as follows $$a_{n+k+1}=a_{k+1}a_{n+1}+a_ka_n=2a_{k+1}a_n+a_{k+1}a_{n-1}+a_ka_n=a_{k+2}a_n+a_{k+1}a_{n-1}\quad \Box$$ By induction on integer $n\geq 0$ we trivially obtain $$a_{4n}\equiv 0 \pmod 4 \quad a_{4n+2}\equiv 2 \pmod 4 \quad a_{4n+1}\equiv a_{4n+3} \equiv 1\pmod 4.$$But from the claim we obtain $a_{2n}=a_n(a_{n+1}+a_{n-1}),$ so we easily obtain $v_2(a_m)=v_2(m)$ $\blacksquare$

Actually,this can be improved into $a_n=n(0\le n \le p-1),a_n=pa_{n+1-p}+a_{n-p}(n\ge p)$,then $v_p(n)=v_p(a_n)$

flower417477 wrote: Actually,this can be improved into $a_n=n(0\le n \le p-1),a_n=pa_{n+1-p}+a_{n-p}(n\ge p)$,then $v_p(n)=v_p(a_n)$ My friend told me about this,can anyone prove it?

any ideas?

Well,I've solved this one. Firstly, let $n=kp+m(0\le m\le p-1)$,so$a_n=pa_{(k-1)p+m+1}+a_{(k-1)p+m}=p(pa_{(k-1)p+m+2}+a_{(k-1)p+m+1)}+a_{(k-1)p+m+1}+a_{(k-1)p+m}$ $=\dots=\sum_{i=0}^kC_k^ip^{k-i}a_{m+k-i}$ When $m\neq 0$, by induction we can easily get the result $a_n \equiv n(mod\ p)$,which led to ${v_p(a_n)=v_p(n)=0}$ When $m=0$: $a_n=\sum_{i=0}^kC_k^ip^{k-i}a_{m+k-i}=\sum_{i=1}^kC_k^ip^ia_i$ If$v_p(C_k^ip^ia_i)\le v_p(n)(i>1)$ Using induction we assume that for any $1\le i\le k$ , we have $v_p(i)=v_p(a_i)$ Then it suffices to $v_p(\frac{(k-1)!}{(i-1)!(k-1)!})\le 1-i$ Which is $v_p(C_{k-1}^{i-1})\le 1-i<0$,which is wrong. As$v_p(C_k^1pa_1)=v_p(pk)=v_p(n)$ So we come to the conclusion $v_p(n)=v_p(a_n)$.

The characteristic polynomial of $a_n = 2a_{n-1} + a_{n-2}$ is $x^2 - 2x - 1 = 0$ which has roots $1 + \sqrt{2}$ and $1 - \sqrt 2$ and hence can be written as $\frac{1}{2\sqrt{2}} \cdot ((1 + \sqrt{2})^n - (1 - \sqrt{2})^n)$. By the Binomial theorem this can be written as \[\frac{1}{\sqrt{2}} \cdot \sum_{k} (\sqrt{2})^{2k - 1}\binom{n}{2k + 1} = 2^k\binom{n}{2k + 1}\]Then notice that the $\nu_2$ of this expression is at least $\min\{\nu_2(2^k\binom{n}{2k + 1})\}$ which occurs when $k = 0$, so $\nu_2(a_n) = \nu_2(n)$ as desired.

JAnatolGT_00 wrote: Same as yours.But I'm curious how you got to the last step directly?

It suffices to prove that $\nu_2(a_n) = \nu_2(n)$. We use the characteristic polynomial to find a closed form for $a_n$, which turns out to be \vspace{-0.25cm} \[a_n = \frac{1}{2\sqrt{2}} \left( (1+\sqrt{2})^n - (1-\sqrt{2})^n \right).\] We simplify this to \begin{align*} a_n &= \frac{1}{2\sqrt{2}} \left[ \sum_{i = 0}^n \binom{n}{i} (\sqrt{2})^i - \sum_{i = 0}^n \binom{n}{i} (-\sqrt{2})^i \right] \\ &= \frac{1}{2\sqrt{2}} \left[ \sum_{i = 0}^n \binom{n}{i} \left((\sqrt{2})^i - (-\sqrt{2})^i\right) \right] \\ &= \frac{1}{2\sqrt{2}} \left[\sum_{k=0}^{\lfloor \tfrac{n-1}{2}\rfloor} \binom{n}{2k+1} 2^{k+1} \sqrt{2}\right] \\ & = \frac{1}{2} \left[\sum_{k=0}^{\lfloor \tfrac{n-1}{2}\rfloor} \binom{n}{2k+1} 2^{k+1}\right]. \\ \end{align*} Because of $\nu_p$ addition rules, we simply need to find $\min\left\{\nu_2 \left( \binom{n}{2k+1} 2^{k+1}\right)\right\}$, which obviously occurs when $k = 0$. Therefore, \[\nu_2(a_n) = \nu_2\left(\frac{1}{2} \binom{n}{1} 2^{1}\right) = \nu_2(n),\] as desired. $\blacksquare$