# Proof by Induction: $\sum_0^nx^i=(1-x^{n+1})/(1-x)$

I'm trying to do my Maths assignment but I can't get this done. I can do other questions but this one is different. This is a picture of the question.

My usual first step is to proof it when n = 1. But the problem is, that I don't know what x is. It says x is not equal to 1, but I still don't know what to do next.

Thank you.

-
The result need to be independent of what $x$ is (except of course $x \ne 1$). – Peter Grill Oct 31 '12 at 0:41
No matter what $x$ is, when $n=1$ the left side is $1+x$ and the right side is $(1-x^2)/(1-x)$, right? – Gerry Myerson Oct 31 '12 at 0:43
@GerryMyerson How's the left side 1 + x? x ^i = x ^ 0 = 1. Right? – Adegoke A Oct 31 '12 at 0:46
Yes, so the left side is $x^0+x^1$, which is $1+x$. – Gerry Myerson Oct 31 '12 at 0:55

Induction involving $x$ is no different from other types of induction. Just treat $x$ normally and we can still prove it for the general case.

Let $$P_n:=\sum_{i=0}^nx^i=\frac{1-x^{n+1}}{1-x}$$

Then for the base case i.e. $n=0$ we have $$\sum_{i=0}^0x^i=\frac{1-x^{1+0}}{1-x}$$ $$1=\frac{1-x}{1-x}$$ $$1=1$$

He have esablished the RHS=LHS and so $P_0$ is true.

Now assume that the statement is true for n. $$\sum_{i=0}^nx^i=\frac{1-x^{n+1}}{1-x}$$

We must show that it is also true for $n+1$.

For the RHS we have $$RHS=\frac{1-x^{(n+1)+1}}{1-x}=\frac{1-x^{n+2}}{1-x}$$

And for the LHS we have $$LHS=\sum_{i=0}^{n+1}x^i=\sum_{i=0}^{n}x^i+x^{n+1}=\frac{1-x^{n+1}}{1-x}+x^{n+1}=\frac{1-x^{n+1}}{1-x}+\frac{x^{n+1}(1-x)}{(1-x)}$$ $$=\frac{1-x^{n+1}+x^{n+1}(1-x)}{1-x}=\frac{1-x^{n+1}+x^{n+1}-x^{n+2}}{1-x}=\frac{1-x^{n+2}}{1-x}$$ Since LHS=RHS $P_{n+1}$ is true. The rest follows.

-
Did you notice that this was an assignment problem? Did you not want to leave anything for OP to do? – Gerry Myerson Oct 31 '12 at 6:00

It doesn't matter what $x$ is, as long as it isn't $1$ (so $1-x$ isn't $0$, and you can divide by it). Just treat it as a normal inductive proof:

Suppose $\sum_{i=0}^{n}{x^{i}}=\frac{1-x^{n+1}}{1-x}$. Then

$$\sum_{i=0}^{n+1}{x^{i}}=\sum_{i=0}^{n}{x^{i}}+x^{n+1}=\frac{1-x^{n+1}}{1-x}+x^{n+1}=\frac{(1-x^{n+1})+(1-x)x^{n+1}}{1-x}$$

$$=\frac{1-x^{n+2}}{1-x},$$

which completes the inductive step.

The base case $n=0$ is LHS=$x^{0}+x^{1}=1+x$ (no matter what $x$ is), RHS=$\frac{1-x^{2}}{1-x}=1+x$, so it's true for all $n$.

-

For $n=1$, the right hand side is

\begin{align*} \frac{1 - x^2}{1-x} &= \frac{(1-x)(1+x)}{1-x} \\ &= 1+x, \quad x \ne 1 \end{align*}

which is identical to the right hand side.

-
But what about x^1? x^i =1. 1 does not equal to 1 + x. – Adegoke A Oct 31 '12 at 0:50
The left hand side for $n=1$ expands to $x^0+x^1 = 1 + x, x \ne 0$ – Peter Grill Oct 31 '12 at 0:53

You need to let $x$ be an arbitrary number, which is just not $1$.

For the base case ($n = 0$): We have $$x^0 = 1 = \frac{1-x}{1-x} = \frac{1-x^{0+1}}{1-x}$$ So the theorem holds in the base case.

For the inductive step: $$\sum_{i=0}^{n+1} x^i = \sum_{i=0}^{n} x^i + x^{n+1}$$

And by induction we know $\sum_{i=0}^n x^i = \frac{1 - x^{n+1}}{1-x}$, so plugging this in we get $$\sum_{i=0}^{n+1}x^i = \frac{1-x^{n+1}}{1-x} + x^{n+1} = \frac{1-x^{n+1}}{1-x} + \frac{(1-x)x^{n+1}}{1-x} = \frac{1 - x^{n+2}}{1-x}.$$

So by induction we're done.

One can also note that there is another proof, without induction that is neater.

$$(\sum_{i=0}^{n} x^i) (1-x) = \sum_{i=0}^{n} x^i - \sum_{i=0}^{n} x^{i+1} = 1 - x^{n+1}$$ because all the terms in the middle cancel out.

-