Show that $x^2+15y^2=4^n$ has at least $n$ non-negative integer solutions 
Prove that for any $n \in \mathbb{Z}^+$ the equation $x^2+15y^2=4^n$ has at least $n$ non-negative integer solutions.

I tried to solve it by mathematical induction.
When $n=1$ we can easily find a solution $(2,0)$.
Let $(x_k, y_k)$ be a solution when $n=k$, we have $(x_{k+1}, y_{k+1}) = (2x_k, 2y_k)$ which is available when $n=k+1$.
Therefore, when $n=k+1$ we get $k$ solutions, if we can find another solution which is different from the other $k$ solutions, the proof is done.
I found that the solutions in $n=k+1$ which are generated from $n=k$ are always even, so I try to find an odd solution to make it different.
I suppose that the odd solution can exist when $n\geq 2$. For example, $(x_2,y_2)=(1,1)$, $(x_3,y_3)=(7,1)$, $(x_4,y_4)=(11,3)$, $(x_5,y_5)=(17,7)$ and so on.
I tried to figure out the relation between $n$ and $y_n$, and got an answer on OEIS:A106853, a strange sequence for me.
And I don't know how to do next. Could you help me?
What's more, I wonder whether the number of solutions is exactly $n$.
 A: We need $n\ge2$
Use Generalized Brahmagupta–Fibonacci identity, $$(ac\pm mbd)^2+m(ad\mp bc)^2=(a^2+mb^2)(c^2+md^2)$$
Here $m=15$
Use induction:
Set $a=b=1$  $$(c\pm15d)^2+15(d\mp c)^2=(1^2+15\cdot1^2)(c^2+15d^2)$$
Now the base cases : $4^2=1^2+15\cdot1^2(i),4^2+15\cdot0^2(ii)$ 
For
$4^3=2^2(4^2)=2^2(1^2+15\cdot1^2)=2^2+15\cdot2^2(i)$ and $4^3=8^2(ii)=7^2+15\cdot1^2(iii)$
A: As OP notes, it suffices to prove that there is an odd solution. 
It is not hard to show that if $x=a$, $y=b$ is a solution to $x^2+15y^2=4^n$ with $x$ and $y$ odd and $x-y$ a multiple of $4$, then $x=(a-15b)/2$, $y=(a+b)/2$ is a solution to $x^2+15y^2=4^{n+1}$ with $x$ and $y$ odd and $x-y$ a multiple of $4$. 
Now notice that $x=1$, $y=1$ is a solution to $x^2+15y^2=4$ with $x$ and $y$ odd and $x-y$ a multiple of $4$, and we have a proof by induction that there's always an odd solution. 
[Note: the formula will sometimes give you negative values for $x$ and/or $y$, but if there's a solution in negative odd integers then there's one in positive odd integers as well, as you can replace any negative number by its absolute value.]
