How can deleting specific digits affect the bounds on the harmonic series?

[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.?

 

[quddusaliquddus]

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

 

[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?

 

[quddusaliquddus]

yes. that is what was meant I am afraid.

 

[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:

[tex]\sum_{n=1}^{\infty}{ \left( \frac{1}{n} \right)} - \sum_{n=1}^{\infty} \left( \frac{1}{10n-1} \right) [/tex]

 

[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

 

[Chen]

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

 

[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. :)

 

[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

 

[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

 

[uart]

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

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. :)

 

[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

 

[quddusaliquddus]

Im sorry i don't 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?

 

[matt grime]

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

 

[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 + ...?

 

[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

 

[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

 

[NateTG]

Chiming in here:

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

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:
[tex]\log_2(2n)\geq \sum_{i=1}^{n}\frac{1}{n}\geq \log_2(n)[/tex]
since
[tex]\frac{1}{2} \leq \sum_{i=2^{n-1}}^{2^n}\frac{1}{n} \leq 1 [/tex]
(Consider that there are [tex]2^{n-1}[/tex] terms each of which is less than or equal to [tex]\frac{1}{2^{n-1}}[/tex] and greater than or equal to [tex]\frac{1}{2^{n}}[/tex])

For convenience, let's define
[tex]f:\mathbb{N} \rightarrow \{0,1\}[/tex] with [tex]f(x)=1[/tex] iff [tex]x[/tex] contains 9
Then for [tex]n[/tex] a power of 10 we have:
[tex]\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))[/tex]

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

 

[quddusaliquddus]

...Digesting...


lemme take all that in.

 

[uart]

Im sorry i don't 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?

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.

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 + ...?

But you don't have a formula for these, that's the whole point of finding a "bound". When you can't 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.

 

[quddusaliquddus]

ok. I'll try and work on this a little bit more with what you guys have posted and other materials.

 

[NateTG]

As can be inferred from my post above, the harmonic series:
[tex]\sum_{i=1}^{\infty} \frac{1}{i}[/tex]
is divergent.

Uart's approach is correct, although his calculation for terms containing 9 is off.

There are [tex]9^i - 9^{i-1}=8 \times 9^{i-1}[/tex] [tex]i[/tex]-digit numbers that do not contain [tex]9[/tex]. Uart had [tex]9\times8^{i-1}[/tex]

If you bound each of those numbers by the lower bound [tex]10^{i-1}[/tex] then you get:
[tex]\sum_{i=1}^{n}\frac{n}{f(n)} < \sum_{i=1}^{1+\log_{10}n} \frac{1}{10^{i-1}} \times (9^i-9^{i-1})=[/tex]
[tex]9 \sum_{i=1}^{\log_{10}n} (\frac{9}{10})^i - \frac{10}{9} \sum_{i=1}^{\log_{10}n} (\frac{9}{10})^i [/tex]
[tex] \frac{71}{9} \times \sum_{i=1}^{\log_{10}n} (\frac{9}{10})^i [/tex]
Now take the limit
[tex] \frac{71}{9} \times \frac{10}{1} = \frac{710}{9} < \frac{720}{9} = 80[/tex]

 

[quddusaliquddus]

Explanation

Thats great!




Cant thank you enough! Now i'll start learning the stuff-and hopefully work out a formula for a general digit being thrown out.

 

[matt grime]

Hey, page 1 post 6. Stop nicking my proofs! (insert some smilie here)

 

[quddusaliquddus]

OK Matt ...

The smilies are on me ...

 

[Janitor]

Qudd,

I am mightily impressed by these fellows here!

Be sure to let us know the results you get for the other nine cases.

Does anybody know of other neat ways of subtracting things from the harmonic series to get finite results? (This reminds me a tad of the way physicists "renormalize" to subtract an infinite amount from an infinite amount to get a finite amount.)

 

[NateTG]

Hey, page 1 post 6. Stop nicking my proofs! (insert some smilie here)

You and Uart can duke it out for credit

 

[uart]

... Now i'll start learning the stuff-and hopefully work out a formula for a general digit being thrown out.

I am mightily impressed by these fellows here!
Be sure to let us know the results you get for the other nine cases.

It's exactly the same for the other 8 cases where the digit that's disgarded is other than zero (I think zero might be special case) . The actual sums will presumably have different values but the bounding process used for the "no nines" case can easily be use for the other 8 cases.

While not really a special case, if we choose terms containing the digit "1" to be disgarded then it's pretty easy to cut bound in half (to 40) by noting that the largest term in each of the "power of ten" groupings is 1/2, 1/20, 1/200, 1/2000 etc.

Uart had 9*8^(i-1) instead of 8*9^(i-1) ...

Thanks Nate. Yeah I realized that I'd counted them incompletely and got that corrected expression above after I'd logged off late last night. :)

 

[quddusaliquddus]

What do you guys think of this?

In [10^n,10^{n+1}), there are 8*9^n integers with no 9 digits. The sum
of the reciprocals of these numbers is less than 8*(9/10)^n (the number
of integers divided by the smallest). Summing this for n >= 0, we get
that the sum is less than 80.

 

[quddusaliquddus]

...help...

Sorry guys. I'm hopeless at this. I don't know how the calculation happened beloew:

As can be inferred from my post above, the harmonic series:
[tex]\sum_{i=1}^{\infty} \frac{1}{i}[/tex]
is divergent.

Uart's approach is correct, although his calculation for terms containing 9 is off.

There are [tex]9^i - 9^{i-1}=8 \times 9^{i-1}[/tex] [tex]i[/tex]-digit numbers that do not contain [tex]9[/tex]. Uart had [tex]9\times8^{i-1}[/tex]

If you bound each of those numbers by the lower bound [tex]10^{i-1}[/tex] then you get:
[tex]\sum_{i=1}^{n}\frac{n}{f(n)} < \sum_{i=1}^{1+\log_{10}n} \frac{1}{10^{i-1}} \times (9^i-9^{i-1})=[/tex]
[tex]9 \sum_{i=1}^{\log_{10}n} (\frac{9}{10})^i - \frac{10}{9} \sum_{i=1}^{\log_{10}n} (\frac{9}{10})^i [/tex]
[tex] \frac{71}{9} \times \sum_{i=1}^{\log_{10}n} (\frac{9}{10})^i [/tex]
Now take the limit
[tex] \frac{71}{9} \times \frac{10}{1} = \frac{710}{9} < \frac{720}{9} = 80[/tex]

That's why I'm having hard time moving onto the other digits. I don't mean to be lazy...it's just that this is way beyond me.

 

[quddusaliquddus]

OK guys. Sorry to bring up an old topic. I've struggled with this. Can someone please explain to me how you get:
====================================
n
log_2(2n)>=sigma(1/n) >=log_2(n)
i=1

2^n
since 1/2 <= sigma(1/n)<=1
i=(2^n)-1
====================================

Please?

 

[NateTG]

OK guys. Sorry to bring up an old topic. I've struggled with this. Can someone please explain to me how you get:
====================================
n
log_2(2n)>=sigma(1/n) >=log_2(n)
i=1

2^n
since 1/2 <= sigma(1/n)<=1
i=(2^n)-1
====================================

Please?

Quick and dirty bounds:
[tex]\sum_{i=2^n}^{2^{n+1}} \frac{1}{2^n} \geq \sum_{i=2^n}{2^{n+1}} \frac{1}{n} \geq \sum_{i=2^n}^{2^{n+1}} \frac{1}{2^{n+1}}[/tex]
The bounds both simplify to multiplication
[tex] 1 \geq \sum_{i=2^n}{2^{n+1}} \frac{1}{n} \geq \frac{1}{2}[/tex]
so
[tex] n+1 \geq \sum_{i=1}{2^{n+1}} \geq \frac{n}{2} [/tex]
You should be able to get it from there.