Sejam m=\left(r_{n} r_{n-1} \ldots r_{0}\right)_{b}, m^{\prime}=\left(s_{n^{\prime}}, s_{n^{\prime}-1} \ldots s_{0}\right)_{b}. Provar que, se n<n^{\prime}, então m<m^{\prime}. Dar um critério para comparar m e m^{\prime} em geral.
Passo 1
Enunciado reescrito e dados fornecidos: temos dois números escritos na base b,
Aqui cada termo r_i b^i representa a contribuição do dígito r_i na posição de peso b^i. Como r_n e s_{n'} são não nulos, b^n e b^{n'} são as potências mais altas que aparecem.
Passo 3
Limite superior para m: como cada r_i \le b-1, temos
m \le \sum_{i=0}^{n} (b-1)b^i = (b-1)\sum_{i=0}^{n} b^i.
Recordando a soma da progressão geométrica, para b\neq 1,
\sum_{i=0}^{n} b^i = \frac{b^{n+1}-1}{b-1}.
Substituindo,
m \le (b-1)\cdot\frac{b^{n+1}-1}{b-1} = b^{n+1}-1.
Portanto obtemos o limite útil
m \le b^{n+1}-1.
Passo 4
Limite inferior para m': como s_{n'}\ge 1 (dígito mais significativo não zero), a menor contribuição possível da casa mais significativa é 1\cdot b^{n'}. Assim
m' \ge b^{n'}.
Passo 5
Comparando as potências quando n<n': como n<n' implica n+1 \le n', e para b\ge 2 temos b^{n+1} \le b^{n'}. Daí
b^{n+1}-1 < b^{n'}.
(Explicação rápida: b^{n+1}\le b^{n'} e subtraindo 1 de b^{n+1} fica estritamente menor que b^{n'}.)
Passo 6
Concluindo a primeira parte: juntando os resultados dos passos anteriores temos
m \le b^{n+1}-1 < b^{n'} \le m'.
Logo m < m'. Isso prova a afirmação pedida: se n<n' então m<m'.
Passo 7
Agora o critério geral de comparação (ideia antes da prova formal): comparar primeiro o número de dígitos (isto é, n vs n'). Se forem diferentes, o número com mais dígitos é maior. Se tiverem o mesmo número de dígitos (n=n'), comparar os dígitos da esquerda (mais significativos) para a direita até achar o primeiro dígito diferente — aí o sinal desse dígito diferente determina qual número é maior. A seguir faço a prova limpa desse critério.
Passo 8
Prova formal do critério quando n=n': suponha n=n'. Se todos os dígitos forem iguais, r_i=s_i para todo i e então m=m'. Caso contrário, existe um índice k tal que r_k\ne s_k; escolha k como o maior índice onde diferem (isto é, o mais significativo diferente). Então para todo i>k temos r_i=s_i, e para i=k temos r_k\ne s_k. Escrevemos a diferença
Logo o resto tem magnitude estritamente menor que b^k. Assim se r_k-s_k>0 então
m-m' \ge 1\cdot b^k - (b^k-1) = 1,
portanto m>m'. Se r_k-s_k<0 então
m-m' \le -1\cdot b^k + (b^k-1) = -1,
portanto m<m'. Isso mostra que o sinal de m-m' é o sinal de r_k-s_k: o dígito mais significativo distinto determina qual número é maior.
Passo 9
Resumo do critério prático (o que usar na prova ou em um exercício, passo a passo):
Compare n e n' (número de dígitos menos 1). Se n<n' então m<m'. Se n>n' então m>m'.
Se n=n', procure o maior índice k tal que r_k\ne s_k. Então:
se r_k<s_k temos m<m';
se r_k>s_k temos m>m';
se não existe tal k (todos os dígitos iguais) então m=m'.
Exemplos rápidos: na base 10, 99<100 porque 99 tem menos dígitos; e 345<367 porque ambos têm 3 dígitos, o primeiro dígito igual 3, o segundo difere com 4<6.
Resposta
Se n<n' então m<m'.\nCritério geral: se n<n' então m<m'; se n>n' então m>m'. Se n=n' então tome o maior índice k com r_k\ne s_k; o sinal de r_k-s_k determina a comparação: se r_k<s_k então m<m', se r_k>s_k então m>m', e se não existir tal k então m=m'.