Results 1 to 13 of 13

Math Help - Proof needed that expression <=1 for all positive integers

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    10

    Proof needed that expression <=1 for all positive integers

    Consider the following function f(k) where k is a positive integer, and \Omega is the Omega constant (0.5671432904097838729999686622) defined by <br />
ln({\frac{1}{\Omega}}) = \Omega <br />

    <br />
f(k) ={\frac{1}{\Omega}}\sum_{j=k}^{\lceil {\frac{k}{\Omega}} \rceil}{\frac{1}{j}}-{\frac{\lceil {\frac{k}{\Omega}} \rceil}{k}}+{\frac{1}{\Omega}}+{\frac{2}{k}}-{\frac{2}{k\Omega}}<br />

    Evaluating the funtion for small values of k gives f(1) = 1, f(2) \approx 0.97 , f(3) \approx 0.97 , f(4) \approx 0.97 etc. Also \lim{k \to \infty}, f(k)=1

    I am interested in finding a proof that for k=1..\infty, f(k)\le1. Any help, hints, or of course a really cool proof, would be much appreciated.

    Thanks

    Rob
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Evo Rob View Post
    Consider the following function f(k) where k is a positive integer, and \Omega is the Omega constant (0.5671432904097838729999686622) defined by <br />
ln({\frac{1}{\Omega}}) = \Omega <br />

    <br />
f(k) ={\frac{1}{\Omega}}\sum_{j=k}^{\lceil {\frac{k}{\Omega}} \rceil}{\frac{1}{j}}-{\frac{\lceil {\frac{k}{\Omega}} \rceil}{k}}+{\frac{1}{\Omega}}+{\frac{2}{k}}-{\frac{2}{k\Omega}}<br />

    Evaluating the funtion for small values of k gives f(1) = 1, f(2) \approx 0.97 , f(3) \approx 0.97 , f(4) \approx 0.97 etc. Also \lim{k \to \infty}, f(k)=1

    I am interested in finding a proof that for k=1..\infty, f(k)\le1. Any help, hints, or of course a really cool proof, would be much appreciated.

    Thanks

    Rob
    I believe that I can do this, but the proof is very fussy so I would rather not have to type it out if anyone else has a neater proof.

    I will start typing it off line and I should be able to post it later other things being equal.

    Outline:

    relpace the sum by an integral which is an upper bound for the sum.

    ignore the first two terms outside the summation as they are always negative

    show that for k>13 the integral and the last two terms outside the summation are strictly decreasing as a function of k, and that at k=14 this is less that 1.

    This shows that the function is bounded above by 1 for k>13, and so we need only check the first 13 terms to prove that f(k) is less than 1 for all positive k.

    We also seem to have a discrepancy with our evaluation of the first few valuea of f(k), maybe these need checking

    RonL
    Last edited by CaptainBlack; August 3rd 2008 at 09:23 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    I believe that I can do this, but the proof is very fussy so I would rather not have to type it out if anyone else has a neater proof.

    I will start typing it off line and I should be able to post it later other things being equal.

    Outline:

    relpace the sum by an integral which is an upper bound for the sum.

    ignore the first two terms outside the summation as they are always negative

    show that for k>13 the integral and the last two terms outside the summation are strictly decreasing as a function of k, and that at k=14 this is less that 1.

    This shows that the function is bounded above by 1 for k>13, and so we need only check the first 13 terms to prove that f(k) is less than 1 for all positive k.

    We also seem to have a discrepancy with our evaluation of the first few valuea of f(k), maybe these need checking

    RonL
    Because 1/x is a positive decreasing function for x>0, for k>1 we have:

    \sum_{j=k}^{\lceil(k/\Omega\rceil} \frac{1}{j}\le \int_{x=k}^{\frac{k}{\Omega}+1} \frac{1}{x-1}\ dx=\ln(k/\Omega) - \ln(k-1)=\ln\left( \frac{k}{\Omega(k-1)}\right)

    Hence:

    <br />
f(k) \le {\frac{1}{\Omega}}\ln\left( \frac{k}{\Omega(k-1)}\right)<br />
-{\frac{\lceil {\frac{k}{\Omega}} \rceil}{k}}+{\frac{1}{\Omega}}+{\frac{2}{k}}-{\frac{2}{k\Omega}}<br />

    Now -{\frac{\lceil {\frac{k}{\Omega}} \rceil}{k}}+{\frac{1}{\Omega}}<0, so

    <br />
f(k) \le {\frac{1}{\Omega}}\ln\left( \frac{k}{\Omega(k-1)}\right)<br />
+{\frac{2}{k}}-{\frac{2}{k\Omega}}<br />

    Now let:

    <br />
h(k)= {\frac{1}{\Omega}}\ln\left( \frac{k}{\Omega(k-1)}\right)<br />
+{\frac{2}{k}}-{\frac{2}{k\Omega}}<br />

    Then:

    \frac{dh}{dk}=\frac{1}{\Omega k(k-1)}-\frac{2}{k^2}+\frac{2}{k^2\Omega}

    But \lim_{k\to \infty}h(k)=1 , and we can see that \frac{dh}{dk}>0\ \forall k>1 , so h(k) is an increasing function bounded above by 1, so we have:

    f(k)\le h(k) <1

    as required.

    (Note this worked out simpler than originaly thought due to correction of some minor errors in my original working)

    RonL
    Last edited by CaptainBlack; August 3rd 2008 at 11:19 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2008
    Posts
    10
    Firstly, please accept my humble apologies, there was a mistake in my typing of the problem
    formulation. For some inexplicable reason, I typed in ceiling functions when they should have been
    floors. This is possibly what caused the discrepancy in the first few values of f(k)

    However, the suggested approach works, with a few minor alterations, for the correct problem
    formulation:

    <br />
f(k) ={\frac{1}{\Omega}}\sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{1}{j}}-{\frac{\lfloor{\frac{k}{\Omega}} <br />
\rfloor}{k}}+{\frac{1}{\Omega}}+{\frac{2}{k}}-{\frac{2}{k\Omega}}<br />

    As 1/x is a positive decreasing function for k>1, we have:
    <br />
\sum_{j=k}^{\lfloor(k/\Omega\rfloor} \frac{1}{j}\le \int_{x=k}^{\frac{k}{\Omega}} \frac{1}{x-1}\ <br />
dx=\ln(k/\Omega -1) - \ln(k-1)=\ln\left( \frac{k/\Omega -1}{(k-1)}\right)<br />

    Also, as
    <br />
\lfloor{k/\Omega}\rfloor\ge{k/\Omega}-1<br />

    we have:
    <br />
f(k)\le {\frac{1}{\Omega}}\ln\left( \frac{k/\Omega -1}{(k-1)}\right) + {\frac{3}{k}}-{\frac{2}{k\Omega}}<br />

    Now let:
     <br />
h(k)={\frac{1}{\Omega}}\ln\left( \frac{k/\Omega -1}{(k-1)}\right) + {\frac{3}{k}}-{\frac{2}{k\Omega}}<br />

     <br />
{\frac{dh}{dk}}=-{\frac{(1-\Omega)}{(k-1)(k-\Omega)}}- {\frac{3}{k^2}}+{\frac{2}{k^2\Omega}}<br />

    Now for  {\frac{dh}{dk}} to be positive, requires that:
     <br />
{\frac{(k-1)(k-\Omega)}{k^2}}>{\frac{\Omega(1-\Omega)}{(2-3\Omega)}} = 0.8222248

    This is true \forall k\ge9 .

    As  \lim_{k\to \infty}h(k)=1 and <br />
\frac{dh}{dk}>0\ \forall k>8<br />

    <br />
f(k)\le h(k) \le1\ \forall k>8<br />

    Finally, f(k) can be evaluted for k=1 to 8, completing the proof.

    Once again, many thanks for the excellent and timely help with this, it is much appreciated.

    Rob
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by CaptainBlack View Post
    I believe that I can do this, but the proof is very fussy so I would rather not have to type it out if anyone else has a neater proof.

    I will start typing it off line and I should be able to post it later other things being equal.

    Outline:

    relpace the sum by an integral which is an upper bound for the sum.

    ignore the first two terms outside the summation as they are always negative

    show that for k>13 the integral and the last two terms outside the summation are strictly decreasing as a function of k, and that at k=14 this is less that 1.

    This shows that the function is bounded above by 1 for k>13, and so we need only check the first 13 terms to prove that f(k) is less than 1 for all positive k.

    We also seem to have a discrepancy with our evaluation of the first few valuea of f(k), maybe these need checking

    RonL
    A big improvement on the sad old line "I have no time now but will reply later if no-one else does ....."
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by mr fantastic View Post
    A big improvement on the sad old line "I have no time now but will reply later if no-one else does ....."
    I had thought of writting exactly that but thought I would only get stick for doing so. Also I had the solution (complete with some errors) in my note pad so could give an outline, it was the prospect of typing it that put me off giving the solution right away (that and having to walk the dog).

    RonL
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Evo Rob View Post
    Firstly, please accept my humble apologies, there was a mistake in my typing of the problem
    formulation. For some inexplicable reason, I typed in ceiling functions when they should have been
    floors. This is possibly what caused the discrepancy in the first few values of f(k)

    However, the suggested approach works, with a few minor alterations, for the correct problem
    formulation:

    <br />
f(k) ={\frac{1}{\Omega}}\sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{1}{j}}-{\frac{\lfloor{\frac{k}{\Omega}} <br />
\rfloor}{k}}+{\frac{1}{\Omega}}+{\frac{2}{k}}-{\frac{2}{k\Omega}}<br />

    As 1/x is a positive decreasing function for k>1, we have:
    <br />
\sum_{j=k}^{\lfloor(k/\Omega\rfloor} \frac{1}{j}\le \int_{x=k}^{\frac{k}{\Omega}} \frac{1}{x-1}\ <br />
dx=\ln(k/\Omega -1) - \ln(k-1)=\ln\left( \frac{k/\Omega -1}{(k-1)}\right)<br />

    Also, as
    <br />
\lfloor{k/\Omega}\rfloor\ge{k/\Omega}-1<br />

    we have:
    <br />
f(k)\le {\frac{1}{\Omega}}\ln\left( \frac{k/\Omega -1}{(k-1)}\right) + {\frac{3}{k}}-{\frac{2}{k\Omega}}<br />

    Now let:
     <br />
h(k)={\frac{1}{\Omega}}\ln\left( \frac{k/\Omega -1}{(k-1)}\right) + {\frac{3}{k}}-{\frac{2}{k\Omega}}<br />

     <br />
{\frac{dh}{dk}}=-{\frac{(1-\Omega)}{(k-1)(k-\Omega)}}- {\frac{3}{k^2}}+{\frac{2}{k^2\Omega}}<br />

    Now for  {\frac{dh}{dk}} to be positive, requires that:
     <br />
{\frac{(k-1)(k-\Omega)}{k^2}}>{\frac{\Omega(1-\Omega)}{(2-3\Omega)}} = 0.8222248

    This is true \forall k\ge9 .

    As  \lim_{k\to \infty}h(k)=1 and <br />
\frac{dh}{dk}>0\ \forall k>8<br />

    <br />
f(k)\le h(k) \le1\ \forall k>8<br />

    Finally, f(k) can be evaluted for k=1 to 8, completing the proof.

    Once again, many thanks for the excellent and timely help with this, it is much appreciated.

    Rob
    if f_1(k) is the function defined in your original postm and f_2(k) the corrected function, is it not the case that:

    f_2(k)\le f_1(k)

    and so the original proof still proves the required result!

    RonL
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jul 2008
    Posts
    10
    As the second term in each function is negative, I think:
    <br />
f_2(k)\ge f_1(k)<br />

    Either we have
     <br />
{\lceil{\frac{k}{\Omega}} \rceil}= {\lfloor{\frac{k}{\Omega}} \rfloor}<br />
    in which case the two functions are the same, or we have
     <br />
{\lceil{\frac{k}{\Omega}} \rceil}= {\lfloor{\frac{k}{\Omega}} \rfloor}+1<br />
    in which case
    <br />
f_2(k)-f_1(k)={\frac{1}{k}}-{\frac{1}{\Omega({\lfloor{k/\Omega}\rfloor + 1})}} \ge0<br />

    Rob
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jul 2008
    Posts
    10
    Unfortunately, both of the proofs given in this thread appear to be faulty.

    In the original proof (given by Captain Black), there is a missing minus sign, which prevents the proof from working.

    <br />
\frac{dh}{dk}={\color{red}-}\frac{1}{\Omega k(k-1)}-\frac{2}{k^2}+\frac{2}{k^2\Omega}<br />

    And in my attempted proof for the correct version of the problem (with floor functions rather than ceilings), there is a missing \Omega which also foils the proof.

    <br />
{\frac{dh}{dk}}=-{\frac{(1-\Omega)}{{\color{red}\Omega}(k-1)(k-\Omega)}}- {\frac{3}{k^2}}+{\frac{2}{k^2\Omega}}<br />

    So, if anyone would like to try and solve the problem, its still open...

    Given:

    <br />
f(k) ={\frac{1}{\Omega}}\sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{1}{j}}-{\frac{\lfloor{\frac{k}{\Omega}} <br />
\rfloor}{k}}+{\frac{1}{\Omega}}+{\frac{2}{k}}-{\frac{2}{k\Omega}}<br />

    Where k is a positive integer and \Omega is the Omega constant, prove that \forall k>0\ \ f(k)\le1

    Any help, or ideally a really cool proof would be much appreciated.

    Thanks

    Rob
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Evo Rob View Post
    Unfortunately, both of the proofs given in this thread appear to be faulty.

    In the original proof (given by Captain Black), there is a missing minus sign, which prevents the proof from working.

    <br />
\frac{dh}{dk}={\color{red}-}\frac{1}{\Omega k(k-1)}-\frac{2}{k^2}+\frac{2}{k^2\Omega}<br />

    And in my attempted proof for the correct version of the problem (with floor functions rather than ceilings), there is a missing \Omega which also foils the proof.

    <br />
{\frac{dh}{dk}}=-{\frac{(1-\Omega)}{{\color{red}\Omega}(k-1)(k-\Omega)}}- {\frac{3}{k^2}}+{\frac{2}{k^2\Omega}}<br />

    So, if anyone would like to try and solve the problem, its still open...

    Given:

    <br />
f(k) ={\frac{1}{\Omega}}\sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{1}{j}}-{\frac{\lfloor{\frac{k}{\Omega}} <br />
\rfloor}{k}}+{\frac{1}{\Omega}}+{\frac{2}{k}}-{\frac{2}{k\Omega}}<br />

    Where k is a positive integer and \Omega is the Omega constant, prove that \forall k>0\ \ f(k)\le1

    Any help, or ideally a really cool proof would be much appreciated.

    Thanks

    Rob
    Well I can make mine work by putting back the two terms that I took out, replacing the \lceil k/\Omega\rceil by k/\Omega+1 and then we have a bound which is again increasing after the first term and tending to 1, so it will then work.

    (I think - I haven't worked through the algebra in detail yet and I have to go out in a moment so won't be able to fix it untill the tommorow)

    RonL
    Last edited by CaptainBlack; August 5th 2008 at 11:26 AM.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    Well I can make mine work by putting back the two terms that I took out, replacing the \lceil k/\Omega\rceil by k/\Omega+1 and then we have a bound which is again increasing after the first term and tending to 1, so it will then work.

    (I think - I haven't worked through the algebra in detail yet and I have to go out in a moment so won't be able to fix it untill the tommorow)

    RonL
    Having worked through this in detail I find that this approach without some modification cannot be made to work.

    RonL
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Jul 2008
    Posts
    10
    Problem statement:

    The function f(k) is defined as follows:

    <br />
f(k) ={\frac{1}{\Omega}}\sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{1}{j}}-{\frac{\lfloor{\frac{k}{\Omega}} <br />
\rfloor}{k}}+{\frac{1}{\Omega}}+{\frac{2}{k}}-{\frac{2}{k\Omega}}<br />

    where k is a positive integer and \Omega is the Omega constant, defined by \Omega=ln({\frac{1}{\Omega}})

    Prove that \forall k>0 \ \ f(k)\le1

    Solution:

    Inductive proof using discrete maths.

    Proof sketch:
    1. Show that kf(k)\le{k} for k=1,2
    2. Show that \forall k\ge2 \ \ (k+1)f(k+1)-kf(k)\le1
    3. By induction \forall k\ge1 \ \ f(k)\le1


    Step 1. Show that kf(k)\le{k} for k=1,2
    f(1) = 1 , f(2) = {\frac{5}{6\Omega}}-{\frac{1}{2}}\approx0.97

    Step 2. Show that \forall k\ge2 \ \ (k+1)f(k+1)-kf(k)\le1
    <br />
kf(k) =\sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{k/\Omega}{j}}-{\lfloor{k/\Omega} <br />
\rfloor}+{\frac{k}{\Omega}}+2-{\frac{2}{\Omega}}<br />
    <br />
=\sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{(k/\Omega)-j}{j}}+k({\frac{1}{\Omega}}-1)+3-{\frac{2}{\Omega}}<br />
    <br />
(k+1)f(k+1)-kf(k) =\sum_{j=k+1}^{\lfloor {(k+1)/\Omega} <br />
\rfloor}{\frac{((k+1)/\Omega)-j}{j}} - \sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{(k/\Omega)-j}{j}}+({\frac{1}{\Omega}}-1)<br />
    <br />
={\frac{1}{\Omega}}\sum_{j=k+1}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{1}{j}} + \sum_{j={\lfloor {k/\Omega} <br />
\rfloor + 1}}^{\lfloor {(k+1)/\Omega} <br />
\rfloor}{\frac{((k+1)/\Omega)-j}{j}}<br />

    (Note this holds for k\ge2 but not for k=1 as in that case k+1>\lfloor(k/\Omega)\rfloor)

    Now there are two cases to consider:

    Case 1: {\lfloor {(k+1)/\Omega} <br />
\rfloor}={\lfloor {k/\Omega} <br />
\rfloor}+1<br />

    The second summation term above can be expressed as:
    {\frac{(k/\Omega)-{\lfloor {(k/\Omega} <br />
\rfloor}}{<br />
{\lfloor {k/\Omega} <br />
\rfloor}+1<br />
}}<br />
\le<br />
{\frac{1}{{\lfloor {k/\Omega} <br />
\rfloor}+1<br />
}}<br />
    Hence:
    <br />
(k+1)f(k+1)-kf(k) \le {\frac{1}{\Omega}}\sum_{j=k+1}^{\lfloor {(k+1)/\Omega} <br />
\rfloor}{\frac{1}{j}}

    <br />
\le {\frac{1}{\Omega}}\int_{x=k+1}^{((k+1)/\Omega) <br />
}{\frac{1}{x}}={\frac{1}{\Omega}}\ln({\frac{(k+1)/\Omega <br />
}{k+1}})=1

    So we have:

    <br />
(k+1)f(k+1)-kf(k) \le 1 <br />

    Case 2: {\lfloor {(k+1)/\Omega} <br />
\rfloor}={\lfloor {k/\Omega} <br />
\rfloor}+2<br />

    The second summation term can be expressed as:
    {\frac{(k/\Omega)-{\lfloor {(k/\Omega} <br />
\rfloor}}{<br />
{\lfloor {k/\Omega} <br />
\rfloor}+1<br />
}}<br />
+<br />
{\frac{(k/\Omega)-{\lfloor {(k/\Omega} <br />
\rfloor}-1}{<br />
{\lfloor {k/\Omega} <br />
\rfloor}+1<br />
}}<br />

    The first of the above terms is the same as case 1 and can be treated in the same way. The second term is negative and can therefore be safely disgarded.

    Again we have:

    <br />
(k+1)f(k+1)-kf(k) \le 1 <br />

    Step 3: By induction \forall k\ge1 \ \ f(k)\le1

    By step 1, we have f(2)\le1 (Basis).

    By step 2, we have \forall k>2 \ \ (k+1)f(k+1)-kf(k)\le1

    Inductive step: assuming that f(k)\le1, we have
    {(k+1)f(k+1)} \le {kf(k)+1} \le {k+1} and hence
    f(k+1)\le1

    As f(1)=1 (by step 1), we have:

    \forall k>0 \ \ f(k)\le1

    Theorem proved!

    Rob
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Evo Rob View Post
    Problem statement:

    The function f(k) is defined as follows:

    <br />
f(k) ={\frac{1}{\Omega}}\sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{1}{j}}-{\frac{\lfloor{\frac{k}{\Omega}} <br />
\rfloor}{k}}+{\frac{1}{\Omega}}+{\frac{2}{k}}-{\frac{2}{k\Omega}}<br />

    where k is a positive integer and \Omega is the Omega constant, defined by \Omega=ln({\frac{1}{\Omega}})

    Prove that \forall k>0 \ \ f(k)\le1

    Solution:

    Inductive proof using discrete maths.

    Proof sketch:
    1. Show that kf(k)\le{k} for k=1,2
    2. Show that \forall k\ge2 \ \ (k+1)f(k+1)-kf(k)\le1
    3. By induction \forall k\ge1 \ \ f(k)\le1


    Step 1. Show that kf(k)\le{k} for k=1,2
    f(1) = 1 , f(2) = {\frac{5}{6\Omega}}-{\frac{1}{2}}\approx0.97

    Step 2. Show that \forall k\ge2 \ \ (k+1)f(k+1)-kf(k)\le1
    <br />
kf(k) =\sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{k/\Omega}{j}}-{\lfloor{k/\Omega} <br />
\rfloor}+{\frac{k}{\Omega}}+2-{\frac{2}{\Omega}}<br />
    <br />
=\sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{(k/\Omega)-j}{j}}+k({\frac{1}{\Omega}}-1)+3-{\frac{2}{\Omega}}<br />
    <br />
(k+1)f(k+1)-kf(k) =\sum_{j=k+1}^{\lfloor {(k+1)/\Omega} <br />
\rfloor}{\frac{((k+1)/\Omega)-j}{j}} - \sum_{j=k}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{(k/\Omega)-j}{j}}+({\frac{1}{\Omega}}-1)<br />
    <br />
={\frac{1}{\Omega}}\sum_{j=k+1}^{\lfloor {k/\Omega} <br />
\rfloor}{\frac{1}{j}} + \sum_{j={\lfloor {k/\Omega} <br />
\rfloor + 1}}^{\lfloor {(k+1)/\Omega} <br />
\rfloor}{\frac{((k+1)/\Omega)-j}{j}}<br />

    (Note this holds for k\ge2 but not for k=1 as in that case k+1>\lfloor(k/\Omega)\rfloor)

    Now there are two cases to consider:

    Case 1: {\lfloor {(k+1)/\Omega} <br />
\rfloor}={\lfloor {k/\Omega} <br />
\rfloor}+1<br />

    The second summation term above can be expressed as:
    {\frac{(k/\Omega)-{\lfloor {(k/\Omega} <br />
\rfloor}}{<br />
{\lfloor {k/\Omega} <br />
\rfloor}+1<br />
}}<br />
\le<br />
{\frac{1}{{\lfloor {k/\Omega} <br />
\rfloor}+1<br />
}}<br />
    Hence:
    <br />
(k+1)f(k+1)-kf(k) \le {\frac{1}{\Omega}}\sum_{j=k+1}^{\lfloor {(k+1)/\Omega} <br />
\rfloor}{\frac{1}{j}}

    <br />
\le {\frac{1}{\Omega}}\int_{x=k+1}^{((k+1)/\Omega) <br />
}{\frac{1}{x}}={\frac{1}{\Omega}}\ln({\frac{(k+1)/\Omega <br />
}{k+1}})=1

    So we have:

    <br />
(k+1)f(k+1)-kf(k) \le 1 <br />

    Case 2: {\lfloor {(k+1)/\Omega} <br />
\rfloor}={\lfloor {k/\Omega} <br />
\rfloor}+2<br />

    The second summation term can be expressed as:
    {\frac{(k/\Omega)-{\lfloor {(k/\Omega} <br />
\rfloor}}{<br />
{\lfloor {k/\Omega} <br />
\rfloor}+1<br />
}}<br />
+<br />
{\frac{(k/\Omega)-{\lfloor {(k/\Omega} <br />
\rfloor}-1}{<br />
{\lfloor {k/\Omega} <br />
\rfloor}+1<br />
}}<br />

    The first of the above terms is the same as case 1 and can be treated in the same way. The second term is negative and can therefore be safely disgarded.

    Again we have:

    <br />
(k+1)f(k+1)-kf(k) \le 1 <br />

    Step 3: By induction \forall k\ge1 \ \ f(k)\le1

    By step 1, we have f(2)\le1 (Basis).

    By step 2, we have \forall k>2 \ \ (k+1)f(k+1)-kf(k)\le1

    Inductive step: assuming that f(k)\le1, we have
    {(k+1)f(k+1)} \le {kf(k)+1} \le {k+1} and hence
    f(k+1)\le1

    As f(1)=1 (by step 1), we have:

    \forall k>0 \ \ f(k)\le1

    Theorem proved!

    Rob
    Well that will save me having to worry about it anymore, my investigations were leading me in a vaguely similar direction, but unfortunaly work has been getting in the way of progressing the task.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: November 24th 2011, 05:05 PM
  2. if x and n are positive integers....
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 7th 2009, 12:07 AM
  3. no positive integers
    Posted in the Algebra Forum
    Replies: 5
    Last Post: May 7th 2009, 10:51 AM
  4. Sum of Positive Integers
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 31st 2007, 05:34 AM
  5. Positive Integers
    Posted in the Algebra Forum
    Replies: 1
    Last Post: January 28th 2007, 06:25 PM

Search Tags


/mathhelpforum @mathhelpforum