0

I am wondering how to prove (1) $b + b^2 + ... + b^{n - 1} < b^n$ for all $b, n \in \{2, 3, ...\}$ and more generaly (2) $a_1b + a_2b^2 + ... + a^{n - 1}b^{n - 1} < b^n$ when $a_i \in \{0, 1, .., b - 1\}, (a_1 \neq 0)$.

I am studying number systems more deeply so I find this question interesting. For example, in base 10: $1 + 10 + 100 + ... + 10 000 = 11 111 < 10^5$ and this obvious in our minds.

But what about other bases, to me this $1 + 10_{(3)} + 100_{(3)} + ... + 10 000_{(3)} = 11 111 < 10^5_{(3)}$ is not obvious at all!

And, for example, how to prove $1 000_{(3)} > 222_{(3)}$?

Infact it's enough to prove $\overline{a_1a_2...a_n}_{(b)} < 10^{n + 1}_{(b)}$ when $a_1 = a_2 = ... = a_n = b - 1$ for every $b \in \{2, 3, ...\}$. In words: biggest $n$-digit number is smaller then smallest $n + 1$-digit number in any base $b$. Thanks!

1b3b
  • 1,276
  • 1
    Well the Left hand side seems like a geometric sum, which you have an identity for. Have you tried doing that? – Keen-ameteur Oct 04 '20 at 09:57
  • Nope I didn't study series and sums... – 1b3b Oct 04 '20 at 10:02
  • 1
    $999_{(3)}$ is not a legit number. – cr001 Oct 04 '20 at 10:04
  • Oh yes... I will fix that – 1b3b Oct 04 '20 at 10:05
  • 1
    And you can prove $1 000_{(3)} > 222_{(3)}$ by doing the subtraction algorithm for $1 000_{(3)} - 222_{(3)}$. It's easy to see the result is positive and this can be generalized to any base. – cr001 Oct 04 '20 at 10:06
  • I'm pretty sure you've learned about sums at some point. But the proof of the geometric sum is fairly simple and can be done by induction. Look at https://en.wikipedia.org/wiki/Geometric_series#Formula – Keen-ameteur Oct 04 '20 at 10:06
  • Like in the decimal system, also in every other $b$ - base system ($b\ge 2$ integer) , every number is larger than any number with fewer digits. – Peter Oct 04 '20 at 10:09
  • $Peter, can you please prove that in your answer? – 1b3b Oct 04 '20 at 10:21

2 Answers2

2

It's enough to show that $$ \sum_{i=1}^{n-1} (b-1)\cdot b^{^i}< b^n. $$

Using the geometric sum formula you have an explicit expression for the left hand side

$$ \sum_{i=1}^{n-1} (b-1)\cdot b^{^i}=(b-1)\sum_{i=1}^{n-1} b^{^i}<(b-1)\cdot \frac{b^n-1}{b-1}=b^n-1<b^n $$

Keen-ameteur
  • 7,663
  • Shouldn't the sum start with $i = 0$? – 1b3b Oct 17 '20 at 21:39
  • 1
    It can, but when I wrote I didn't think the sum includes $1$ for some reason. If the sum starts from $i=0$, then the strict inequality is replaced by a weak inequality. – Keen-ameteur Oct 18 '20 at 08:39
0

I found elegant and simple solution to my own problem. I also proved at the end the famous sum (without mathematical induction!).

Suppose we have base $b$ for our needs. Then, $\{x_0 := 0, x_1 := 1, ..., x_n := b - 1\}$ is set of symbols we will use to denote some natural number with $n$ digits in a base $b.$

Now, we want to prove that biggest $n$-digit number A = $\overline{x_nx_n...x_n}$ is smaller then the smallest $(n + 1)$-digit number $B = \overline{100...0}$. Infact we will prove that $A = B - 1.$ That's easy:

Because of $x_n = b - 1$ we want to prove $(b - 1)b^0 + (b - 1)b + ... + (b - 1)b^n = b^{n + 1} - 1.$

LHS is equal to $(b - 1) + (b^2 - b) + (b^3 - b^2) + ... + (b^{n + 1} - b^n).$ So, of course after cancelling we get our result.

And one can observe the following: The Legend of chess mentions the sum $1 + 2 + 4 + ... + 2^{63} = 2^{64} - 1$. This can be proven in general case by tehnique given above. Observe that the sum $2^0 + 2^1 + ... + 2^{n - 1}$ is equal to $(2 - 1)2^0 + (2 - 1)2 + ... + (2 - 1)2^{n - 1} = 2^{n} - 1$ and hence the result. Also, notice that on the LHS we have $\overline{11...1}$ ($\text{n ones}$) and on the RHS we have $\overline{100...0}$ ($\text{n zeros}$).

1b3b
  • 1,276