jmc

Expanding, we get $$\begin{array}{rl}3k+j+(k+j{)}^2& =3k+j+k^2+2kj+j^2\\ & =k(k+3)+2kj+j(j+1).\end{array}$$For each integer $k,$ either $k$ or $k+3$ is even, so $k(k+3)$ is always even. Similarly, either $j$ or $j+1$ is even, so $j(j+1)$ is always even. Thus, $3k+j+(k+j{)}^2$ is always even.

We claim that for any nonnegative integer $n,$ there exist unique nonnnegative integers $j$ and $k$ such that $$3k+j+(k+j{)}^2=2n.$$Let $a=k+j,$ so $$3k+j+(k+j{)}^2=2k+(k+j)+(k+j{)}^2=a^2+a+2k.$$For a fixed value of $a,$ $k$ can range from 0 to $a,$ so $a^2+a+2k$ takes on all even integers from $a^2+a$ to $a^2+a+2a=a^2+3a.$

Furthermore, for $k+j=a+1,$ $$3k+j+(k+j{)}^2=(a+1{)}^2+(a+1)+2k=a^2+3a+2+2k$$takes on all even integers from $a^2+3a+2$ to $a^2+3a+2+2(a+1)=a^2+5a+4,$ and so on. Thus, for different values of $a=k+j,$ the possible values of $3k+j+(k+j{)}^2$ do not overlap, and it takes on all even integers exactly once.

Therefore, $$\sum _{j=0}^{\infty }\sum _{k=0}^{\infty }{2}^{-3k-j-(k+j{)}^2}=\sum _{i=0}^{\infty }{2}^{-2i}=\boxed{\frac{4}{3}}.$$