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?


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.

  • $\begingroup$ +1: But you are probably missing the case when $S=n+1$. $\endgroup$ – Aryabhata Nov 4 '10 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 Nov 4 '10 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$ – Rahul Nov 4 '10 at 9:04
  • $\begingroup$ @Rahul: No worries, you don't have to apologize :-) $\endgroup$ – Aryabhata Nov 4 '10 at 14:24
  • $\begingroup$ Yes, you are right. $\endgroup$ – Aryabhata Nov 4 '10 at 14:27

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

  • $\begingroup$ @Rahul: I suppose this is similar as what you have. I think this is quite simple and intuitive, though. $\endgroup$ – Aryabhata Nov 3 '10 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$ – Rahul Nov 3 '10 at 22:06
  • $\begingroup$ @Rahul: You are right. I have edited it. $\endgroup$ – Aryabhata Nov 3 '10 at 22:34
  • $\begingroup$ Is there a particular reason why you chose to argue through the derivative and not Descartes' rule of signs? $\endgroup$ – Willie Wong Nov 3 '10 at 23:00
  • $\begingroup$ @Willie: The derivative is particularly nice and trying to visualize the graph is always intuitive :-) $\endgroup$ – Aryabhata Nov 3 '10 at 23:06

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).

  • $\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$ – Rahul Nov 3 '10 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$ – Bill Dubuque Nov 5 '10 at 23:08
  • $\begingroup$ Thanks! Your update is very illuminating. $\endgroup$ – Rahul Nov 6 '10 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.