Actually, the problem is from the Dutch Olympiad 1995 (or something). Here's a solution from "Mathematical Olympiad Treasures": Problem 2. The sequence $(a_{n})_{n\geq 1}$ satisfies $a_{1}=2,$ $a_{2}=3$ and, for each $n\geq 2,$ either $a_{n+1}=2a_{n-1}$ or $a_{n+1}=3a_{n}-2a_{n-1}.$ Prove that no integer between $1600$ and $2000$ can be a term of the sequence. Solution. Clearly, the sequence is not uniquely determined by the above conditions. A short analysis shows that the first $6$ terms could be a) 2,3,4,6,8,12; b) 2,3,4,6,10,12; c) 2,3,4,6,10,18; d) 2,3,5,6,10,12; e) 2,3,5,6,10,18; f) 2,3,5,6,8,12; g) 2,3,5,9,10,18; h) 2,3,5,9,10,12; i) 2,3,5,9,17,18; j) 2,3,5,9,17,33; The key observation is that each of the numbers $2,3,4,5,6,8,9,10,12,17,18$ and $33$ can be written as a sum of two powers of $2$ (or, equivalently, that their binary representation contains exactly two $1$'s). Thus, we may conjecture that $a_{n}=2^{x_{n}}+2^{y_{n}},$ for some integers $x_{n}$, $ y_{n}$ and try induction. Unfortunately, the attempt fails unless we observe something more. Let's take, for instance, the case h) and write the terms as sums of powers of $2$: $2=2^{0}+2^{0},$ $3=2^{0}+2^{1},$ $5=2^{0}+2^{2},$ $ 9=2^{0}+2^{3},$ $10=2^{1}+2^{3},$ $12=2^{2}+2^{3}.$ If you don't see the pattern, let's take case c): $2=2^{0}+2^{0},$ $3=2^{0}+2^{1},$ $ 4=2^{1}+2^{1},$ $6=2^{1}+2^{2},$ $10=2^{1}+2^{3},$ $18=2^{1}+2^{4}.$ We can see that at each step, exactly one of the numbers $x_{n}$ and $y_{n}$ increases with one unit. Now, we can state a stronger induction hypothesis which is easier to prove (this is not uncommon!): for each $n$, $ a_{n}=2^{x_{n}}+2^{y_{n}},$ with $x_{n}\leq x_{n+1},$ $y_{n}\leq y_{n+1}$ and $x_{n}+y_{n}+1=x_{n+1}+y_{n+1}.$ This obviously holds for $n=1,2.$ Suppose it holds for all $k\leq n$ and look at $a_{n+1}.$ If $a_{n+1}=2a_{n-1},$ then \[ a_{n+1}=2\left( 2^{x_{n-1}}+2^{y_{n-1}}\right) =2^{x_{n-1}+1}+2^{y_{n-1}+1}. \] If $x_{n}=x_{n-1}+1,y_{n}=y_{n-1},$ then let $x_{n+1}=x_{n}$ and $ y_{n+1}=y_{n}+1$ . We obtain $a_{n+1}=2^{x_{n+1}}+2^{y_{n+1}}.$ If $ x_{n}=x_{n-1},y_{n}=y_{n-1}+1,$ then let $x_{n+1}=x_{n}+1$ and $ y_{n+1}=y_{n}.$ Also, we get $a_{n+1}=2^{x_{n+1}}+2^{y_{n+1}}.$ If $a_{n+1}=3a_{n}-2a_{n-1},$ then \[ a_{n+1}=3\left( 2^{x_{n}}+2^{y_{n}}\right) -2\left( 2^{x_{n-1}}+2^{y_{n-1}}\right) . \] If $x_{n}=x_{n-1}+1,y_{n}=y_{n-1},$ then \[ a_{n+1}=3\left( 2^{x_{n-1}+1}+2^{y_{n-1}}\right) -2\left( 2^{x_{n-1}}+2^{y_{n-1}}\right) =2^{x_{n-1}+2}+2^{y_{n-1}}, \] so that if we take $x_{n+1}=x_{n}+1$ and $y_{n+1}=y_{n},$ we obtain $ a_{n+1}=2^{x_{n+1}}+2^{y_{n+1}}.$ The case $x_{n}=x_{n-1},y_{n}=y_{n-1}+1$ is similar thus our assertion is proved. Finally, we notice that the binary representations of the numbers $1600$ and $2000$ are $11001000000$ and $11111010000$, respectively. Clearly, no number between them has a binary representation with only two $1$'s. In fact, we can replace $1600$ and $2000$ with $1537$ and $2047$