# 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$.

• Where did you find this problem? :) – Sawarnik Mar 8 '15 at 9:02
• Any questions/thoughts about my answer, Jingyi? – Gerry Myerson Mar 9 '15 at 12:08

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.]

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)$

• Sorry, I don't understand. It seems that this method can only generate even solutions? I have tried induction and $(x_{k+1}, y_{k+1}) = (2x_k, 2y_k)$. – J. XU Mar 8 '15 at 6:24
• @JingyiXu, You already have $2^2+2\cdot15=4^3$ – lab bhattacharjee Mar 8 '15 at 6:28
• But, for $4^3$ I need $3$ solutions. – J. XU Mar 8 '15 at 6:31
• @JingyiXu, Updated the solution – lab bhattacharjee Mar 9 '15 at 13:53