Number bases $p$

Question

I did not understand the proof of this lemma, could anyone help me?

Lemma. Let $p\in\mathbb{N}$, $p\ge2$. Let $x\in[0,1)$ such that \begin{equation} x=\sum_{k=1}^{\infty}\frac{a_k}{p^k}=\sum_{k=1}^{\infty}\frac{b_k}{p^k} \end{equation} with two distinct sequences $\{a_k\}$, $\{b_k\}\subseteq\mathbb{N}$, $0\le a_k\le p-1$, $0\le b_k\le p-1$ for all $k\in \mathbb{N}$.

Then exists $n\in\mathbb{N}$ such that $a_k=0$, $b_k=p-1$ for all $k\ge n+1$.

Proof. We place $a_0=b_0=0$. By hypothesis exists $n\in\mathbb{N}$, $n\ge1$ such that \begin{equation} \begin{split} a_k&=b_k\quad \text{for all}\quad k=1,\dots,n-1 \\ a_n &\ge b_n+1 \end{split} \end{equation} (Why?)

Therefore:

\begin{equation} x-\sum_{k=1}^{n-1}\frac{a_k}{p^k}\ge\frac{a_n}{p^n}\ge\frac{b_n+1}{p^n}\ge\sum_{k=1}^{n-1}\frac{b_k}{p^k} \end{equation} (why?).

Then, \begin{equation} \begin{split} \sum_{k=n}^{\infty}\frac{a_k}{p^k} =& \frac{a_n}{p^n} \\ \sum_{k=n}^{\infty}\frac{b_k}{p^k} =& \frac{b_n+1}{p^n}. \end{split} \end{equation}

(why?)

then the thesis (why?)

Thanks!

Answer 1

By hypothesis exists $n\in\mathbb{N}$, $n\ge1$ such that \begin{equation} \begin{split} a_k&=b_k\quad \text{for all}\quad k=1,\dots,n-1 \\ a_n &\ge b_n+1 \end{split} \end{equation}

It is given that the two sequences are different. Two sequences are equal if all the corresponding entries are equal, so if the sequences are different then there must be some specific element $a_n$ that differs from the corresponding element $b_n$. For this proof we choose $n$ to be as small as possible, i.e. it is the first index where the sequences differ.

$a_n$ and $b_n$ differ, and they are integers. Therefore either $a_n \ge b_n+1$ or $b_n \ge a_n+1$. The rest of the proof works just as well in the latter case, but with the letters $a$ and $b$ switched throughout. So we may as well assume the former, i.e. that $a_n \ge b_n+1$.

Therefore: \begin{equation} x-\sum_{k=1}^{n-1}\frac{a_k}{p^k}\ge\frac{a_n}{p^n}\ge\frac{b_n+1}{p^n}\ge x-\sum_{k=1}^{n-1}\frac{b_k}{p^k} \end{equation}

I've added the an $x$ on the rhs that you accidentally left out.

The first inequality: $$ x-\sum_{k=1}^{n-1}\frac{a_k}{p^k} = \sum_{k=1}^{\infty}\frac{a_k}{p^k} -\sum_{k=1}^{n-1}\frac{a_k}{p^k}\\ = \sum_{k=n}^{\infty}\frac{a_k}{p^k}\\ = \frac{a_n}{p^n} + \sum_{k={n+1}}^{\infty}\frac{a_k}{p^k} \ge \frac{a_n}{p^n} $$

So after subtracting the start of the series, you're left with the infinite tail starting at the $n$th term. Since all the terms are non-negative, leaving out all but the first term will result in a number that is smaller (or equal).

The middle inequality comes from the previous section where $a_n \ge b_n+1$.

The last inequality is similar to the first but in the opposite direction using sequence $b$:

$$ x-\sum_{k=1}^{n-1}\frac{b_k}{p^k} = \frac{b_n}{p^n} + \sum_{k={n+1}}^{\infty}\frac{b_k}{p^k} \\ \le \frac{b_n}{p^n} + \sum_{k={n+1}}^{\infty}\frac{p-1}{p^k} $$

So again after subtracting the start of the series ($b$ this time), you're left with the infinite tail starting at the $n$th term. Since all the numbers $b_k$ in that tail are at most $p-1$, so that tail would only get bigger if we replace those $b_k$ by $p-1$. If you work out that final geometric sum you get:

$$ x-\sum_{k=1}^{n-1}\frac{b_k}{p^k} \le \frac{b_n}{p^n} + \sum_{k={n+1}}^{\infty}\frac{p-1}{p^k}\\ = \frac{b_n}{p^n} + \frac{1}{p^n} = \frac{b_n+1}{p^n} $$

Then, \begin{equation} \begin{split} \sum_{k=n}^{\infty}\frac{a_k}{p^k} =& \frac{a_n}{p^n} \\ \sum_{k=n}^{\infty}\frac{b_k}{p^k} =& \frac{b_n+1}{p^n}. \end{split} \end{equation}

We know that $a_k=b_k$ for all $k=1,\dots,n-1$ so the left side and the right side of that compound inequality are actually equal:

\begin{equation} x-\sum_{k=1}^{n-1}\frac{a_k}{p^k} = x-\sum_{k=1}^{n-1}\frac{b_k}{p^k} \end{equation}

That means that they must all be equal. (i.e. if $r \le s \le t$ and $r=t$ then we have $r=s=t$). \begin{equation} x-\sum_{k=1}^{n-1}\frac{a_k}{p^k} = \frac{a_n}{p^n} = \frac{b_n+1}{p^n} = x-\sum_{k=1}^{n-1}\frac{b_k}{p^k} \end{equation}

then the thesis

The inequalities becoming equalities means that when we left out the $a$-tail the value did not change, hence the $a_k$ on that tail were all already zero. Similarly changing the $b$-tail to all have value $p-1$ also changed nothing, so the $b_k$ where alrady $p-1$.

Answer 2

HINT.-I do not want to give you an answer to your four (why?) but a guide for you to find it yourself.

Remember that in base $10$ you have $1=1.000000.....=0.999999......$. This can be shifted to a decimal place. For example $$0.123=0.122+0.001=0.122+0.00099999999.....=0.12299999999......$$ On the other hand, you do have $0.123=0.12300000000.....$ so you have

$$\begin{equation} 0.123=0.12300000000.....=0.12299999999......\sum_{k=1}^{\infty}\frac{a_k}{10^k}=\sum_{k=1}^{\infty}\frac{b_k}{10^k} \end{equation}$$ where $a_k$ and $b_k$ are here "our" usual digits from $0$ to $9$.

Remember too that in base $p$ all (positive of course) integer smaller that $p$ is a "digit" and that $p$ is the first non digit and written $p=10_{(p)}$.