Application of Newton-Raphson: OMO Spring 2018

This year’s OMO included this problem:

13. Find the smallest positive integer n for which the polynomial \displaystyle x^n-x^{n-1}-x^{n-2}-\cdots -x-1 has a real root greater than 1.999.

Solution. 

Equivalently, the polynomial is \displaystyle x^n-\frac{x^n-1}{x-1}=x^{n+1}-2x^n+1=0 if x=1 is ignored. At this point you may be tempted to continue playing with the polynomial, but then you recall that sick method you learned called Newton’s method. Unfortunately, you forgot exactly how it looks like, but thankfully your wits haven’t left you yet, since you know that the method is based on the first order approximation of a Taylor series around a best-guess for the root: \displaystyle f(x)=f(a)+f'(a)(x-a)=0. Rearranging, we have \displaystyle x=a-\frac{f(a)}{f'(a)} . In this case, a is quite obviously 2, so we have \displaystyle 2-\frac{2^{n+1}-2\cdot 2^n+1}{(n+1)2^n-n\cdot 2\cdot 2^{n-1}}=2-\frac{1}{2^n}. The problem wants to minimize \displaystyle x>1.999\implies 2-\frac{1}{2^n}>2-\frac{1}{10^3}\implies \frac{1}{2^n}<\frac{1}{10^3}. Thus the answer is \displaystyle \boxed{10}.

\displaystyle \rule{8cm}{0.4pt}

Bonus. Solution to problem 18 of the same contest.

Suppose that a,b,c are real numbers such that a<b<c and a^3-3a+1=b^3-3b+1=c^3-3c+1=0. Find \displaystyle \frac{1}{a^2+b}+\frac{1}{b^2+c}+\frac{1}{c^2+a}.

Solution. 

Really, we are just finding the three solutions to the the cubic \displaystyle x^3-3x+1, which can be done easily with Cardano’s method, which you have also forgotten. Nonetheless, you are willing to do some exploring.

Note that \displaystyle (s+t)^3-3(s+t)st=s^3+t^3, and comparing this form to the cubic, we see that we want \displaystyle 3st=3 and \displaystyle s^3+t^3=-1 where s+t are the solutions. Rewriting the latter equation in terms of t, (or s it doesn’t matter), we find that \displaystyle (t^3)^2+t^3+1=0\implies t^3=\frac{-1\pm i\sqrt{3}}{2}=e^{\frac{2\pi i}{3}}\implies t=e^{\frac{2\pi i}{9}} (the above is just one of two solutions). Check out shameless plug if you need a refresher. We also get \displaystyle s=e^{\frac{-2\pi i}{9}}, so that \displaystyle s+t=2\cos\left(\frac{2\pi}{9}\right). The other solution is \displaystyle 2\cos\left(\frac{4\pi}{9}\right). Unfortunately, it seems the other two solutions \displaystyle e^{\frac{-4\pi i}{9}}+e^{\frac{2\pi i}{9}},\quad e^{\frac{4\pi i}{9}}+e^{\frac{-2\pi i}{9}} are much more complicated (they are not even real). Going back to the first step, we realize that instead of s+t, sw^2+tw works just as well (where w is the primitive third root of unity), yielding the solution \displaystyle w^{-2/3}w^2+w^{1/3} w=2\cos\left(\frac{8\pi}{9}\right). Putting these three solutions in order, we get \displaystyle a=2\cos\left(\frac{8\pi}{9}\right),b=2\cos\left(\frac{4\pi}{9}\right),c=2\cos\left(\frac{2\pi}{9}\right). At this point, you could just whip out your four-function calculator (which is allowed on the test) and bash out the values with a power series expansion, but obviously there is no insight here (if you are going to do this, note that you want to re-write everything in terms of c, since small angles have better approximations).

Instead, we note that \displaystyle a^2=2+c,\quad b^2=2+a, \quad c^2=2+b,\quad a+b+c=0 where the first set of equalities follows from the double angle formula and the last one follows from Vieta. Combining these, we get \displaystyle a^2+b=2-a,\quad b^2+c=2-b,\quad c^2+a=2-c, so that we want to evaluate \displaystyle \sum_i ^3 \frac{1}{2-r_i} where r_i are the roots of f(x) =x^3-3x+1.

\displaystyle \rule{8cm}{0.4pt}

Lemma. \displaystyle \sum_i ^n \frac{1}{x-r_i}=\frac{f'(x)}{f(x)} for polynomials f(x) of the nth degree with n distinct roots r_i.

Proof 1. \displaystyle \int\sum_i ^n \frac{1}{x-r_i}\, dx=\int\frac{f'(x)}{f(x)}\, dx We get \displaystyle \log\left(\prod_i^n (x-r_i)\right)=\log f(x) from the LHS and substituting u=f(x) on the RHS we get \displaystyle \int \frac{f'(x)}{u}\frac{du}{f'(x)}=\log u +c=\log f(x)+c and considering initial conditions, c=0.

Proof 2. \displaystyle f(x)=\prod_i (x-r_i) By the product rule, \displaystyle f'(x)= \sum_{i=1}^n \prod_{j=1, j\neq i}^n (x-r_j)=f(x)\sum_i \frac{1}{x-r_i}.

Remarks. This lemma assumed that all roots have multiplicity 1, since our cubic has this property. The general case requires only trivial modifications and is left as an exercise for the reader.

Corollary 1. A polynomial with roots of multiplicity 1 shares no roots with its derivative.

Corollary 2. Let \rho be a root of f'(x) . Then \displaystyle \sum_{i} \frac{1}{\rho-r_i}=0.

Corollary 3. The harmonic mean of the roots is equal to -n\frac{f(0)}{f'(0)}. Note that this can be easily seen from Vieta as well.

\displaystyle \rule{8cm}{0.4pt}

Thus, the answer is \displaystyle\frac{f'(2)}{f(2)}=\boxed{3}.

Leave a Reply

Your email address will not be published. Required fields are marked *