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.
Prove the following identity without using induction: $\sum\limits_{i=0}^n a^i = \frac{1-a^{n+1}}{1-a}$ for $a\neq1$
-
0The 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? – 2012-10-07
3 Answers
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} $
-
0@Mike it takes induction to give a mathematical meaning to the sign $a^k$ not to mention $\sum\limits_{i=1}^n a^i$ – 2012-10-07
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!