Results 1 to 7 of 7

Math Help - Proof of maximum value?

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Proof of maximum value?

    So, I have been working on a problem for a while. I am trying to see what sort of maximum and minimum values it can attain. I have for a while conjectured that it attains a maximum value of \left(\frac{4}{3}\right)^{n+1}. I want to see if my proof follows. If anyone is willing to take a look, I would be most appreciative.

    Define A_n = \left\{2^{a_n}(2^{a_{n-1}}(\cdots(2^{a_1}(4^{a_0}-1)-3)-\cdots)-3^{n-1})-3^n\in 3^{n+1}\mathbb{Z}>0\mid a_i \in \mathbb{N}\right\} (Note: the a_i's are all positive integers, but for not all positive integers produce elements of 3^{n+1}\mathbb{Z}, so it doesn't span all positive integers).

    Claim: \displaymode \frac{\prod_{i=0}^n 2^{a_i}}{2^{a_n}(\cdots)-3^n}\le \left(\frac{4}{3}\right)^{n+1} where the denominator is an element of A_n.

    Proof by induction on n.

    For n=0, this is simply \frac{2^{a_0}}{2^{a_0}-1}. Since 2^{a_0}-1\in 3\mathbb{Z}, it must be that a_0\equiv 0 (\text{mod } 2), so \frac{4^{a_0}}{4^{a_0}-1}\le \frac{4^1}{4^1-1} = \frac{4}{3}. Assume the claim is true for all sets up to A_{n-1}. Then, if

    \displaymode \frac{\prod_{i=0}^n 2^{a_i}}{2^{a_n}(\cdots)-3^n}\le k, then
    \displaymode \log_2{\left(\frac{\prod_{i=0}^n 2^{a_i}}{2^{a_n}(\cdots)-3^n}\right)\le \log_2(k)
    \displaymode \log_2{\prod_{i=0}^n 2^{a_i}}-\log_2{(2^{a_n}(\cdots)-3^n)}\le \log_2(k)
    \displaymode \log_2{\prod_{i=0}^n 2^{a_i}}-\log_2{2^{a_n}(\cdots)}+\log_2{2^{a_n}(\cdots)}-\log_2{(2^{a_n}(\cdots)-3^n)}\le \log_2(k)
    \displaymode \log_2{\frac{\prod_{i=0}^{n-1} 2^{a_i}}{(2^{a_{n-1}}(\cdots)-3^{n-1})}}+\log_2{\frac{2^{a_n}(\cdots)}{2^{a_n}(\cdots  )-3^n}\le \log_2(k)

    We can apply the induction hypothesis to the first term, and for the second term, we know that the bottom is an element of A_n with a minimum value of 3^{n+1} (since every element of A_n is an element of 3^{n+1}\mathbb{Z}. And the top is then 3^{n+1}+3^n. So, evaluating this, we get:

    \displaymode \log_2{\frac{\prod_{i=0}^{n-1} 2^{a_i}}{2^{a_{n-1}}(\cdots)-3^{n-1}}}+\log_2{\frac{2^{a_n}(\cdots)}{2^{a_n}(\cdots)-3^n}\le \log_2{\left(\frac{4}{3}\right)^n}+\log_2{\frac{3^  n(3+1)}{3^{n+1}}}=\log_2{\left(\frac{4}{3}\right)^  {n+1}. Eliminating the logs from both sides (2 to the power of each side) yields the inequality desired, and hence by induction, proves the claim.

    Is this proof correct? Am I overlooking something?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16

    Re: Proof of maximum value?

    It looks good to me. What you've proven is that it must be less than or equal to this bound. Is there an element that attains this bound?
    Last edited by Vlasev; September 7th 2012 at 05:54 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: Proof of maximum value?

    Yes, it turns out that the minimum element is always in the set. So, for all n, 3^{n+1}\in A_n. And it is simple to check that 4^{a_n}(4^{a_{n-1}}(...(4^{a_0}-1)-...)-3^{n-1})-3^n=3^{n+1} when a_0=a_1=...=a_n=1.

    Edit:

    I forgot to mention that the minimum element always attains the maximum bound for that ratio since:
    \frac{4^{a_n=1}\cdots 4^{a_0=1}}{3^{n+1}}=\frac{4^{n+1}}{3^{n+1}}
    Last edited by SlipEternal; September 7th 2012 at 06:58 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16

    Re: Proof of maximum value?

    Good! What is this problem related to, if I may ask?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: Proof of maximum value?

    Let I=\{2n-1\mid n\in\mathbb{N}\} be the set of odd positive integers. Define f:I\to I by f(n)=\frac{3n+1}{2^a} where a is the largest power of 2 that divides 3n+1. The function f is sometimes called the Syracuse function, and is one of the methods used to investigate the 3n+1 Conjecture (also known as the Syracuse problem, the Collatz Conjecture, etc.).

    Let B_n = \{\frac{k}{3^{n+1}}\mid k\in A_n\}. Notice that f^{-(n+1)}(1) \subseteq B_n. Now, if we want to check the asymptotic density of f^{-(n+1)}(1) in I, we need to figure out how many elements of f^{-(n+1)}(1) are less than 2m-1 for some m. So, we have:

    \displaymode \frac{2^{a_n}(\cdots)-3^n}{3^{n+1}} \le 2m-1
    \displaymode \log_2{\prod_{i=0}^n 2^{a_i}}-\log_2{\prod_{i=0}^n 2^{a_i}}+\log_2{(2^{a_n}(\cdots)-3^n)} \le \log_2(3^{n+1}(2m-1))
    \displaymode \sum_{i=0}^n{a_i} - \log_2{\frac{\prod_{i=0}^n 2^{a_i}}{2^{a_n}(\cdots)-3^n}} \le \frac{n+1}{\log_3{2}} + \log_2(2m-1)

    I now know that the second term on the left is bounded below by 0 and bounded above by \log_2{\frac{4^{n+1}}{3^{n+1}}}.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16

    Re: Proof of maximum value?

    I knew it! I had a feeling it had something to do with the Collatz problem. All these 3's and 2's...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,931
    Thanks
    782

    Re: Proof of maximum value?

    I work on it whenever I get frustrated with my coursework. I find it relaxing to work on a problem that I don't care if I make any progress on. It helps relieve stress from grad school.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof of a maximum and minimum
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: January 30th 2010, 12:52 AM
  2. Maximum Value???
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: January 24th 2010, 04:23 AM
  3. Maximum value.
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 13th 2009, 12:57 AM
  4. Maximum value
    Posted in the Calculus Forum
    Replies: 3
    Last Post: December 28th 2008, 10:03 PM
  5. Maximum
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 10th 2008, 03:34 AM

Search Tags


/mathhelpforum @mathhelpforum