# 1+1/2+1/3+ +1/n<80 if u.=>

1. Mar 29, 2004

### quddusaliquddus

1+1/2+1/3+...+1/n<80 if u.......=>

prove:

1 + 1/2 + 1/3 + .. + 1/n<80 if you eliminate terms with 9 as a digit in its denominater?

Generalise to deleting other digits in denom.?

2. Mar 29, 2004

### quddusaliquddus

Anyone out there who can help?.....please?......

3. Mar 30, 2004

### Janitor

No matter how big n is?

Can't guide you on this, but was your source reliable? Do you mean that 1/19, for instance, is excluded from the sum because it has a 9 in the 19?

4. Mar 30, 2004

### quddusaliquddus

yes. that is what was meant im afraid.

5. Mar 30, 2004

### Zurtex

Hmm, been thinking about this now, because you need to proove that this sum is always less than 80 is not the same as:

$$\sum_{n=1}^{\infty}{ \left( \frac{1}{n} \right)} - \sum_{n=1}^{\infty} \left( \frac{1}{10n-1} \right)$$

Last edited: Mar 30, 2004
6. Mar 30, 2004

### matt grime

The only problem there is that you are asuming that the sums converge so that you can rearrange the summation.

I think a possible proof goes along the lines:

take the fisrt 8 terms:

1+1/2+...+1/8 < 8

then take the valid terms with two digits in the denominator:

1/10+1/11+...+1/88 < 72/10 72 possible terms, all less than or equal to 1/10

now it would be nice, but I've not counted if there were 72*9 terms with 3 digits in the denominator in the sum cos we can replace them with 72*9/100

Then we can bound above by a gp if this continues and get a bound of 8/(1-9/10) = 80

Last edited: Mar 30, 2004
7. Mar 30, 2004

### Chen

Zurtex, that's only for the terms 1/9, 1/19, 1/29, etc. What about 1/90, 1/91, 1/92, etc?

8. Mar 30, 2004

### uart

I've got an idea that just might work with this, especially as you're only after an upper bound.

Say you just look at how many terms in the sum are excluded (and hence how many are included) for each "decade" (eg 1..9, 10..99, 100,999, etc) and then place an upper bound on each "decade" sum as the number of terms included in each "decade" times the maximum sum term within that decade.

For example, in the "decade" from 1000 to 9999 there are only 5832 terms so the an upper bound would be 5.832

PS: Not sure if "decade" is really the best word to describe the intervals I'm using but I hope everyone knows what I mean. :)

Last edited: Mar 30, 2004
9. Mar 30, 2004

### matt grime

I think that if you've counted correctly, you've done some of the leg work for my proof above (that appeared lafter fist bein posted) as 5000 is about 72*18 as I'd require

10. Mar 30, 2004

### uart

Just running with that idea a bit more. You can easily make an acurrate sum of the first few "decades" without invoking any upper bounds. This will reduce the size of the overall upper bound you come up with. But eventually you'll need to just bound each "decade" as described above.

Here's my rough calc of the number of terms exluded in each decade. You need to make some sort of series out of this and get a closed form expression to use in the infinite sum. Should be do-able I think.

1..9 : 1 = 1 of 9 excluded
10..99 : 8*1 + 10 = 18 of 90
100..999 : 8*(1+18) + 100 = 252 of 900
1000..9999 : 8*(1+18+252) + 1000=3168 of 9000 etc

Last edited: Mar 30, 2004
11. Mar 30, 2004

### uart

Yeah Matt, I didn't see your post until after I posted mine, but I think we are both looking at pretty much the same idea. :)

12. Mar 31, 2004

### uart

OK I've got this one fully sorted now. It's actually much easier to count the "not contain 9's" direct rather than count the "contain 9's" as I did above.

The number of numbers that don't contain the digit "9" in each power of 10 range is quite easy to track as follows.

0..9 : 9 numbers (*see note)
10..99 : 9*8 numbers
100..999 : 9*8*8 numbers
1000..9999 : 9*8^3 etc

Note: I included zero in the first group just to help make the pattern consistant.

So the upper bound to the sum of all the terms that don't contain "9" is simply :

UB = 9 * ( 1 + 0.8 + 0.8^2 + 0.8^3 + ....)
= 45

As I suggested earlier this upper bound can be made a bit tighter by just manually summing some of the early terms in the series and postponing the upper bound sum a little. For example if you sum all the terms up to 1/8 then you can immediately reduce the upper bound by 9 - Sum(1/1, 1/2, ... 1/8) which reduces the upperbound to under 39

13. Mar 31, 2004

### quddusaliquddus

Im sorry i dont understand. Does this prove that by throwing out all these terms with 9 as denom, the UB of the original sum (1 + 1/2 + 1/3 + ... + 1/n) is 80?

14. Mar 31, 2004

### matt grime

No, that it is bounded above by 80 for any n.

15. Mar 31, 2004

### quddusaliquddus

what about using the formula for 1/1 + 1/2 + ... + 1/n (n<>infinity), and substracting the formulae for 1/9+1/19+1/29+... + 1/90 + 1/91 + ... + 1/99 + 1/109 + ...?

16. Mar 31, 2004

### matt grime

Which formula are these? I know of none for how to sum the first n reciprocals nor do I know a formula for the sum of all the reciprocals of natural numbers less than n which have at least one 9 in their decimal representation

17. Mar 31, 2004

### quddusaliquddus

i think while working on another problem, i cam across the first sum you just mentioned - unfortunately i've lost it. I have never come across the second one though. Sorry-its not too helpful

18. Mar 31, 2004

### NateTG

Chiming in here:

Of the first $$n$$ numbers, approximately $$n * (\frac{9}{10})^{\log_{10}(n)}$$ do not contain $$9$$:

1:1
10:9 (missing 9)
100:81 (missing 9 19 29 39 49 59 69 79 89 90 91 92 93 94 95 96 97 98 99)
1000:729 (missing 19*9 (each of the non-9 leading digits incl. 0) + 100 = 271)
and so on.

Now:
$$\log_2(2n)\geq \sum_{i=1}^{n}\frac{1}{n}\geq \log_2(n)$$
since
$$\frac{1}{2} \leq \sum_{i=2^{n-1}}^{2^n}\frac{1}{n} \leq 1$$
(Consider that there are $$2^{n-1}$$ terms each of which is less than or equal to $$\frac{1}{2^{n-1}}$$ and greater than or equal to $$\frac{1}{2^{n}}$$)

For convenience, let's define
$$f:\mathbb{N} \rightarrow \{0,1\}$$ with $$f(x)=1$$ iff $$x$$ contains 9
Then for $$n$$ a power of 10 we have:
$$\sum_{i=1}^{n}\frac{f(i)}{n} \geq \sum_{i=1}^{\log_{10}n} \frac{1}{9^i} \sum_{j=1}^{\frac{n}{10^i}} \frac{1}{n}> \sum_{i=1}^{\log_{10}n} \frac{1}{9^i} (\log_2{n}- i log_2(10))$$

Which is a fairily tight approximation. If you simplify it, you might be able to get your proof.

19. Mar 31, 2004

### quddusaliquddus

....Digesting......

lemme take all that in.

20. Mar 31, 2004

### uart

Yes it proves that the sum can be no more than 45, so therefore it can also be no more than 80. You can show it is no more than 39 by just doing a tiny bit more work and you can even show that it is no more than 26.7 by exactly summing the terms below 10^4 and using the bounding function for terms 10^4 and greater.

But you dont have a formula for these, that's the whole point of finding a "bound". When you cant figure out how to sum something exactly then the next best thing is to try and find something easier to sum but which you at least know is always as large or larger than the original thing. That is, you cant find the sum but you can say with certainty that is is not greater than X (eg 80 or whatever the case may be).

The bounding approximation that I'm using is 1/1 + 1/1 + 1/1 +...1/1 for all no_digit_nine numbers less than ten, 1/10 + 1/10 + 1/10 + ...1/10 for all no_nine_digit numbers between ten and 99 etc etc. You see how it works, it's much easier than the original sum and is always at least as big or bigger, so it leads to a bound.