11
$\begingroup$

Américo Tavares pointed out in his answer to this question that finding the ratio of a geometric progression only from knowledge of the sum of its first $n+1$ terms $S = 1+x+x^2+\cdots+x^n$ amounts to solving a polynomial of degree $n$. This suggested to me that there might be up to $n$ real solutions of $x$ for a given sum, but I could not find any. In fact, it turned out that the following fact is true:

For $n \ge 1$ and $S \in \mathbb{R}$, the polynomial equation $x^n + x^{n-1} + \cdots + x + 1 = S$ has at most two real solutions.

A corollary is that if $n$ is odd, there is exactly one real solution. I was only able to prove this using a rather contrived geometric argument based on the shape of the graph of $y = x^{n+1}$. Is there a simple, direct (and ideally, intuitive) proof of this fact?

$\endgroup$
0

3 Answers 3

13
$\begingroup$

In between the previous two answers - one very specific and one very general, there is the following one:

Rolle's theorem states that between any two zeros of the function lies a zero of the derivative. So each time you differentiate the number of real roots can not decrease by more than 1. This actually holds with multiplicity as well - if a root is of multiplicity k, then it is of multiplicity (k-1) for the derivative, and there are still roots of the derivative strictly between consecutive distinct roots of the original function. So $x^{n+1}−Sx+S−1$ has at most one root more than $(n+1)x^n-S$ and at most two more than $n(n+1)x^{n-1}$, so not more than three total (counted with multiplicity). One of those is $x=1$, so there are no more than two for the $1+x+\ldots+x^n=S$. QED.

$\endgroup$
5
  • $\begingroup$ +1: But you are probably missing the case when $S=n+1$. $\endgroup$
    – Aryabhata
    Commented Nov 4, 2010 at 5:41
  • $\begingroup$ Nope. All the counts are with multiplicity, so the case when x=1 is a multiple root is included. $\endgroup$
    – Max
    Commented Nov 4, 2010 at 7:53
  • $\begingroup$ After thinking about it some more, I like the conciseness of this answer, which seems like a viewing of the content of Moron's answer in a broader light. @Moron: Sorry for changing my accepted answer. $\endgroup$
    – user856
    Commented Nov 4, 2010 at 9:04
  • $\begingroup$ @Rahul: No worries, you don't have to apologize :-) $\endgroup$
    – Aryabhata
    Commented Nov 4, 2010 at 14:24
  • $\begingroup$ Yes, you are right. $\endgroup$
    – Aryabhata
    Commented Nov 4, 2010 at 14:27
12
$\begingroup$

The roots are also roots of

$x^{n+1} - Sx + S - 1 = 0$

which we get by multiplying your equation by $x-1$.

This polynomial ($x^{n+1} - Sx + S-1$), as we move from $x = -\infty$ to $x = \infty$ is either

  • Monotonically increasing, and thus has at most one real root.

  • Monotonically decreasing, and then monotonically increasing and hence can have at most two real roots.

  • Monotonically increasing, then decreasing and then again increasing (happens only when $n$ is even). In which case there are at most three real roots, one of which is $1$. So for $S \ne n+1$, the original equation does not have more than two solutions. If $S=n+1$ and $n$ is even, then the turning points are $-1$ and $1$ and the value of the polynomial at $-1$ is positive. So the only roots are $1$ and a root which is $< -1$.

This can be seen by looking at its derivative, which is an increasing function for odd $n$, and for even $n$, it is positive, then possibly negative (depending on $S$) and then positive again, as we move from $x = -\infty$ to $x = \infty$.

$\endgroup$
5
  • $\begingroup$ @Rahul: I suppose this is similar as what you have. I think this is quite simple and intuitive, though. $\endgroup$
    – Aryabhata
    Commented Nov 3, 2010 at 21:52
  • 1
    $\begingroup$ This is indeed quite similar to what I got, but I think more care is needed for a complete proof. For even $n$, the derivative is not an increasing function, and when $n = 2, S = 1$ the polynomial $x^3 - x$ falls in neither of your cases. One would have to argue that there are at most three roots, one of them is $x = 1$, and that one is not a solution to the original equation. $\endgroup$
    – user856
    Commented Nov 3, 2010 at 22:06
  • $\begingroup$ @Rahul: You are right. I have edited it. $\endgroup$
    – Aryabhata
    Commented Nov 3, 2010 at 22:34
  • $\begingroup$ Is there a particular reason why you chose to argue through the derivative and not Descartes' rule of signs? $\endgroup$ Commented Nov 3, 2010 at 23:00
  • $\begingroup$ @Willie: The derivative is particularly nice and trying to visualize the graph is always intuitive :-) $\endgroup$
    – Aryabhata
    Commented Nov 3, 2010 at 23:06
12
$\begingroup$

A powerful algorithmic way to handle such problems is to employ Sturm's Theorem. If you work out the details you will see that it is quite simple for this example. This in turn is a special case of the CAD (cylindrical algebraic decomposition) algorithm - an effective implementation of Tarski's quantifier elimination for the first order theory of the reals. The general ideas behind these methods prove helpful in solving a variety of problems. It's well worth the effort to learn the general methods rather than ad-hoc techniques.

Per Rahul's request, here are further details of applying Sturm's algorithm to the example at hand. We desire to prove that $\rm\ \ g(x) =\ x^n +\:\cdots\: + x^2 + x + 1 - s\ \ $ has at most two distinct real roots. Consider $\rm\ f(x) = (x-1)\ g(x) =\ x^{n+1}-1-s\ (x-1)\:.\ $ Since $\rm\ \ f\:' = (n+1)\ x^n - s\ \ $ we have $\rm\ f\ mod\ f\:'\: =\ f\: - \: x/(n+1)\ f\:'\ =\ a\ x + b\ $ for some $\rm\:a,\:b\in \mathbb R\:$. So the euclidean remainder sequence in the calculation of $\rm\ gcd(f,\:f\:')\ $ has length at most $4$, viz. $\rm\ f,\ f\:',\ a\ x + b,\ c\ $. Thus it has at most $3$ sign changes at any point, so Sturm's theorem implies that $\rm\ f(x)\ $ has at most $3$ distinct real roots. So if $\rm\: x = 1\:$ isn't a multiple root of $\rm \:f(x)\:$ then $\rm\ g(x) = f(x)/(x-1)\ $ has at most $2$ distinct real roots. Else $\rm\ x-1\:|\:gcd(f,\:f\:')\ \Rightarrow\ x-1\:|\:c\ \Rightarrow\ c=0\:$. So in this case the remainder sequence has length at most $3$, so at most $2$ sign changes, so $\rm\:f\ $ has at most $2$ distinct real roots, therefore ditto for $\rm\:g\:$.

Although Sturm's theorem is slightly more work here than Rolle's theorem, it has the added benefit that it allows one to compute the precise number of roots in any interval (versus only bounds using Rolle's theorem).

$\endgroup$
3
  • $\begingroup$ Ah, thanks, I was not aware of Sturm's theorem, which looks like quite a powerful result! I'm afraid I don't see how applying it to $x^n - 1$ solves the problem though. Could you clarify? It seems to me that one would have to apply it to $x^n + x^{n-1} + \ldots + x + 1$ or to $x^{n+1} - Sx + S - 1$, which can be done but is not quite simple in either case. $\endgroup$
    – user856
    Commented Nov 3, 2010 at 22:44
  • $\begingroup$ @Rahul: I edited my post to provide further details. As you can see Sturm's algorithm is both powerful and simple. $\endgroup$ Commented Nov 5, 2010 at 23:08
  • $\begingroup$ Thanks! Your update is very illuminating. $\endgroup$
    – user856
    Commented Nov 6, 2010 at 1:07

You must log in to answer this question.