# Prove the following identity without using induction: $\sum\limits_{i=0}^n a^i = \frac{1-a^{n+1}}{1-a}$ for $a\neq1$

I'm struggling with proving $$\sum^n_{i=0}a^i = \frac{1-a^{n+1}}{1-a}$$ for $a\neq1$, not sure where to start.

-
Do you mean $a^{n+1}$? – draks ... Oct 7 '12 at 22:25
The question cannot be answered without a precise definition of a "proof without induction". For example, is a proof that invokes a lemma that uses induction considered to be a proof without induction? – Bill Dubuque Oct 7 '12 at 22:41

No matter how you organize you proof you will use induction, may be implicitly. Here is an attempt to show a proof that seems not uses induction. Let $$S=1+a+a^2+\ldots+a^n$$ then $$a S=a(1+a+a^2+\ldots+a^n)=a+a^2+a^3+\ldots+a^{n+1}$$ and $$(1-a)S=S-aS=(1+a+a^2+\ldots+a^n)-(a+a^2+a^3+\ldots+a^{n+1})=1-a^{n+1}$$ Since $(1-a)S=1-a^{n+1}$, then dividing by $1-a$ we get $$S=\frac{1-a^{n+1}}{1-a}$$

-
Where is the induction ? – Belgi Oct 7 '12 at 22:31
In the cancelation. – Norbert Oct 7 '12 at 22:32
I don't think this one use induction. – Patrick Li Oct 7 '12 at 22:38
Great answer, thanks very much! – mirai Oct 7 '12 at 22:44
Every time you manipulate with unknown amount of summands you use induction, explicitly or implicitly – Norbert Oct 7 '12 at 22:44

Let $f(0)=0$ and for $k \gt 0$ let $f(k)=\dfrac{1-a^{k+1}}{1-a}$. Note that $$f(k)-f(k-1)=\frac{1-a^{k+1}}{1-a}-\frac{1-a^k}{1-a}=\frac{a^k(1-a)}{1-a}=a^k.$$ It follows that $$1+a+a^2+\cdots +a^n=(f(1)-f(0))+(f(2)-f(1))+(f(3)-f(2))+\cdots +(f(n)-f(n-1)).$$ Open the parentheses on the right, and observe the mass cancellation (telescoping).

Remark: Any of the usual sum results can be mechanically transformed in an analogous way into a telescoping argument.

As for avoiding induction, one cannot, and the above proof does not. Telescoping that involves $5$ terms, or $500$ terms, does not require induction. Telescoping with "$n+1$" terms does require induction.

-

Almost as in the other answers, consider $P=(1-X)(\sum_{i=0}^nX^n)$. From the way it is formed, $P$ is a polynomial in $X$ of degree $1+n$ (did I use induction yet?). Now let $i\in\{1,\ldots,n\}$ and consider the coefficient $c_i$ of $X^i$ in $P$. From the definition of polynomial multiplication we have $c_i=1\times1_i-1\times 1_{i-1}=0$, where the subscripts on the $1$'s are just to indicate the degree of the term of $\sum_{i=0}^nX^n$ that they were obtained as coefficient of (these coefficients are all $1$ up to degree $n$ inclusive). Also the constant term of $P$ is $1\times 1=1$, and the leading term of $P$ is $-X.X^n=-X^{n+1}$. So $P=1-X^{n+1}$, as there cannot be any other terms. Now substitute $X:=a$ to obtain $(1-a)(\sum_{i=0}^na^n)=1-a^{n+1}$ and finallly divide by $a-1\neq0$.

It is a bit tiresome, but I think you will find it hard to point out where I used induction. And I didn't even write ellipses once!

-