Possible Duplicate:
Value of $\sum x^n$
Proof to the formula $$1+x+x^2+x^3+\cdots+x^n = \frac{x^{n+1}-1}{x-1}.$$
$\begingroup$
$\endgroup$
5
-
$\begingroup$ A proof is sketched here. $\endgroup$– J. M. ain't a mathematicianCommented Nov 24, 2010 at 14:59
-
5$\begingroup$ Can someone please fix the exponent in the title and content? $\endgroup$– user02138Commented Nov 24, 2010 at 18:37
-
$\begingroup$ See also math.stackexchange.com/questions/11618/… $\endgroup$– lhfCommented Nov 25, 2010 at 0:13
-
$\begingroup$ Proven inter alia in math.stackexchange.com/questions/29023/value-of-sum-xn/… $\endgroup$– Arturo MagidinCommented Apr 7, 2011 at 15:17
-
1$\begingroup$ This is Euclid book IX, proposition 35: aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX35.html $\endgroup$– user13618Commented Dec 31, 2011 at 4:33
Add a comment
|
7 Answers
$\begingroup$
$\endgroup$
Let $S=1+x+x^2+...+x^n$. Then, $xS=x+x^2+...+x^{n+1}=1+x+x^2+...+x^n+(x^{n+1}-1)=S+x^{n+1}-1$. So, $xS-S=x^{n+1}-1$. So, $S=\frac{x^{n+1}-1}{x-1}$. (The exponent of the $x$ in the numerator of the RHS should be $n+1$ not $n$).
$\begingroup$
$\endgroup$
6
Since $1-x^{n+1}$ has $1$ as a root, the quotient $\frac{1-x^{n+1}}{1-x}$ is a polynomial.
If $\mathbb F_q$ is a finite field with $q$ elements and $V$ is a $\mathbb F_q$-vector space of dimension $n+1$, then $\frac{1-q^{n+1}}{1-q}=|P(V)|$ is the cardinal of the projective space attached to $V$. Now $P(V)$ can be described as a disjoint union $$P(V)=\mathbb A^0\sqcup\mathbb A^1\sqcup \mathbb A^2\sqcup\cdots\sqcup\mathbb A^n$$ where $\mathbb A^k$ is, for each $k$, an affine space of dimension $k$ over $\mathbb F_q$ (which is a complicated way of saying, as far as our purposes go, a vector space over $\mathbb F_q$ of dimension $k$) Since $|\mathbb A^k|=q^k$, we find that $$\frac{1-q^{n+1}}{1-q}=1+q+q^2+q^3+\cdots+q^n$$ for all numbers $q$ which are powers of prime numbers. It follows that $$\frac{1-x^{n+1}}{1-x}=1+x+x^2+x^3+\cdots+x^n$$ as polynomials, because the equality holds for infinitely many values of $x$ (and we are working over $\mathbb Z$...)
answered Dec 14, 2010 at 15:58
-
2$\begingroup$ Hooray for swatting flies with nukes! :-) I think you need more justification for the formula for $|P(V)|$, though... $\endgroup$ Commented Dec 14, 2010 at 16:15
-
$\begingroup$ @Steven, $V\setminus0$ has $q^{n+1}-1$ elements, and $P(V)=(V\setminus0)/\mathbb F_q^\times$ is the quotient of $V\setminus0$ by the multiplicative action of the group $\mathbb F_q^\times$, which does not have fixed points. The formula for $|P(V)$ follows from counting the points in $P(V)$ grouped by orbits. $\endgroup$ Commented Dec 14, 2010 at 16:18
-
1$\begingroup$ @Steven, while this seems a bit silly, it is a rather good example of a general phenomenon, going all the way to motives, universal cohomology theories and what not! $\endgroup$ Commented Dec 14, 2010 at 17:57
-
$\begingroup$ Bravo, bravo! I quite like it. I want to read about "because the equality holds for infinitely many values of x (and we are working over Z...)". Do you have a reference? It's probably in my algebra book, and it does make sense. $\endgroup$ Commented Apr 7, 2011 at 8:04
-
1$\begingroup$ @Eivind: I am trying to prove that two polynomials $f$ and $g$ —the left and right hand sides of the last equality I wrofe— are equal, and I showed that $f-g$ has infinitely many zeroes: since $f-g$ is itself a polynomial, that can only happen if $f-g$ is identically zero. $\endgroup$ Commented Apr 7, 2011 at 12:59
$\begingroup$
$\endgroup$
HINT $\ \ $ The sum $\rm\:S\:$ is "almost" preserved by a shift symmetry $\rm\ S \to x\:S$
Examine the discrepancy $\rm\ x\:S - S\:.\ \ $ It's just the finite case of Hilbert's infinite Hotel
answered Nov 24, 2010 at 15:10
$\begingroup$
$\endgroup$
Observe that \begin{eqnarray} x^{n+1} - 1 = x^{n+1} + (x^{n} - x^{n}) + \cdots + (x - x) - 1 = (x^{n} + x^{n-1} + \cdots + x + 1)(x - 1). \end{eqnarray}
answered Nov 24, 2010 at 16:20
$\begingroup$
$\endgroup$
1
It equals (x^(n+1)-1)/(x-1), not what you wrote.
$\begingroup$
$\endgroup$
For a more mechanical proof, you could use induction. The proof then boils down to finding a common denominator:
$\frac{x^{n+1}-1}{x-1} + x^{n+1} = \frac{x^{n+1}-1+(x-1)x^{n+1}}{x-1} = \frac{x^{n+2}-1}{x-1}$
answered Nov 24, 2010 at 17:50
$\begingroup$
$\endgroup$
1
Since $$\frac1{1-x}=1+x+x^2+x^3+\cdots,$$ we have $$ \frac{1-x^{n+1}}{1-x}=(1+x+x^2+x^3+\cdots)-(x^{n+1}+x^{n+2}+x^{n+3}+x^{n+4}+\cdots) $$ And on the right hand side every thing cancels except $1+x+x^2+\cdots+x^n$.
(This argument is probably circular! :) )
answered Dec 14, 2010 at 15:47
-
$\begingroup$ Not necessarily - you could derive the formula for $1\over 1-x$ via Taylor series... :-) $\endgroup$ Commented Dec 14, 2010 at 16:14