<s>[INST] Find all non negative integers x,y,z so we get a whole square Find all $x,y,z\in\mathbb{N_0}$ so that there exists a $k\in\mathbb{N}$ so that
$$4^x+4^y+4^z=k^2$$.
We can transform this problem to:
Find all $a,b\in\mathbb{N_0}$ so that there exists a $t\in\mathbb{N}$ so that
$$4^a+4^b+1=t^2$$
where $a=x-z, b=y-z, k=2^z \cdot t$.
We see that $3|t^2 \Rightarrow 3|t$ and so we have that $a+b\equiv2 \mod3$.
Looking at $\mod 5$ we can see that both of $a$ and $b$ can't be both even at the same time. So one of them has to be odd.
 [/INST] Consider ,
$4^{x}+4^{y}+4^{z}=k^{2}.$
Assume that $x \geq y \geq z$.
It is immediately obvious that $k$ is even. 
Let $k=2m$ where $m$ is an integer.
Thus we have,
$4^{x}+4^{y}+4^{z}=4m^{2}$, assuming that $x,y,z \geq 2$, we have,
$4^{x-1}+4^{y-1}+4^{z-1}=m^{2}$, and so we return to our intial equation. 
If we repeat this procedure until at least one of $x,y,z$ are $0$, we shall reach the equation you described.
$1+4^{p}+4^{q}=n^{2}$ where $p,q,n$ are arbitrary integers. (*)
WLOG let $p>q$, so we have,
$4^{q}(4^{p-q}+1)=(n-1)(n+1)$.
(*) revealed that $n$ is odd and so $n-1,n+1$ are consecutive even integers. Thus one of these integers must be divisible by a power of $4$, and the other must be of the form $2b$ where $b$ is odd.
And so we have, 
$4^{q-1}(4^{p-q}+1)=\frac{(n-1)}{2}\frac{(n+1)}{2}$. (Credit to Samiron)
Equating, the odd and even parts, we are left with,
$\frac{n-1}{2}=4^{q-1} \Rightarrow n=2(4^{q-1})+1,$ and
$\frac{n+1}{2}=4^{p-q}+1 \Rightarrow n=2(4^{p-q})+1$.
Finally, 
$4^{p-q}=4^{q-1} \Rightarrow \frac{p+1}{2}=q$
Hence (*) becomes,
$1+4^{p}+4^{\frac{p+1}{2}}=n^{2} \Rightarrow (1+2^{p})^{2}=n^{2}, \Rightarrow n=2p+1$ ,  and we are done.
NB:  If we equate, 
$\frac{n-1}{2}=4^{p-q}+1 \Rightarrow n=2(4^{p-q})+3$ and,
$\frac{n+1}{2}=4^{q-1} \Rightarrow n=2(4^{q-1})-1$
Hence, 
$2(4^{q-1})-1=2(4^{p-q})+3 \Rightarrow 2(4^{q-1})=2(4^{p-q})+4 \Rightarrow 4^{q-1}=4^{p-q}+2 \Rightarrow 4^{q-1}-4^{p-q}=2$
And so we have a pair of numbers that are multiples of $4$, that differ by $2$. This is clearly not possible. Hence this case yields no solutions.
</s>