Prove $7^{71}>75^{32}$

My math teacher left two questions last week, prove (1) $6^9>10^7$ and (2) $7^{71}>75^{32}.$

I did the first question: \begin{align}\frac{6^9}{10^7}&=\frac{4}{5}\times\frac{27^3}{25^3}\\&=0.8\times1.08^3\\&>0.8\times(1+3\times0.08+3\times0.08^2)\\&>0.8\times(1+3\times0.086)\\&>0.8\times1.25=1.\end{align}

But I can't work out the second, I calculated it out on my computer, $\frac{7^{71}}{75^{32}}=1.000000949\cdots$

$\color{green}{\textbf{Improved version.}}$

There is an alternative approach.

As it was shown in the my first answer, $$R=\dfrac{75^{32}}{7^{71}}=\dfrac{5^2}{3^3}\,\dfrac{5^6}{3^7\cdot7}\,\left(\dfrac{3^3\cdot5^4}{7^5}\right)^{14} = \dfrac{625^2}{7\cdot 243^2}\,\left(\dfrac{16875}{16807}\right)^{14}.\tag1$$

Identity $(1)$ can be presented in the form of $$R= \dfrac{625^2}{7\cdot 243^2}\,\left(\dfrac{225}{224}\right)^{14} \,\left(\dfrac{2400}{2401}\right)^{14} =\dfrac{625^2}{7\cdot 243^2}\,\left(\dfrac{225}{224}\right)^{14} \,\left(1-\dfrac{1}{2401}\right)^{14}\tag{1.1}$$

$$<\dfrac{625^2}{7\cdot 243^2}\,\left(\dfrac{225}{224}\right)^{14} \,\left(1-\dfrac{14}{2401}+\dfrac{91}{2401^2}\right),\tag{1.2}$$

$$R < \dfrac{35557}{37845}\,\left(\dfrac{225}{224}\right)^{14}.\tag2$$

Since $$\dfrac{225^2}{224^2} = 1+\dfrac t7,\quad\text{where}\quad t=\dfrac{449}{7168},\tag3$$ one can get $$\left(1+\dfrac t7\right)^7 = 1 + \dfrac 77t + \dfrac{21}{7^2}t^2+\dfrac{35}{7^3}t^3 +\dfrac{35}{7^4}t^4+\dfrac{21}{7^5}t^5+\dfrac7{7^6}t^6+\dfrac1{7^7}t^7$$ $$< 1+t+\dfrac37t^2\left(1+\dfrac5{21}t+\dfrac {5^2}{21^2}t^2+\dots\right) =1+t+\dfrac{9t^2}{21-5t} = \dfrac{21+16t+4t^2}{21-5t},$$ $$\dfrac{35557}{37845}\left(1+\dfrac t7\right)^7-1 < \dfrac{35557}{37845}\cdot\dfrac{21+16t+4t^2}{21-5t}-1 $$ $$=\dfrac{142228 t^2 + 758137 t - 48048}{37845(21-5t)},$$ wherein $$(142228 t^2 + 758137 t - 48048)\bigg|_{\large\frac{449}{7168}} = -\dfrac{7\,828\,635}{12\,845\,056} < 0.$$ Therefore, $$\dfrac{35557}{37845}\left(1+\dfrac t7\right)^7 < 1$$ and $\;\color{brown}{\mathbf{R<1}}.\;$

Proved!

I will give a solution that involve only calculations with 2 digit numbers; all the other contributions will be estimated. I will call my approach the sloppy continued fractions method. Unluckily, if you want to cut down computations you have to be smarter, and in particular lengthy. Sorry for that, but you will enjoy! After the theoretical framework is set up, the problem is easy to understand, but if you prefer you can skip to the "out of the blue" section at the bottom.

Theory

Firstly, notice that the problem can be reformulated as $\log_7(75) < \frac{71}{32}$. The instance of finding good rational approximants to irrational numbers is a classical one, and it is addressed by the continued fractions method. In case of logarithms and inequalities, it has the following simpler form. Say we want to understand whether $\log_a(b) < \frac{p}{q}$. Then:

1. Take the maximum integer $n_0$ less than $\log_a(b)$, i.e. solve $a^{n_0} < b < a^{n_0+1} $, and let $m_0$ be the maximum integer less than $p/q$.
2. If $m_0 \ge n_0 +1$ the inequality is true, because $$\frac{p}{q} \ge m_0 \ge n_0 +1 \ge \log_a(b) $$ Else, if $n_0 \ge m_0 +1$ the inequality is false, because $$ \frac{p}{q} \le m_0 +1 \le n_0 \le \log_a(b) $$ Otherwise, go to step 3 supposing $n_0 = m_0$.
3. Since $\log_a(b) - n_0 = \log_a(b/a^{n_0})$ is less than one, we can write $$ \log_a(b) = n_0+ \frac{1}{\log_{a_1}(b_1) } $$ where $a_1 = b/a^{n_0}, b_1 = a$. Analogously we can write $$ \frac{p}{q} = n_0 + \frac{1}{ \frac{p_1}{q_1} } $$ where $p_1 = q, q_1 = p-n_0 q$.
4. Now we reformulate the inequality and we get $$ n_0 + \frac{1}{\log_{a_1}(b_1) } < n_0 + \frac{p-n_0 q}{q} $$ $$ \log_{a_1}(b_1) > \frac{p_1}{q_1} $$ And we can repeat from step 1 with a similar problem (but sign reversed).

There is a little problem: while the fraction gets simpler at step (5), the numbers involved in logarithms becomes harder. Let me state a little lemma.

Logarithm approximation. Let $\alpha, \beta \in \mathbb{N}$ and $k,j \in \mathbb{Z}$ small with respect to $\alpha, \beta$. Then if $x = k/\alpha, y = j/\beta$:

$$ 1+\frac{1}{\ln(\alpha/\beta)} (x -y -(x^2+y^2)) < \log_{\frac{\alpha}{\beta}} (\frac{\alpha+k}{\beta+j} ) < 1+\frac{1}{\ln(\alpha/\beta)} (x-y +(x^2+y^2))$$

Proof. This is a simple consequence of $ x-x^2 \le \ln(1+x) \le x+x^2$. Also, depending on the sign of $k,j$ and the inequality that must be used, sometimes the quadratic term is not necessary (indeed $\log(1+x) \le x$ for positive $x$ and $\log(1+x) \ge x$ for negative $x$).

Now let me restate the continued fraction method with a sloppiness parameter. We want to solve inequalities of the form $\log_a (b) < \frac{p}{q} \cdot \alpha$, where $\alpha \simeq 1 $ is a rational number (the approximation parameter). The bad thing is that it can stop at some time because of our sloppiness, but if it doesn't stop it works with few digits!! Also, don't worry if you can't follow the exact formulas, because they will get explicit thereafter.

1. Take the maximum integer $n_0$ less than $\log_a(b)$, i.e. solve $a^{n_0} < b < a^{n_0+1} $, and let $m_0$ be the maximum integer less than $p/q$.
2. If If $\alpha m_0 \ge n_0 +1$ the inequality is true, because $$\alpha\frac{p}{q} \ge \alpha m_0 \ge n_0 +1 \ge \log_a(b) $$ Else, if $n_0 \ge \alpha (m_0 +1)$ the inequality is false, because $$ \alpha \frac{p}{q} \le \alpha(m_0 +1) \le n_0 \le \log_a(b) $$ Else, if $n_0 = m_0$ go to step 3. In any other case, return "YOU HAVE BEEN TOO SLOPPY! TRY AGAIN!".
3. Since $\log_a(b) - n_0 = \log_a(b/a^{n_0})$ is less than one, we can write $$ \log_a(b) = n_0+ \frac{1}{\log_{a_1}(b_1) } $$ where $a_1 = b/a^{n_0}, b_1 = a$. Analogously we can write $$ \alpha \frac{p}{q} - n_0 = \alpha(n_0 + \frac{q_1}{p_1} ) - n_0 = (\alpha -1)n_0 + \alpha \frac{q_1}{p_1} = \frac{q_1}{p_1} ( \alpha + \frac{p_1}{q_1} n_0 (\alpha-1) )= \frac{1}{ \alpha_1 \frac{p_1}{q_1} } $$ where $p_1 = q, q_1 = p-n_0 q, \alpha_1 = \left ( \alpha + \frac{p_1}{q_1} n_0 (\alpha-1) \right )^{-1} $.
4. Now we reformulate the inequality and we get $$ n_0 + \frac{1}{\log_{a_1}(b_1) } < n_0 + \frac{1}{\alpha_1 \frac{p_1}{q_1} } $$ $$ \log_{a_1}(b_1) > \alpha_1 \frac{p_1}{q_1} $$ If we want to, we can approximate a bit the logarithm on the left using the logarithm approximation and move this contribution in $\alpha_1$. Then we can repeat from step 1 with a similar problem (but reversed inequality).

Calculations

Let's start! At the beginning $a=7, b= 75, p=71, q=32, \alpha=1$. Also, let me notice that the continued fraction of $71/32$ is $[2,4,1,1,3]$, that is: $$ \frac{71}{32} = 2+\frac{1}{4+\frac{1}{1+ \frac{1}{1+\frac{1}{3}}}} $$

Since we suspect this approximations is really close, probably the continued fraction of the logarithm will be the same for a lot of time, so that we have a guess of what the "$n_0$" should be.

STEP 1

1.1 Note that $7^2 < 75 < 7^3$, so that $n_0 = 2= m_0$ and we go to point 3.

1.3 We have $a_1 = 75/49, b_1 = 7, p_1 = 32, q_1 = 71 - 64 = 7$. The inequality is now $$ \log_{75/49} (7) > \frac{32}{7}$$ here it is a trick we will use repeatedly: $$ \log_{75/49}(7) = \color{red}{\log_{75/49}(75/50)}\log_{75/50}(7) > \color{red}{\left(1- \frac{1}{50} \right)} \log_{3/2}(7) = \frac{49}{50} \log_{3/2}(7) $$

1.5 It is enough to verify that something smaller than LHS is greater than RHS, and we get the sloppy inequality $$ \log_{3/2}(7) > \frac{50}{49} \frac{32}{7} $$

STEP 2

2.1 The suggestion from the continued fraction of 32/7 makes us try $n_1 = 4$, and indeed $$ 3^4 = 81 < 112 = 7 \cdot 16 = 7 \cdot 2^4, \ \ \ 3^5 = 343 > 7 \cdot 32 $$ 2.3 Formulas yield $a_2 = 112/81 , b_2 = 3/2, p_2 = 7, q_2 = 4$ and $$\alpha_2 = \left ( \frac{50}{49} + \frac{7}{4} \cdot 4 \cdot \frac{1}{49}\right)^{-1} = \left ( \frac{57}{49} \right)^{-1} = \frac{49}{57} $$ The inequality is now $$ \log_{112/81} (3/2) < \frac{7}{4} \frac{49}{57}$$ and the log trick yields $$ \log_{112/81}(3/2) = \log_{112/81}(110/80) \log_{11/8}(3/2) < \left ( 1-\frac{2}{112} + \frac{1}{81} \right ) \log_{11/8}(3/2) < \log_{11/8}(3/2)$$

2.5 The sloppy inequality remains $$ \log_{11/8} (3/2) < \frac{7}{4} \frac{49}{57} $$

STEP 3

3.1 Under the usual suggestion we try $n_2 = 1$ and it works: $$ \frac{11}{8} = 1+ \frac{3}{11} < 1+ \frac{1}{2} = \frac{3}{2}, \frac{11^2}{8^2} = \left( 1+ \frac{3}{11} \right)^2 > 1+ \frac{6}{11} > \frac{3}{2} $$ 3.3 We get $p_3 =4, q_3 = 3, a_3 = 24/22 = 12/11, b_3 = 11/8$ and

$$ \alpha_3 = \left ( \frac{49}{57} -\frac{4}{3} \frac{9}{57} \right )^{-1} = \frac{57}{37} $$

3.5 The fraction $12/11$ is nice, so we don't do the trick at this step. The sloppy inequality is just

$$ \log_{12/11}( 11/8) > \frac{4}{3} \frac{57}{37} $$

STEP 4.

4.1 Here it is the surprise: using the rule for the cube of a sum we have that

$$ \left ( 1 + \frac{1}{11} \right) ^3 = 1 + \frac{3}{11} + \frac{3}{11^2} + \frac{1}{11^3} < 1 + \frac{3}{11} + \frac{10}{121} + \frac{11}{11^3} = \frac{15}{11} < \frac{11}{8}$$

because $15 \cdot 8 = 120 < 121 = 11^2$. This translates into $\log_{12/11}(11/8) \ge 3$. On the other side

$$ \frac{4}{3} \frac{57}{37} < \frac{4}{3} \frac{60}{36} = \frac{20}{9} < 3 \le \log_{12/11}(11/8) $$

And we are done. Victory! Yey!

Out of the blue

Let's start from the observation that

$$ (\#1) \ \ \ \ \ \ \left ( \frac{12}{11} \right ) ^3 = \left (1+ \frac{1}{11} \right ) ^3 = $$ $$ =1+ \frac{3}{11} +\frac{3}{11^2} +\frac{1}{11^3} \le 1+ \frac{3}{11} + \frac{10}{11^2} + \frac{11}{11^3} $$ $$ = \frac{15}{11} < \frac{11}{8} $$

So that $\log_{12/11}(11/8) > 3$. Also, note that

$$ (\#2) \ \ \ \ \ \ 3 > \frac{20}{9} = \frac{60}{36} \frac{4}{3} > \frac{57}{37} \frac{4}{3} $$ If we combine (1) and (2) we get $ \log_{12/11}(11/8) > \frac{57}{37} \frac{4}{3}$. Taking reciprocal (that swaps base and argument in the logarithm) and adding 1 we get

$$ (\#3) \ \ \ \ \ \ \log_{11/8} \left ( \frac{12}{11} \frac{11}{8} \right ) = \log_{11/8}(3/2) < $$ $$ <1+\frac{37}{57} \frac{3}{4} < \frac{37}{57}+ \frac{21}{57} + \frac{37}{57} \frac{3}{4} = $$ $$ = \frac{37}{57} \cdot 1 + \frac{12}{57} \frac{7}{4} + \frac{37}{57} \frac{3}{4} = $$ $$ =\frac{37}{57} \frac{7}{4} + \frac{12}{57} \frac{7}{4} = \frac{49}{57} \frac{7}{4}$$

Using the inequality

$$ (\#4) \ \ \ \ \ \ \log_{112/81} (11/8) = 1+ \log_{112/81}\left (\frac{110 \cdot 81}{112 \cdot 80} \right ) = $$ $$ = 1+ \log_{112/81} \left (1- \frac{2}{122} \right ) - \log_{112/81}\left ( 1-\frac{1}{81} \right ) < $$ $$ < 1+ \frac{1}{\ln(112/81) } \left ( -\frac{2}{122} + \frac{1}{81} \right ) < 1 $$

We can multiply inequality (3) by the (4), and using $\log_x y \log_y z = \log_x z$:

$$ (\#5) \ \ \ \ \ \ \log_{11/8}(3/2) < \frac{49}{57} \frac{7}{4} \Rightarrow \log_{112/81}(3/2) = \log_{112/81}(11/8) \log_{11/8}(3/2) < \frac{49}{57} \frac{7}{4} $$

Taking reciprocals and adding 4 we get

$$ (\#6) \ \ \ \ \ \ \log_{3/2} \left ( \frac{112}{81} \frac{81}{16} \right) = \log_{3/2}(7) > $$ $$ > 4+ \frac{57}{49} \frac{4}{7} = \frac{57}{49} \cdot 4 - \frac{8}{49} \cdot 4 + \frac{57}{49} \frac{4}{7} = $$ $$ = \frac{57}{49} \frac{32}{7} - \frac{32}{7} \frac{7}{49} = \frac{50}{49} \frac{32}{7} $$

Consider the following inequality $$ (\#7) \ \ \ \ \ \ \log_{75/49}(3/2) = 1+ \log_{75/49} \left ( \frac{49 \cdot 75}{75 \cdot 50} \right ) = $$ $$ = 1+ \log_{75/49} \left ( 1- \frac{1}{50} \right ) > 1+ \frac{1}{\ln(75/49) } (- \frac{1}{50} + \frac{1}{50^2}) > $$ $$ > 1- 2 \cdot \frac{1}{51} > 1- \frac{1}{50} = \frac{49}{50} $$ To show (7) we used, between the second and the third row, that $$ (75/49)^2 < (75/48)^2 = (25/16)^2 < e \Rightarrow \frac{1}{\ln(75/49) } = \log_{75/49}(e) > 2 $$ Indeed, $625 < 256 \cdot e$. We are almost finished: combining the inequalities

$$\log_{3/2}(7) > \frac{50}{49} \frac{32}{7}, \ \ \color{red}{\log_{75/49}(3/2) > \frac{49}{50}} $$

we get $ \log_{75/49}(7) > \frac{32}{7}$. Taking inverses and adding 2 we get

$$ 2+ \log_7(75/49) = \log_7(75) < 2+ \frac{7}{32} = \frac{71}{32} $$

Putting this to the exponent of $7$ we get $$ 75 < 7^{71/32} \Rightarrow 75^{32} < 7^{71} $$

as desired!

$\color{green}{\textbf{Just now!}}$

$$\ln\dfrac{75^{32}}{7^{71}}=\ln\left(\dfrac{20}{21}\left(\dfrac{2400}{2401}\cdot\dfrac{225}{224}\right)^{14}\dfrac{78125}{78732}\right)$$ $$=\ln\left(\dfrac{41-1}{41+1}\left(\dfrac{4801-1}{4801+1}\cdot\dfrac{449+1}{449-1}\right)^{14}\dfrac{156857-607}{156827+607}\right)$$ $$= 2\sum\limits_{k=1}^\infty\dfrac1{2k-1}\left(-\dfrac1{41^{2k-1}}-\dfrac{14}{4801^{2k-1}}+\dfrac{14}{449^{2k-1}}-\dfrac{607^{2k-1}}{156827^{2k-1}}\right)$$ $$< 2\left(-\dfrac1{41}-\dfrac1{4\cdot41^3}-\cdot\dfrac{14}{4801}+\dfrac{14}{449}-\dfrac{607}{156827}\right)$$ $$-\dfrac1{6\cdot41^3}+ \dfrac1{48\cdot449^2}\left(1+\dfrac{5}{3\cdot 449^2}+\dfrac{5^2}{3^2\cdot 449^4}+\dots\right) <0.$$ Proved!

$\color{brown}{\textbf{Previous version.}}$

Equivalent inequality is $$71\ln 7 > 32\ln3+64\ln 5.$$

Taking in account numeric equalities $$7^5=16807,\quad 3^3\cdot 5^4=16875,\quad 5^6 = 15625,\quad 3^7\cdot7 = 15309,$$ one can denote $$2\ln5-3\ln3=\ln\dfrac{25}{27} = \ln\dfrac{1-x}{1+x},\quad x = \dfrac1{26},$$ $$3\ln3+4\ln5-5\ln 7= \ln \dfrac{3^3\cdot5^4}{7^5} = \ln\dfrac{1+y}{1-y},\quad y = \dfrac{34}{16841},$$ $$7\ln3+\ln7-6\ln5 = \ln \dfrac{3^7\cdot7}{5^6} = \ln\dfrac{1-z}{1+z},\quad z = \dfrac{158}{15467}.$$

Easily to check expression for the goal sum: $$S=32\ln3+64\ln 5-71\ln7 = \ln\dfrac{1-x}{1+x}+14\ln\dfrac{1+y}{1-y}-\ln\dfrac{1-z}{1+z}.$$ If $\;x,y,z,t>0\;$ then $$S = -\ln\dfrac{1+x}{1-x}+14\ln\dfrac{1+y}{1-y}+\ln\dfrac{1+z}{1-z},$$ $$\ln\dfrac{1+t}{1-t} = \ln(1+t)-\ln(1-t) = 2t +\dfrac23t^3+\dfrac25t^5+\dfrac27t^7+\dots,$$ $$S_1=-\ln\dfrac{1+x}{1-x} < -2x-\dfrac23x^3 = -\dfrac{2x(3+x^2)}{3}$$ $$S_1<-\dfrac{2029}{26364}<-0.076\,961\,007,$$ $$S_2=14\ln\dfrac{1+y}{1-y}<28y(1+y^2+y^4+\dots)=\dfrac{28y}{1-y^2},$$ $$S_2<\dfrac{28\cdot34\cdot16841}{16841^2-34^2}<0.056\,528\,941,$$ $$S_3=\ln\dfrac{1+z}{1-z}\le2z+\dfrac23z^3(1+z^2+z^4+\dots) =2z+\dfrac23\,\dfrac{z^2}{1-z^2} =\dfrac{2z}{3}\dfrac{3-2z^2}{1-z^2},$$ $$S_3 <\dfrac{316}{46401}\dfrac{3\cdot15467^2-2\cdot158^2}{15467^2-158^2}<0.020\,431\,305$$ $$S=S_1+S_2+S_3 < -0.000\,000\,761 < 0.$$

Proved!

Here's a basic approach where the overwhelming majority of the work is squaring three 9-digit numbers. Make of that what you will!

We find that $75$ is $135$ in base 7. I'll write $\ldots$ to mean some sequence of zeros. Successively square using arithmetic in base 7 to get

\begin{align*} 135^1 &= 135 \\ 135^2 &= 22254 \\ 135^4 &= 22254^2 = 532640502 \\ 135^8 &= 532640502^2 = 420605123423162604 < 420605124\ldots \\ 135^{16} &< 420605124\ldots^2 < 243433061\ldots \\ 135^{32} &< 243433061\ldots^2 < 66666663\ldots \end{align*}

If you count the number of $0$'s in the final $\ldots$, you'll see that $135^{32}$ (in base 7) is at most 71 digits, which is less than $7^{71}$ which is 72 digits.

The $22254^2 = 532640502$ step would be tedious by hand, but really not bad. The obnoxious bit would be $532640502^2 = 420605123423162604$ and the two virtually identical calculations after it. Strictly speaking you only have to do enough calculations to assure yourself the claimed upper bounds hold, though that probably doesn't help much.

You could use Karatsuba's algorithm to make the big squaring operations less painful. For instance,

\begin{align*} 532640502^2 &= (5326\ldots + 40502)^2 \\ &= 5326\ldots^2 + 2 \cdot 5326\ldots \cdot 40502 + 40502^2 \\ &= 42051211\ldots + 630111343\ldots + 2255562604 \\ &= 4206051233(\cdots) \\ &< 420605124\ldots. \end{align*}

In all you'd need to do 4 5-digit squares, 3 4-digit squares, 3 4-digit and 5-digit products, and some easy additions and other little things. That's actually getting pretty reasonable.