# How find this positive integer numbers $m$,such $a_{n}=2a_{n-1}+a_{n-2}$,if $2^{2011}|a_{m}$

let sequence $$a_{0}=0,a_{1}=1,a_{n}=2a_{n-1}+a_{n-2},(n\ge 2)$$

Find all positive integer numbers $m$ ,such $2^{2011}|a_{m}$

My try:since $a_{0}=0,a_{1}=1$,then $$a_{n}=\dfrac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}$$ then I can't. maybe this idea is not usefull.It is said this can use :Binary number But I can't. Thank you

• Idea: calculate a few $a_n$, see the parity (and more), guess a patron, prove by induction. – Martín-Blas Pérez Pinilla Feb 10 '14 at 14:45
• By just experimenting, it looks like the $2$-adic valuation of $a_n$ equals the $2$-adic valuation of $n$. Maybe this pattern can be proved by induction? – froggie Feb 10 '14 at 15:45

Let $\lambda_+ = 1 + \sqrt{2}$ and $\lambda_- = 1 - \sqrt{2}$, so that $$a_n = \frac{\lambda_+^n - \lambda_-^n}{2\sqrt{2}}.$$ One thing you can observe immediately is that $$a_{2n} = \frac{\lambda_+^{2n} - \lambda_-^{2n}}{2\sqrt{2}} = a_n \cdot(\lambda_+^n + \lambda_-^n).$$ By simply expanding, $$\lambda_+^n + \lambda_-^n = \sum_{k=0,\,\,even}^n\binom{n}{k}2(\sqrt{2})^k,$$ and from this we see that $\lambda_+^n + \lambda_-^n$ is an integer whose $2$-adic valuation is exactly $1$. Thus we conclude that $$\nu_2(a_{2n}) = 1 + \nu_{2}(a_n).$$ By induction, we similarly have $\nu_2(a_{2^mn}) = m + \nu_2(a_n)$.

To prove that $\nu_2(a_n) = \nu_2(n)$, it therefore suffices to show that $\nu_2(a_n) = 0$ when $n$ is odd. We can do this by induction on $n\geq 1$, $n$ odd. Indeed, $\nu_2(a_1) = \nu_2(1) = 0$. Now, if $n>1$ is odd and we know that $a_{m}$ is odd for all odd $m<n$, then by the recursion relation and induction, we have that $a_n = 2a_{n-1} + a_{n-2}$ is odd, so $\nu_2(a_n) = 0$. This completes the proof that $\nu_2(a_n) = \nu_2(n)$.

In particular, $2^{2011}\mid a_n$ if and only if $2^{2011}\mid n$.

• Do you mean $\nu_2(a_{2^mn}) = m + \nu_2(a_{n})$? – ploosu2 Feb 11 '14 at 0:16
• @ploosu2: You're right, that was a typo. Edited. – froggie Feb 11 '14 at 7:04

If it's any help, here are some first terms of the sequence written in binary (since using binary numbers was a hint). It certainly looks like $a_n$ has as many zeros in the end as $n$, as was already mentioned (the $2$-adic evaluation comment by froggie). I don't see any easy way to prove this, though. But here's the list:

1. $a_1 = 1$
2. $a_{10} = 10$
3. $a_{11} = 101$
4. $a_{100} = 1100$
5. $a_{101} = 11101$
6. $a_{110} = 1000110$
7. $a_{111} = 10101001$
8. $a_{1000} = 110011000$
9. $a_{1001} = 1111011001$
10. $a_{1010} = 100101001010$
11. $a_{1011} = 1011001101101$
12. $a_{1100} = 11011000100100$
13. $a_{1101} = 1000001010110101$
14. $a_{1110} = 10011101110001110$
15. $a_{1111} = 101111100111010001$
16. $a_{10000} = 1110010111100110000$
17. $a_{10001} = 100010101100000110001$
18. $a_{10010} = 1010011101111110010010$
19. $a_{10011} = 11001010001011101010101$
20. $a_{10100} = 111101000000111000111100$
21. $a_{10101} = 10010011010011001111001101$
22. $a_{10110} = 101100011100111010111010110$
23. $a_{10111} = 1101011010100001111101111001$
24. $a_{11000} = 100000011000101011010011001000$
25. $a_{11001} = 1001110001011111000100100001001$
26. $a_{11010} = 10111100110000011100011011011010$
27. $a_{11011} = 111000111101100110001011010111101$
28. $a_{11100} = 10001001100001001111111010001010100$
29. $a_{11101} = 101001100000000000101111111101100101$
30. $a_{11110} = 1100100001100001011011111001100011110$
31. $a_{11111} = 11110001111000010111101110010110100001$
32. $a_{100000} = 1001000111111100111010111011111001100000$
33. $a_{100001} = 10110000001110010001101100110001001100001$
34. $a_{100010} = 110101001011100001010110001000001100100010$
35. $a_{100011} = 10000000011000110100111001110110100010100101$
36. $a_{100100} = 100110101111101001011001001110101010001101100$
37. $a_{100101} = 1011101100010011001011001101100001000101111101$
38. $a_{100110} = 11100001110100011100001100100110111011101100110$
39. $a_{100111} = 1000100001001011010001110010111010000000001001001$
40. $a_{101000} = 10100100100001010111111110010011010111011111111000$
41. $a_{101001} = 110001101001100001010001010111101111111000000111001$
42. $a_{101010} = 1110111110111001101100010100001111010101100001101010$
43. $a_{101011} = 100100001010111111100010110011011100101010000100001101$
44. $a_{101100} = 1010111010100111000110001111011001000101001101010000100$
45. $a_{101101} = 11010010110100110001000110101001101101111101011000010101$
46. $a_{101110} = 111111100111110011010111111001110100100100100011010101110$
47. $a_{101111} = 10011001100110001100111000101000110110111000110001101110001$
48. $a_{110000} = 101110010110100001101001001001011100010010110000110110010000$
49. $a_{110001} = 1101111111001110100111001010111111111011100100111111010010001$
50. $a_{110010} = 100001110001010001011011011111001011011001100000000101010110010$

EDIT: I had second term three times. Sorry I don't know how to make the list index to accord with the terms, so I left the zeroth term out. Now the list index is the same as sequence index.

Any 2-term linear recursion can be represented as a power of a matrix (in this case, $[a_{n+1}, a_n; a_n, a_{n-1}] = [2,1;1,0]^n$). This means that the identities $a_{2n} = a_{n}*(a_{n-1} + a_{n+1})$ and $a_{2n+1} = a_{n+1}^2 + a_{n}^2$ hold. Given the base {0, 1, 2}, the 2-adic evaluation follows inductively.

• I suggest you elaborate a bit on the 'follows immediately'. It is clear to me what you mean, but some people might prefer to see how the induction goes exactly. No offense at all, instead it's nice to learn something from reading answers once more. – punctured dusk Feb 10 '14 at 20:19