Two versus One

Number Theory Level 4

Find the smallest positive integer $n$ for which

$n^{50} + (n+1)^{50} \gt (n+2)^{50}.$

Inspiration

The answer is 103.

2 solutions

Brian Charlesworth
Mar 24, 2017

Letting $m = n + 1$ , the given equation can be rewritten as

$m^{50} \gt (m + 1)^{50} - (m - 1)^{50} \Longrightarrow 1 \gt \left(1 + \dfrac{1}{m}\right)^{50} - \left(1 - \dfrac{1}{m}\right)^{50} \Longrightarrow$

$1 \gt \displaystyle\sum_{k=0}^{50} \dbinom{50}{k}\dfrac{1}{m^{k}} - \sum_{k=0}^{50} \dbinom{50}{k} \dfrac{(-1)^{k}}{m^{k}} \Longrightarrow$

$1 \gt \dfrac{100}{m} + \dfrac{39200}{m^{3}} + \dfrac{4237520}{m^{5}} + O(m^{-7}) \Longrightarrow$

$m \gt 100 + \dfrac{39200}{m^{2}} + \dfrac{4237520}{m^{4}} + O(m^{-6}) \Longrightarrow$

$m^{2}(m - 100) \gt 39200 + \dfrac{4237520}{m^{2}} + O(m^{-4})$ .

Now from the inspiration problem we know that $m \gt 100$ , so the RHS of the equation will max out at about $39200 + 425$ , so we are looking for the least $m$ such that $m^{2}(m - 100) \gt 39625$ . But as $m \gt 100$ we have that $m^{2}(m - 100) \gt 10000(m - 100)$ , so $m = 104$ is the least $m$ that will accomplish the task, giving us $n = m - 1 = \boxed{103}$ .

(Just as a check, note that $3 \times 103^{2} = 31827$ and $4 \times 104^{2} = 43264$ .)

Moderator note:

This problem ties together several different ideas in mathematics. Having a strong understanding of the basics allows us to make quick deductions on how best to proceed approximating the answer.

If you do not know initially that m is greater then 100 then how you will proceed ?

Kushal Bose - 4 years, 2 months ago

I suppose I didn't really need to reference the inspiration problem here, since from the second to last inequality in my calculation it is clear that $m \gt 100$ . in which case $m^{2}(m - 100) \gt 39625$ is an appropriate inequality to work with. I suppose we could take one more step and let $k = m - 100 \gt 0$ , giving us

$(100 + k)^{2}\times k \gt 39625 \Longrightarrow$

$k \gt \dfrac{39625}{(100 + k)^{2}} \gt \dfrac{39625}{100^{2}} = 3.9625 \Longrightarrow k \ge 4$ .

Brian Charlesworth - 4 years, 2 months ago

But doesn't n = 10 make the initial inequality wrong?

Loppukilpailija - 4 years, 2 months ago

Sorry! Someone completely changed my original problem without any input from me. The powers should be $50$ and not $5$ . I've changed it back to its original form.

P.S.. I've noticed your report. Hopefully you'l get credit for a correct answer soon. :)

Brian Charlesworth - 4 years, 2 months ago

Sir, I tried to solve it in a different way but ended up in a confusion. Please let me know where I did mistake.Here is my approach. Take logarithm on both sides, we get Log(n^50+(n+1)^50) > log((n+2)^50) We know that log( a+b)=log a log b , we get Log(n^50) log((n+1)^50) > log ((n+2)^50) We know that log(a^x)=x log a, we get 50 50 log (n) * log (n+1) > 50 log (n+2) Now cancelling 50 and applying log a * log b= log (a+b), we get 50 log(2n+1) > log (n+2) =>(2n+1)^50 > (n+2)

To satisfy the above equation, the least value of n be 1. But if I substitute n=1 in the given equation, it is not satisfying.

Please let me know the mistake I made in solving the problem

chetan kakarlapudi - 4 years, 2 months ago

The rule for logs is that $\log(ab) = \log(a) + \log(b)$ , and not the equation $\log(a + b) = \log(a)\log(b)$ . Try $a = b = 1$ in your equation, for example. $\log(a + b)$ would equal $\log(2) \ne 0$ , but $\log(a) + \log(b) = \log(1) + \log(1) = 0$ .

Brian Charlesworth - 4 years, 2 months ago

...or you just go use Excel like I did

Gabriel Collares - 4 years, 2 months ago

This is whack! What class would one normally have to have completed to know this?

Thomas N Dowling - 4 years, 2 months ago

I would think a high school senior on the math team would have the knowledge and problem-solving ability to solve this analytically.

Brian Charlesworth - 4 years, 2 months ago

what is $o(m^{-7} )$ ? very nice problem btw.

Mehdi K. - 4 years, 2 months ago

This is known as Big_O notation . So $O(m^{-7})$ means that all the remaining powers in the series are $\le -7$ .

Brian Charlesworth - 4 years, 2 months ago

What is the operation involved in the summation of 1/m^k from 0 to 50 and why? Also, i don't get the big_o notation. Thanks!

Patrick Cuenco - 4 years, 1 month ago

The summations are the expansions of $(1 + \frac{1}{m})^{50}$ and $(1 - \frac{1}{m})^{50}$ using the Binomial Theorem .

The Big-O notation $O(m^a)$ means that all the remaining powers in the series are $\le a$ . This is meant to indicate thus their contributions to the sum are increasingly negligible, and the Big-O notation just "collects" them all in one expression.

Brian Charlesworth - 4 years, 1 month ago

Ed Sirett
Apr 6, 2017

Brute force it in 3ms!
I do hope I get a lot of downvotes for 'cheating'

#include <fstream>
#include <iostream>
#include <gmpxx.h>

using namespace std;

void pow50( int base , mpz_class& retval )
{
retval=1;
for (int i=1; i<=50; i++)
     retval *= base;
}

int main()
{
    mpz_class a,b,c;
    int n=0;
    do {
         n += 1;
         pow50(n, a);
         pow50(n+1, b);
         pow50(n+2, c);
    } while( a+b < c);
    cout <<  "n = " << n << endl;
    return 0;
}

Gives:
n = 103
Process returned 0 (0x0) execution time : 0.003 s

I cheated too, but I didn't have the time to write a program. Thank god for google's feature of not having to press enter to give an answer.

harrison truscott - 4 years, 2 months ago

Nothing wrong with brute force, especially when it confirms the analytic result. :)

Thanks for posting your program. (+1)

Brian Charlesworth - 4 years, 2 months ago

power = 50
for i in range (1,1000):
    if (i)**power+(i+1)**power>(i+2)**power:
        print i
        break

Michael Fitzgerald - 3 years, 3 months ago

.I did the same way but on Keisan Online Calculator.
Tried 1,1,100; 1001,1,100; 50,1,200, just not to give much work to calculator !!! Used function n^50+(n+1)^50 - (n+2)^50 . Checked for change of sign.

Niranjan Khanderia - 2 years, 3 months ago

Two versus One

The answer is 103.

2 solutions

Moderator note:

0 pending reports