Proof of maximum value?

**SlipEternal** · September 7th 2012, 04:15 PM

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?

**Vlasev** · September 7th 2012, 05:52 PM

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?

**SlipEternal** · September 7th 2012, 06:27 PM

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}}$

**Vlasev** · September 7th 2012, 09:44 PM

Good! What is this problem related to, if I may ask?

**SlipEternal** · September 8th 2012, 10:13 AM

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}}}$ .

**Vlasev** · September 8th 2012, 10:42 AM

I knew it! I had a feeling it had something to do with the Collatz problem. All these 3's and 2's...

**SlipEternal** · September 8th 2012, 11:02 AM

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.

Thread: Proof of maximum value?

LinkBack

Thread Tools

Display

Proof of maximum value?

Re: Proof of maximum value?

Re: Proof of maximum value?

Re: Proof of maximum value?

Re: Proof of maximum value?

Re: Proof of maximum value?

Re: Proof of maximum value?

Similar Math Help Forum Discussions

Proof of a maximum and minimum

Maximum Value???

Maximum value.

Maximum value

Maximum

Search Tags