The divisibility properties of the numbers defined by $a_{n+1}=2a_n+a_{n-1}$ (and $a_1=1$ and $a_2=2$) are not random. One reason for this is that this sequence has the very non-random property of being eventually periodic mod $N$, for every integer $N$. In particular, since $$ a_n = \frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}},$$ we see that if $p$ is an odd prime then $a_n\equiv 0\pmod{p}$ if and only if $n$ is a multiple of the order of $$ \frac{1+\sqrt{2}}{1-\sqrt{2}} = -(1+\sqrt{2})^2 $$ in the multiplicative group of $\mathbf{F}_p(\sqrt{2})$. (Note that the order of this element does not depend on the choice of a square root of $2$ in $\mathbf{F}_{p^2}^*$.) Therefore if $p$ is an odd prime then $$ \mathbb{P}\bigl[a_n\equiv 0\pmod{p}\bigr] = \frac{1}{c_p} $$ where $c_p$ is the order of $-(1+\sqrt{2})^2$ in $\mathbf{F}_{p^2}^*$. For completeness, I note that the terms of the sequence $(a_n)$ alternate in parity, so that half of them are even and half are odd.

The next question is to understand the distribution of the numbers $c_p$, where $p$ is an odd prime. This connects with the number field analogue of Artin's primitive root conjecture. First consider primes $p$ with $p\equiv 1\pmod{8}$: for such primes, both $-1$ and $2$ are squares in $\mathbf{F}_p^*$, so that also $-(1+\sqrt{2})^2$ is a square and thus $c_p\mid (p-1)/2$. It is expected that there are infinitely many primes $p\equiv 1\pmod{8}$ for which $1+\sqrt{2}$ generates $\mathbf{F}_p^*$ (so that $c_p= (p-1)/2$), and further there is a heuristically predicted (positive) value for the density of such primes $p$. Similar remarks apply when $p\equiv -1\pmod{8}$. Next if $p\equiv 3\pmod{8}$ then $2$ is a nonsquare in $\mathbf{F}_p^*$, but the image of the unit group of $\mathbf{Z}[\sqrt{2}]$ in $\mathbf{F}_{p^2}^*$ has order dividing $p+1$, so that $c_p\mid (p+1)/2$. Further, there is a heuristically predicted (positive) value for the density of the set of primes $p\equiv 3\pmod{8}$ for which $c_p=(p+1)/2$. Again, similar remarks apply when $p\equiv -3\pmod{8}$. These heuristic predictions have been proved under the assumption of suitable Generalized Riemann Hypotheses. For references, see Pieter Moree's comprehensive survey on Artin's primitive root conjecture, which contains a wealth of further information.

The divisibility properties of the numbers defined by $a_{n+1}=2a_n+a_{n-1}$ (and $a_1=1$ and $a_2=2$) are not random. One reason for this is that this sequence has the very non-random property of being eventually periodic mod $N$, for every integer $N$. In particular, since $$ a_n = \frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}},$$ we see that if $p$ is an odd prime then $a_n\equiv 0\pmod{p}$ if and only if $n$ is a multiple of the order of $$ \frac{1+\sqrt{2}}{1-\sqrt{2}} = -(1+\sqrt{2})^2 $$ in the multiplicative group of $\mathbf{F}_p(\sqrt{2})$. (Note that the order of this element does not depend on the choice of a square root of $2$ in $\mathbf{F}_{p^2}^*$.) Therefore if $p$ is an odd prime then $$ \mathbb{P}\bigl[a_n\equiv 0\pmod{p}\bigr] = \frac{1}{c_p} $$ where $c_p$ is the order of $-(1+\sqrt{2})^2$ in $\mathbf{F}_{p^2}^*$. For completeness, I note that the terms of the sequence $(a_n)$ alternate in parity, so that half of them are even and half are odd.

The next question is to understand the distribution of the numbers $c_p$, where $p$ is an odd prime. This connects with the number field analogue of Artin's primitive root conjecture. First consider primes $p$ with $p\equiv 1\pmod{8}$: for such primes, both $-1$ and $2$ are squares in $\mathbf{F}_p^*$, so that also $-(1+\sqrt{2})^2$ is a square and thus $c_p\mid (p-1)/2$. It is expected that there are infinitely many primes $p\equiv 1\pmod{8}$ for which $1+\sqrt{2}$ generates $\mathbf{F}_p^*$ (so that $c_p= (p-1)/2$), and further there is a heuristically predicted (positive) value for the density of such primes $p$. Similar remarks apply when $p\equiv -1\pmod{8}$. Next if $p\equiv 3\pmod{8}$ then $2$ is a nonsquare in $\mathbf{F}_p^*$, but every unit in $\mathbf{Z}[\sqrt{2}]$ has norm $\pm 1$ and hence its image in $\mathbf{F}_{p^2}^*$ has order dividing $2(p+1)$, so that $c_p\mid (p+1)$. Further, there is a heuristically predicted (positive) value for the density of the set of primes $p\equiv 3\pmod{8}$ for which $c_p=(p+1)$. Again, similar remarks apply when $p\equiv -3\pmod{8}$. These heuristic predictions have been proved under the assumption of suitable Generalized Riemann Hypotheses. For references, see Pieter Moree's comprehensive survey on Artin's primitive root conjecture, which contains a wealth of further information.