Peter wrote: An integer sequence $\{a_{n}\}_{n \ge 1}$ is defined by \[a_{0}=0, \; a_{1}=1, \; a_{n+2}=2a_{n+1}+a_{n}\] Show that $2^{k}$ divides $a_{n}$ if and only if $2^{k}$ divides $n$. Let's prove a nice lemma concerning this kind of sequences. Lemma 1: If $\{x_{n}\}_{n\ge1}$ is a sequence of real numbers defined by $x_{1}=a,x_{2}=b$ ($a,b\in{R}$) and $x_{n+2}=bx_{n+1}+ax_{n}$ ,then $x_{n+m}=x_{n}x_{m+1}+x_{n-1}x_{m}$ for any positive integer $m$. Proof: Let's led the proof by induction for $m$. 1.$m=1$ $\Rightarrow$ $x_{n+m}=x_{n}x_{m+1}+x_{n-1}x_{m}\Leftrightarrow x_{n+1}=bx_{n}+ax_{n-1}$ 2. Suppose that we have proved the desired relation for all positive integer $m$s that are less or equal to some $k$. 3. Now we prove it for $m=k+1$. We have that \[x_{n+k+1}=bx_{n+k}+ax_{n+k-1}=b(x_{n}x_{k+1}+x_{n-1}x_{k})+a(x_{n}x_{k}+x_{n-1}x_{k-1})\] but \[b(x_{n}x_{k+1}+x_{n-1}x_{k})+a(x_{n}x_{k}+x_{n-1}x_{k-1})=x_{n}x_{k+2}+x_{n-1}x_{k+1}\] $\Rightarrow$ $x_{n+k+1}=x_{n}x_{k+2}+x_{n-1}x_{k+1}.$ So the lemma is proven. Now let's use this lemma for our sequence:$\{a_{n}\}_{n \ge 1}$. We get that $a_{n+m}=a_{m}a_{n+1}+a_{m-1}a_{n}$.Putting $m=n$ we find that $a_{2n}=a_{n}(a_{n+1}+a_{n-1})=2a_{n}(a_{n}+a_{n-1}).$ From the initial property of the sequence we can see that $a_{n}$ and $a_{n-1}$ are either both odd or both even. And as we have that $a_{0}=0$ and $a_{1}=1$ $\Rightarrow$ $a_{2n}$ is even and $a_{2n+1}$ is odd for all $n\in{N_{0}}$,then $a_{n}+a_{n-1}$ is an odd number.So if $2^{k}|a_{2n}\Rightarrow 2^{k}|2a_{n}\Rightarrow 2^{k-1}|a_{n}$. But considering that $a_{2}=2$ we obtain that $2^{k}|a_{n}\Rightarrow 2^{k}|n$.

Peter wrote: An integer sequence $ \{a_{n}\}_{n \ge 1}$ is defined by \[ a_{0}=0, \; a_{1}=1, \; a_{n+2}=2a_{n+1}+a_{n}\] Show that $ 2^{k}$ divides $ a_{n}$ if and only if $ 2^{k}$ divides $ n$. I really love this problem. It is beautiful and has many solutions. What we need to do is to read $ a_{n}$ (modulo $ 2^{k}$ and) modulo $ 2^{k+1}$. We shall establish that $ a_{2^{k}m}\equiv 2^{k}\; (mod \; 2^{k+1})$ for all odd $ m \in \mathbf{Z}_{>0}$ and $ k \in \mathbf{Z}_{\geq 0}$. This implies that $ 2^{k}\; \vert \; a_{2^{k}m}$ and $ 2^{k+1}\not\vert \; a_{2^{k}m}$. We need the following simple congruence. [Proposition] Suppose that $ n=2^{k}m \in \mathbf{Z}_{>1}$, where $ m$ is odd. For all odd $ j<n$, we have $ \binom{n}{j}\equiv 0 \; (mod \; 2^{k})$. It is a particular case of the following claim with $ p=2$: [Claim] Let $ p$ be a prime number and let $ n \in \mathbf{Z}_{>1}$. Write $ n=p^{e}m$, where $ (m, p)=1$. Then, for all $ j<n$ with $ (j, p)=1$, we obtain \[ \binom{n}{j}\equiv 0 \; (mod \; p^{e}). \] [Proof of Claim] Since ${ j \; \vert \; j \binom{n}{j}= n \binom{n-1}{j-1}= p^{e}\cdot m \binom{n-1}{j-1}}$ and since $ (j, p^{e})=1$, we find that $ j \; \vert \; m \binom{n-1}{j-1}$ so that \[ \binom{n}{j}= p^{e}\cdot \frac{m \binom{n-1}{j-1}}{j}\equiv 0 \; (mod \; p^{e}). \] In order to read $ a_{2^{k}m}$ modulo $ 2^{k+1}$, we find the combinatorial solution of the linear recurrence. It's a routine job to get \[ a_{n}= \frac{1}{2\sqrt{2}}\left( (1+\sqrt{2})^{n}-(1-\sqrt{2})^{n}\right). \] By the binomial theorem, we obtain \[ a_{n}= \sum_{j \; \text{: odd}}2^{ \frac{j-1}{2}}\binom{n}{j}= n+\sum_{j>1 \; \text{: odd}}2^{\frac{j-1}{2}}\binom{n}{j}. \] Suppose that $ n=2^{k}m$ where $ m$ is odd. Let $ 1<j<n$ be odd. It follows from the above proposition and from $ 2 \; \vert \; 2^{\frac{j-1}{2}}$ that $ 2^{\frac{j-1}{2}}\binom{n}{j}\equiv 0 \; (mod \; 2^{k+1})$. We therefore conclude that \[ a_{n}\equiv 2^{k}m+\sum_{j>1 \; \text{: odd}}2^{\frac{j-1}{2}}\binom{n}{j}\equiv 2^{k}\; (mod \; 2^{k+1}). \]

Peter wrote: An integer sequence $ \{a_{n}\}_{n \ge 1}$ is defined by \[ a_{0}=0, \; a_{1}=1, \; a_{n+2}=2a_{n+1}+a_{n}\] Show that $ 2^{k}$ divides $ a_{n}$ if and only if $ 2^{k}$ divides $ n$. One may modify the method by Tiks to generalize the problem slightly. Theorem. Let $ u$ be an integer with $ u \equiv 2 \; (mod \; 4)$. Suppose that the sequence $ \{x_{n}\}_{n \ge 0}$ satisfies the recurrence relation \[ x_{n+1}= u x_{n}+x_{n-1}, \;\; n \in \mathbb{N}\] and has the initial condition $ x_{0}=0$ and $ x_{1}=1$. Then, $ 2^{k}$ divides $ a_{n}$ if and only if $ 2^{k}$ divides $ n$. Proof. Since it clearly holds for $ n=0$, we now assume that $ n \geq 1$. It is enough to show the following. Claim. For all odd $ m \geq 1$ and $ k \geq 0$, we obtain $ 2^{k}\; \vert\vert \; a_{2^{k}m}$. We first work modulo $ 2$. Reading the recurrence relation modulo $ 2$, we find that $ x_{n}\; (mod \; 2)$ is periodic. Indeed, it follows from $ u \equiv 2 \; (mod \; 4)$ that \[ x_{n+2}\equiv u x_{n+1}+x_{n}\equiv x_{n}\; (mod \; 2). \] Since $ x_{1}\equiv 1 \; (mod \; 2)$ and $ x_{2}\equiv u \equiv 0 \; (mod \; 2)$, this means that both $ x_{n}$ and $ n$ has the same parity for all $ n \in \mathbb{N}$. Since $ u\equiv 2 \; (mod \; 4)$, we may write \[ u=2 r \] for some odd integer $ r$. The trick is to establish the following factorization formula. Proposition. Set $ Q_{n}=r x_{n}+x_{n-1}$, where $ n \geq 1$. Then, for all $ m \geq 1$ and $ k \geq 1$, we obtain \[ x_{2^{k}m}= 2^{k}x_{m}\prod_{j=0}^{k-1}Q_{2^{j}m}. \] Proof of claim. Let $ m \geq 1$ be odd and $ k \geq 0$. Our job is to show that $ 2^{k}\vert x_{2^{k}m}$ and $ 2^{k+1}\not\vert x_{2^{k}m}$. In the case of $ k=0$, it clearly holds because $ x_{m}$ is odd. Now assume that $ k \geq 1$. By the proposition, we get \[ x_{2^{k}m}= 2^{k}x_{m}\prod_{j=0}^{k-1}Q_{2^{j}m}\] We need to show that $ x_{m}\prod_{j=0}^{k-1}Q_{2^{j}m}$ is odd. Recall that $ x_{n}$ and $ n$ has the same parity for all $ n \in \mathbb{N}$. Since $ m$ is odd, $ x_{m}$ is odd. Since $ r$ is odd, we see that \[ Q_{n}\equiv r x_{n}+x_{n-1}\equiv x_{n}+x_{n-1}\; (mod \; 2) \] so that $ Q_{n}$ is always odd. Hence, $ \prod_{j=0}^{k-1}Q_{2^{j}m}$ is also odd. This completes the proof. Now, we need to prove the proposition. It comes from the following formula. Lemma. For all $ n \in \mathbb{N}$, we have \[ x_{2n}= 2 x_{n}\left( rx_{n}+x_{n-1}\right) = 2x_{n}Q_{n}. \] Proof of proposition. Our job is to show that \[ x_{2^{k}m}= 2^{k}x_{m}\prod_{j=0}^{k-1}Q_{2^{j}m}. \] By the lemma, $ x_{2m}= 2x_{m}Q_{m}$. Applying the lemma twice, we have $ x_{2^{2}m}= 2^{2}x_{m}Q_{m}Q_{2m}$. Now, it is clear that we need to use the induction on $ k$. Proof of lemma. Recall that $ x_{n+1}= u x_{n}+x_{n-1}$, $ n \in \mathbb{N}$. It can be rewritten as \[ x_{2n}= 2 x_{n}\left( \frac{u}{2}x_{n}+x_{n-1}\right). \] or \[ x_{2n}= x_{n}\left( ux_{n}+2x_{n-1}\right). \] or \[ x_{2n}= x_{n}\left( x_{n+1}+x_{n-1}\right). \] However, this can be deduced by taking $ m=n$ in the following theorem. Theorem. Suppose that the sequence $ \{x_{n}\}_{n \ge 0}$ satisfies the recurrence relation \[ x_{n+1}= u x_{n}+x_{n-1}, \;\; n \in \mathbb{N}\] and has the initial condition $ x_{0}=0$ and $ x_{1}=1$. Then, we have \[ x_{n+m}= x_{m+1}x_{n}+x_{m}x_{n-1}\] for all $ n \geq 1$ and $ m \geq 0$. Proof. This is well-known. For example, we may prove this by induction on $ m$.

Peter wrote: An integer sequence $ \{a_{n}\}_{n \ge 1}$ is defined by \[ a_{0}=0, \; a_{1}=1, \; a_{n+2}=2a_{n+1}+a_{n}\] Show that $ 2^{k}$ divides $ a_{n}$ if and only if $ 2^{k}$ divides $ n$. We offer an alternative proof of the previous theorem in the above solution. {Theorem.} Let $ u$ be an integer with $ u \equiv 2 \; (mod \; 4)$. Suppose that the sequence $ \{x_{n}\}_{n \ge 0}$ satisfies the recurrence relation \[ x_{n+1}= u x_{n}+x_{n-1}, \;\; n \in \mathbb{N}\] and has the initial condition $ x_{0}=0$ and $ x_{1}=1$. Then, $ 2^{k}$ divides $ a_{n}$ if and only if $ 2^{k}$ divides $ n$. We'll establish the following claim. {Claim.} Let $ k \geq 1$ and $ m \geq 0$. Set $ G_{k}(m)=\frac{x_{2^{k}m}}{2^{k}}$. Then, $ G_{k}(m)$ is integer for all $ k$ and $ m$. Furthermore, \[ G_{k}(m) \equiv \begin{cases}1 \; (mod \; 2) & \left( m \equiv 1 \; (mod \; 2) \right), \\ 2 \; (mod \; 4) & \left( m \equiv 2 \; (mod \; 4) \right), \\ 0 \; (mod \; 4) & \left( m \equiv 0 \; (mod \; 4) \right). \\ \end{cases}\] Clearly, this implies that $ 2^{k}\; \vert\vert \; a_{2^{k}m}$ for all odd $ m \geq 1$ and $ k \geq 0$. {Proposition.} The sequence $ \{u_{n}\}_{n \ge 1}$ satisfies the recurrence relation \[ u_{n+1}={u_{n}^{2}-2}, \;\; n \in \mathbb{N}\] and has the initial condition $ u_{1}=u^{2}+2$. Then, for all $ k \geq 1$ and $ m \geq 0$, we have \[ G_{k+1}(m)=\frac{1}{2}G_{k}(2m) \] and \[ G_{k}(m+2) = u_{k}G_{k}(m+1)-G_{k}(m). \] We first use the proposition to prove the claim and then prove the proposition. Since $ u\equiv 2 \; (mod \; 4)$, we write $ u=2 r$ for some odd integer $ r$. {Proof of Claim.} Induction on $ k$. First, consider the case $ k=1$. In the previous solution, we showed that both $ x_{n}$ and $ n$ have the same parity. Hence, we see that $ x_{n}$ is even for all even $ n$. In other words, we find that \[ G_{1}(m)=\frac{x_{2m}}{2}\] is an integer for all $ m \geq 0$. By the second assertion in the proposition, we get \[ G_{1}(m+2) = \left( u^{2}+2 \right) G_{1}(m+1)-G_{1}(m). \] Since $ u \equiv 2 \; (mod \; 4)$, this implies that \[ G_{1}(m+2) \equiv 2 G_{1}(m+1)-G_{1}(m) \; (mod \; 4). \] Since $ G_{1}(0)=\frac{x_{0}}{2}=0 \equiv 0 \; (mod \; 4)$ and $ G_{1}(1)=\frac{x_{2}}{2}=\frac{u}{2}=r \equiv 1 \; (mod \; 2)$, this congruence imply that \[ G_{1}(m) \equiv \begin{cases}1 \; (mod \; 2) & \left( m \equiv 1 \; (mod \; 2) \right), \\ 2 \; (mod \; 4) & \left( m \equiv 2 \; (mod \; 4) \right), \\ 0 \; (mod \; 4) & \left( m \equiv 0 \; (mod \; 4) \right). \\ \end{cases}\] Hence, it is true for $ k=1$. Now, assume that it holds for some $ k \geq 1$. First, we need to show that $ G_{k+1}(m)$ is integer for all $ m \geq 0$. By the inductive hypothesis, we see that $ G_{k}(2m)$ is even. Hence, \[ G_{k+1}(m)=\frac{1}{2}G_{k}(2m) \] is also an integer for all $ m \geq 0$. It's an easy job to check that $ u_{k}\equiv 2 \; (mod \; 4)$ holds for all $ k \geq 1$. Hence, reading the second assertion in the proposition modulo $ 4$, we obtain \[ G_{k+1}(m+2) \equiv 2 G_{k+1}(m+1)-G_{k+1}(m) \; (mod \; 4). \] We compute $ G_{k+1}(0)=\frac{x_{0}}{2^{k+1}}= 0$. By the inductive hypothesis, we see that $ G_{k}(2) \equiv 2 \; (mod \; 4)$ so that $ G_{k+1}(1)=\frac{1}{2}G_{k}(2) \equiv 1 \; (mod \; 2)$. Since $ G_{k+1}(0) \equiv 0 \; (mod \; 4)$ and since $ G_{k+1}(1) \equiv 1 \; (mod \; 2)$, one may conclude that \[ G_{k+1}(m) \equiv \begin{cases}1 \; (mod \; 2) & \left( m \equiv 1 \; (mod \; 2) \right), \\ 2 \; (mod \; 4) & \left( m \equiv 2 \; (mod \; 4) \right), \\ 0 \; (mod \; 4) & \left( m \equiv 0 \; (mod \; 4) \right), \\ \end{cases}\] as desired. {Proof of Proposition.} The first assertion is easy: \[ G_{k+1}(m)=\frac{ x_{2^{k+1}m}}{2^{k+1}}=\frac{1}{2}\cdot \frac{ x_{2^{k}\cdot 2m}}{2^{k}}= \frac{1}{2}G_{k}(2m). \] The second assertion is equivalent to \[ 2^{k}G_{k}(m+2) = u_{k}2^{k}G_{k}(m+1)-2^{k}G_{k}(m) \] or \[ x_{2^{k}(m+2)}= u_{k}x_{2^{k}(m+1)}-x_{2^{k}m}. \] This can be proved by induction on $ k$. We omit the details.

I used 2-adic analysis: First, one can find the explicit form of $a_n$ as: $a_n = \frac{(1+\sqrt{2})^n - (1-\sqrt{2})^n}{2\sqrt{2}}$ This formula is equivalent to looking at the integral coefficient of the term with $\sqrt{2}$ in the expansion of $(1+\sqrt{2})^n$. The problem statement can now be proved with the following, more general statement: Prove that $v_2(a_n) = v_2(n)$. To prove this, we use induction. But first let us rewrite $a_i$ to make the 2-adic stuff more workable. Define $(1+\sqrt{2})^i = b_i + a_i\sqrt{2}$ Note that $b_i$ is odd for all i. This follows directly from the binomial expansion of $(1+\sqrt{2})^i$. For the base cases, $v_2(a_1) = 0$ and $v_2(a_2) = 1$. We now carry our induction on $i \leq 2^k \rightarrow i \leq 2^{k+1}$ Suppose that $v_2(a_i) = i$ for all $i \leq 2^k$. We have that $v_2(a_{2i}) = v_2(2a_i \cdot b_i) = v_2(a_i) + 1 = v_2(i) + 1 = v_2(2i)$ And $v_2(a_{2i+1}) = v_2(2a_i\cdot b_i + b_{2i}) = 0 = v_2(2i+1)$. So our induction hypothesis holds and the conclusion is implied.