This is an exercise from "Topics in the theory of numbers" from the chapter on Diophantine Approximation
Let $b=\left(b_1,b_2,\dots,b_s\right)$ be a sequence of digits ($b_i=0,1,\dots,9$). We say that a number $a$ does not contain $b$ if in base-10 notation, the elements of $b$ do not occur in their given order as consecutive digits of $a$. Prove that if $\left(a_1,a_2,\dots\right)$ is a sequence of distinct numbers for which none of the elements contain $b$, then the sum $$\sum_{i=1}^n\frac{1}{a_i}$$ is smaller than some constant not depending on $n$
For the poof let
- $A=\{a_i:a_i\text{ has less than $s$ digits}\}$ so $card(A)\le10^{s-1}$
- $B=\{a_i:a_i\text{ has $s$ digits and }a_i\ne b\}$ so $card(B)\le10^s-1$
- $C_k=\{a_i:a_i\text{ has $s+k$ digits and $a_i$ does not contain $b$}\}$. How can $card(C_k)$ be bounded?
Now both $A$ and $B$ are finite so given that $$\sum_{i=1}^n\frac{1}{a_i}=\sum_{a_i\in A}\frac{1}{a_i}+\sum_{a_i\in B}\frac{1}{a_i}+\sum_{k=1}^m\sum_{a_i\in C_k}\frac{1}{a_i}$$ it is clear that $\sum_{a_i\in A}\frac{1}{a_i}+\sum_{a_i\in B}\frac{1}{a_i}$ is finite and smaller than $10^{s-1}+1-10^{-s}$
If I had a good enough bound $f(k)$ for $card(C_k)$ it could be proved that $$\sum_{k=1}^m\sum_{a_i\in C_k}\frac{1}{a_i}\le\sum_{k=1}^m\frac{f(k)}{10^{s+k}}$$ converges to some positive number as $m\to\infty$
Is the proof correct (supposing that such bound exists)? I'm not sure the "divide the sequence into three disjoint sets and sum them separately" is rigorous at all. I don't know much combinatorics so please explain in some answer how to get a bound (good or bad). I only know $f(k)=10^{s+k}-10^k(k+1)$ for $k=1,2,\dots,s-1$. Thanks
You can reorder an infinite sum as long as it is absolutely convergent, which means it converges when you take the absolute value of all the terms. In this case all the terms are positive, so if it converges you can reorder it any way you want. In the above argument you are summing the terms in exactly the order they are given in the original sum. Set $A$ comes first, then $B$, then the $C_k$ in order of $k$.
$f(k)=10^{s+k}-10^k(k+1)$ for $k \lt s$ can be justified by saying there are $10^{s+k}$ numbers with $s+k$ digits when we allow a leading zero. We want to subtract those that have the disallowed digit string. There are $k$ positions that the digit string can start in and $10^k$ choices for the other digits, so $k10^k$ disallowed numbers. This leaves $10^{s+k-1}-k10^k$ allowable numbers, not quite the claimed count. This works for $k \lt s$ because you can't have two copies of the disallowed string. When $k \ge s$ you can and numbers that have it twice will get counted twice. We need to apply inclusion-exclusion once we get this large.