Alternative solutions to $n^2+n = k^2+k + 2kn$

Question

Consider this equation:

$n^2+n = k^2+k + 2kn$

I want to find the set of non-negative integer n,k that satisfies the equation.

I tried to write $n$ as $k$ by solving the equation with $n$ as root results in: $n = {2k - 1 + \sqrt{8k^2 + 1} \over 2}$

With $8k^2+1$ as a square number, I found the series of $k$ by pell equation: $k_i = 6k_{i-1} - k_{i-2}$ , and thus $n$ can be deduced from there.

However there is a different solution, one can write:

$k_i = 2n_{i-1} + k_{i-1} + 1$

$n_i = 2k_i + n_{i-1}$

($n_0 = 0, k_0 = 0$)

Which I can't figure out how to get there. Please help.

Answer 1

The equation $n^2+n=k^2+k+2kn$ may be rewritten as $$[1]\ \ \ [2(n-k)+1]^2-8k^2=1,$$ which is a Pell equation of the simple type with 1 on the right side, all of whose solutions are obtained on writing $(3+\sqrt{8})^i=a_i+b_i\sqrt{8}.$ In this we have $2(n_i-k_i)+1=a_i$ and $k_i=b_i$

The recursion rule for the $a_i,b_i$ is obtained using $$(a_{i-1}+b_{i-1}\sqrt{8})\cdot (3+\sqrt{8})=a_i+b_i\sqrt{8},$$ giving recursions $a_i=3a_{i-1}+8b_{i-1}$ and $b_i=a_{i-1}+3b_{i-1}.$ We now have to restate these recursions in terms of the variables $n_i,k_i$ of the original equation. Note that always $k_i=b_i$, and that from $a_i=2(n-k)+1$ we can recover $n_i$ as $n_i=(a_i+2k_i-1)/2.$

Now the recursion for $k_i$ is the easier of the two, since from the above:

$$k_i=b_i=a_{i-1}+3b_{i-1}=\\ [2n_{i-1}-2k_{i-1}+1]+3k_{i-1}=2n_{i-1}+k_{i-1}+1.$$ Thus $k_i=2n_{i-1}+k_{i-1}+1$ in agreement with the recursion for $k_i$ mentioned in the question of the post.

To show the other recurrence for the $n_i$ it will help to rewrite the version given in the question of the recurrence, quote:

$k_i = 2n_{i-1} + k_{i-1} + 1$

$n_i = 2k_i + n_{i-1}$

($n_0 = 0, k_0 = 0$)

by substituting for $k_i$ in the second relation its value from the first relation, obtaining:

$k_i = 2n_{i-1} + k_{i-1} + 1,$

$n_i = 5n_{i-1} + 2k_{i-1}+2.$

In this rewritten form, both relations refer from the present pair $n_i,k_i$ to the previous solution pair $n_{i-1},k_{i-1}.$

Now for $n_i$ we have the equations

$n_i=((a_i)+2(k_i)-1)/2 = ([3a_{i-1}+8k_{i-1}]+2[2n_{i-1}+k_{i-1}+1]-1)/2,$

where in the last parenthesis we used our above value for $k_i$. Now we can replace on the rightmost side $a_{i-1}$ by its definition as $2n_{i-1}-2k_{i-1}+1$ and simplify algebraically, arriving at $n_i=5n_{i-1}+2k_{i-1}+2.$ This matches the rewritten recursion for $n_i$ (as noted above, in terms of $n_{i-1},k_{i-1}$) in the question of the post.