Leigh.Samphier/Sandbox/Canonical P-adic Expansion of Rational is Eventually Periodic/Lemma 5

From ProofWiki
Jump to navigation Jump to search



Theorem

Let $p$ be a prime.

Let $b \in Z_{> 0}$ such that $b, p$ are coprime.

Let $\sequence{d_n}$ be a sequence of $p$-adic digits.

Let $\sequence{r_n}$ be a sequence of integers:

$(\text a) \quad \forall n \in \N: r_n = d_n b + p r_{n+1}$
$(\text b) \quad \exists n_0 \in \N : \forall n \ge n_0 : -b \le r_n \le 0$


Then:

$\exists \mathop m, l \in \N : \forall n \ge m: r_n = r_{n + l}$ and $d_n = d_{n + l}$


Proof

By hypothesis the sequence $\sequence{r_n}$ takes only finitely many values.

Hence:

$\exists m, l \in \N : l > 0 : r_m = r_{m+l}$


Lemma 10

Let:

$n, k \in \N : r_n = r_{n + k}$


Then:

$d_n = d_{n + k}$


The proof now proceeds by induction.

For all $n \ge m$, let $\map P {n}$ be the proposition:

$r_n = r_{n+l}$ and $d_n = d_{n + l}$

Basis for the Induction

$\map P {m}$ is the proposition:

$r_m = r_{m+l}$ and $d_m = d_{m + l}$


It has already been shown that:

$r_m = r_{m+l}$

From lemma 10:

$d_m = r_{m+l}$

This proves proposition $\map P {m}$.

$\Box$


Induction Hypothesis

Let $n \ge m$.

The induction hypothesis is the proposition $\map P {n}$:

$r_n = r_{n+l}$ and $d_n = d_{n + l}$

It has to be shown that the proposition $\map P {n+1}$ is true:

$r_{n + 1} = r_{n + l + 1}$ and $d_{n + 1} = d_{n + l + 1}$


Induction Step

We have:

\(\ds d_n b + p r_{n + 1}\) \(=\) \(\ds r_n\) Theorem hypothesis
\(\ds \) \(=\) \(\ds r_{n+l}\) Induction hypothesis
\(\ds \) \(=\) \(\ds d_{n+l} b + p r_{n + l + 1}\) Theorem hypothesis
\(\ds \leadsto \ \ \) \(\ds p \paren{ r_{n + l + 1} - r_{n + 1} }\) \(=\) \(\ds \paren {d_n - d_{n + l} }b\) Rearranging terms
\(\ds \) \(=\) \(\ds 0\) Induction hypothesis
\(\ds \leadsto \ \ \) \(\ds r_{n + 1}\) \(=\) \(\ds r_{n + l + 1}\)

From lemma 10:

$d_{n + 1} = d_{n + l + 1}$

$\Box$


Hence:

$\forall n \ge m: r_n = r_{n + l}$ and $d_n = d_{n + l}$

The result follows.

$\blacksquare$