Alternative solutions to $n^2+n = k^2+k + 2kn$ 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.
 A: 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.
