algebra direct connect pell eqn soln $(p_{nk},q_{nk})$ with $(p_n + q_n\sqrt{D})^k$
Solution 1:
I just had insights that facilitated the proof.
Given:
(a) $\;D \in \mathbb{Z^+}\;$ is not a perfect square.
(b) The continued fraction expansion of $\;\sqrt{D}\;$ is
$\;[a_1, \overline{a_2, \cdots, a_n, 2a_1}].$
(c) Coprime $\;\frac{p_r}{q_r}\;$ denotes the $r^{th}$
convergent of $\sqrt{D}.$
(d) $\;\forall k \in \mathbb{Z^+}, \;(P_k,Q_k)$ is defined by
$\;(p_n + q_n\sqrt{D})^k = P_k + Q_k\sqrt{D}.$
To prove: $\;\;$ (e) $\;\forall k \in \mathbb{Z^+},$ $\;(p_{nk},q_{nk}) = (P_k, Q_k).$
Proof:
In general, continued fraction results may have to adjust to the first element
in $\;\alpha = [a_1, a_2, \cdots]$ being $a_1,$ rather than $a_0.$
When $\;n=1\;$ (i.e. $\;\sqrt{2} = [1,\overline{2}]),\;$ the artificial nature
of
$\;(p_{n-1}, q_{n-1}) = (p_0, q_0) = (1,0)\;$ suggests that this case
should be handled separately.
$\underline{\text{case 1:} \;\; n>1}$
In Old-s_pdf, the analysis in pages 114-115 (page 61/85 in the pdf file),
establishes the following:
(1) $\;p_{n-1} = Dq_n - a_1p_n\;$ and $\;q_{n-1} = p_n - a_1q_n.$
(2) $\;{p_n}^2 - D{q_n}^2 = (-1)^n.$
However, examination of this analysis indicates that it can be extended to
$\alpha_{[(nk)+1]} = \sqrt{D} + a_1\; :\;k\in\mathbb{Z^+} \;\Rightarrow\; \sqrt{D} = \dfrac{(\sqrt{D} + a_1)p_{nk} + p_{[(nk)-1]}} {(\sqrt{D} + a_1)q_{nk} + q_{[(nk)-1]}}\;$
This leads to
(3) $\;p_{[(nk)-1]} = Dq_{nk} - a_1p_{nk}\;$ and $\;q_{[(nk)-1]} = p_{nk} - a_1q_{nk}.$
Also, since $\;p_{nk}q_{[(nk)-1]} - q_{nk}p_{[(nk)-1]} = (-1)^{nk},\;$ this leads to
(4) $\;{p_{nk}}^2 - D{q_{nk}}^2 = (-1)^{nk}.$
(5) $\;{P_k}^2 - D{Q_k}^2 \;=\; (P_k + Q_k\sqrt{D})(P_k - Q_k\sqrt{D})
\;=\; (P_1 + Q_1\sqrt{D})^k (P_1 - Q_1\sqrt{D})^k\;$
[since conjugation is multiplicitive]
$\;=\; (p_n + q_n\sqrt{D})^k (p_n - q_n\sqrt{D})^k
\;=\; ({p_n}^2 - D{q_n}^2)^k \;=\; (-1)^{nk}
\;=\; {p_{nk}}^2 - D{q_{nk}}^2.$
(6) Suppose that $\;\frac{p_{nk}}{q_{nk}} =\;$
the ratio $\;\frac{P_k}{Q_k}.$
Then, since $\;p_{nk}, q_{nk}, P_k,\;$ and $\;Q_k$ are all positive,
$\exists s>0 \ni (p_{nk}, q_{nk}) = (sP_k, sQ_k) \;\Rightarrow\;
{p_{nk}}^2 - D{q_{nk}}^2 = s^2({P_k}^2 - D{Q_k}^2).$
Therefore, by result (5), $\;(p_{nk}, q_{nk}) = (P_k, Q_k).$
..........................
Let $A$ denote the continued fraction
$\;[a_1, a_2, \cdots, a_n] = \frac{p_n}{q_n}.$
Let $B$ denote the continued fraction $\;[2a_1, a_2, \cdots, a_n].$
Then, $\;B = a_1 + \frac{p_n}{q_n}\;$ and
$\;\frac{p_{2n}}{q_{2n}} = \;$ the continued fraction represented by
$\;[A, B].$
Therefore, $\;\dfrac{Bp_n + p_{n-1}}{Bq_n + q_{n-1}} = \;$ the ratio $\;\dfrac{p_{2n}}{q_{2n}}.$
By the previous results, this leads to
$\dfrac{p_{2n}}{q_{2n}} \;=\; \dfrac{(a_1 + \frac{p_n}{q_n})p_n + (Dq_n - a_1p_n)} {{(a_1 + \frac{p_n}{q_n})q_n + (p_n - a_1q_n)}} \;=\; \dfrac{a_1p_n + \frac{{p_n}^2}{q_n} + Dq_n - a_1p_n} {a_1q_n + p_n + p_n - a_1q_n} $
$=\; \dfrac{{p_n}^2 + D{q_n}^2}{2p_nq_n} \;=\; \dfrac{P_2}{Q_2}.\;$ Therefore, by result (6), $\;(p_{2n}, q_{2n}) = (P_2, Q_2).$
(7) Thus, when $n>1,$ the conjecture is true for $k=2.$
..........................
Inductively assume that when $n>1,$ the conjecture is true for $\;\{1, 2, \cdots, k\}.$
$P_{k+1} + \sqrt{D}Q_{k+1} \;=\; (P_k + \sqrt{D}Q_k)(P_1 + \sqrt{D}Q_1)$
$=\; (P_kP_1 + DQ_kQ_1) + \sqrt{D}(P_kQ_1 + P_1Q_k)$
$=\;$ [by inductive assumption] $\;(p_{nk}p_n + Dq_{nk}q_n) + \sqrt{D}(p_{nk}q_n + p_nq_{nk}) \;\Rightarrow$
$(P_{k+1},Q_{k+1}) \;=\; (p_{nk}p_n + Dq_{nk}q_n, p_{nk}q_n + p_nq_{nk}).$
Let $C$ denote the continued fraction representation of $\;\dfrac{p_{nk}}{q_{nk}}.$
Then $\;\dfrac{p_{[n(k+1)]}}{q_{[n(k+1)]}} = \;$ the continued fraction represented by $\;[C, B].$
Therefore, $\;\dfrac{Bp_{nk} + p_{[(nk)-1]}}{Bq_{nk} + q_{[(nk)-1]}} = \;$ the ratio $\;\dfrac{p_{[n(k+1)]}}{q_{[n(k+1)]}}.$
By the previous results, this leads to
$\dfrac{p_{[n(k+1)]}}{q_{[n(k+1)]}} \;=\; \dfrac{(a_1 + \frac{p_n}{q_n})p_{nk} + (Dq_{nk} - a_1p_{nk})} {(a_1 + \frac{p_{n}}{q_n})q_{nk} + (p_{nk} - a_1q_{nk})} \;=\; \dfrac{a_1p_{nk} + \frac{p_np_{nk}}{q_n} + Dq_{nk} - a_1p_{nk}} {a_1q_{nk} + \frac{p_nq_{nk}}{q_n} + p_{nk} - a_1q_{nk}}$
$=\; \dfrac{p_np_{nk} + Dq_{nk}q_n}{p_nq_{nk} + p_{nk}{q_n}} \;=\; \dfrac{P_{k+1}}{Q_{k+1}}.\;$
Therefore, by result (6), $\;(p_{[n(k+1)]}, q_{[n(k+1)]}) = (P_{k+1}, Q_{k+1}).$
(8) Thus, when $n>1,$ the conjecture is true by induction.
..........................
$\underline{\text{case 2:} \;\; n=1}$
When $n=1, \;\sqrt{D} = [a_1, \overline{2a_1}].$
(9) Therefore, $\;(p_1, q_1) = (a_1, 1), \;(p_2, q_2) = (2{a_1}^2 + 1, 2a_1),\;$
and for $\;2\leq k \in\mathbb{Z^+}, \;(p_{k+1}, q_{k+1})
\;=\; (2a_1p_k + p_{k-1}, 2a_1q_k + q_{k-1}).$
$\sqrt{D} + a_1 = [\overline{2a_1}] \;=\; 2a_1 + \dfrac{1}{\sqrt{D} + a_1} \;\Rightarrow$
$D + {a_1}^2 + 2a_1\sqrt{D} = 2a_1\sqrt{D} + 2{a_1}^2 + 1 \;\Rightarrow\;$
(10) $\;D = {a_1}^2 +1.$
(11) From (9) and (10), $\;{p_1}^2 - D{q_1}^2 = -1.$
..........................
Let $R$ represent the continued fraction $\;[a_1, 2a_1, \cdots, 2a_1]\; ([k+1] $ elements).
This implies that $\;R = \frac{p_{k+1}}{q_{k+1}}.$
Let $\;S = \;$ the continued fraction represented by $\;[\overline{2a_1}] \;\Rightarrow S = a_1 + \sqrt{D}.$
Then $\sqrt{D} = \;$ the continued fraction represented by $\;[R, S].$
(12) Therefore, $\;\sqrt{D} \;=\; \dfrac{Sp_{k+1} + p_k}{Sq_{k+1} + q_k}.$
This is very similar to equation (4.39) given in Old-s_pdf, on page 114
(page 61/85 in the pdf file). That pdf's subsequent analysis will be paralleled
with result (12) above as the starting point and will lead to :
(13) When $n=1,\;$ and $\;k\geq 2:$
$p_k = Dq_{k+1} - a_1p_{k+1} \;$ and $\;q_k = p_{k+1} - a_1q_{k+1}.$
(14) Continuing the parallel analysis, result (13) will lead to
${p_k}^2 - D(q_k)^2 = (-1)^k.$
(15) The analysis and conclusions in results (5) and (6) from case 1 also
apply when $n=1.\;$ Therefore,
$\;{P_k}^2 - D{Q_k}^2 = (-1)^k = {p_k}^2 - D(q_k)^2.$
Therefore, $\;\frac{p_k}{q_k} = \frac{P_k}{Q_k} \;\Rightarrow\;
(p_k, q_k) = (P_k, Q_k).$
..........................
(16) From results (9) and (10) above, it is immediate that
$(p_2, q_2) = (2{a_1}^2 + 1, 2a_1) = ({a_1}^2 + D, 2a_1) = (P_2, Q_2).$
Inductively assume that when $n=1,\;$ the conjecture is true for $\;\{1, 2, \cdots, (k+1)\}.$
$P_{k+2} + \sqrt{D}Q_{k+2} \;=\; (P_{k+1} + \sqrt{D}Q_{k+1})(P_1 + \sqrt{D}Q_1)$
$=\; (P_{k+1}P_1 + DQ_{k+1}Q_1) + \sqrt{D}(P_{k+1}Q_1 + P_1Q_{k+1})$
$=\;$ [by inductive assumption] $\;(p_{k+1}a_1 + Dq_{k+1}) + \sqrt{D}(p_{k+1} + a_1q_{k+1}) \;\Rightarrow$
$(P_{k+2},Q_{k+2}) \;=\; (p_{k+1}a_1 + Dq_{k+1}, p_{k+1} + a_1q_{k+1}).$
..........................
Let $T$ denote the continued fraction representation of $\;\dfrac{p_{k+1}}{q_{k+1}}.$
Then $\;\dfrac{p_{k+2}}{q_{k+2}} = \;$ the continued fraction represented by $\;[T, 2a_1].$
Therefore, $\;\dfrac{2a_1p_{k+1} + p_k}{2a_1q_{k+1} + q_k} = \;$ the ratio $\;\dfrac{p_{k+2}}{q_{k+2}}.$
Using result (13), this leads to
$\dfrac{p_{k+2}}{q_{k+2}} \;=\; \dfrac{2a_1p_{k+1} + (Dq_{k+1} - a_1p_{k+1})}{2a_1q_{k+1} + (p_{k+1} - a_1q_{k+1})} \;=\; \dfrac{a_1p_{k+1} + Dq_{k+1}} {a_1q_{k+1} + p_{k+1}} \;=\; \dfrac{P_{k+2}}{Q_{k+2}}.\;$
Therefore, by result (15), $\;(p_{k+2}, q_{k+2}) = (P_{k+2}, Q_{k+2}).$
(17) Thus, when $n=1,$ the conjecture is also true by induction.