Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

3 Answers 3

up vote 11 down vote accepted

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

share|improve this answer
    
Where is the induction ? –  Belgi Oct 7 '12 at 22:31
    
In the cancelation. –  Norbert Oct 7 '12 at 22:32
1  
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
3  
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.

share|improve this answer

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!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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