# Reason behind particular induction step

I'm wondering why and how you get some of these steps in an Induction proof.

Okay, so the question is to prove the following statement by induction:

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

The first step that sort of confuses me is having a base case of $n=2$. Why would you start out with that, and not $n=1$? Maybe it's just trivial to show the $n=1$ base case.

Thes next step that also confuses me would be when we show that this is true for $n = k+1$

We write it out as:

$1 - x + x^2 - x^3$ $+ ... +$ $x^{2k-2} - x^{2k-1} + x^{2k} = \frac{x^{2k-1}+1}{x+1} - x^{2k-1} + x^{2k}$

I don't understand how two terms were added ($- x^{2k-1} + x^{2k}$)

Any sort of explanation of clarification would be helpful! Thanks.

-
Technically, there can be as many base cases as wanted. So I believe it was more out of observing that the case $n=1$ is trivial. –  Matt Groff Oct 29 '12 at 1:23
Remark $\$ It's simpler to prove more generally $\rm\ 1 + z + \,\cdots + z^k = \dfrac{1-z^{k+1}}{1-z}.\:$ Yours is the special case $\rm\:z = -x,\ k = 2n-2.$ –  Bill Dubuque Oct 29 '12 at 2:46
My guess is that if the first step was to test the base case of $n=2$, then the question asked you to prove it for $n\ge2$. –  Mike Oct 29 '12 at 4:28

Let $P(n)$ be the statement

$$1-x+x^2-x^3+\ldots+x^{2n-2}=\frac{x^{2n-1}+1}{x+1}\;;\tag{1}$$

you want to prove that $P(n)$ is true for all $n\ge 2$. (I’ll come back to the choice of $2$ later.) For the induction step you assume $P(k)$ for some $k\ge 2$ and try to prove $P(k+1)$. Let’s see what those statements really are. $P(k)$ is

$$1-x+x^2-x^3+\ldots+x^{2k-2}=\frac{x^{2k-1}+1}{x+1}\;,$$

obtained by substituting $k$ for $n$ in $(1)$. $P(k+1)$ is obtained similarly, by substituting $k+1$ for $n$ in $(1)$, so it’s

$$1-x+x^2-x^3+\ldots+x^{2(k+1)-2}=\frac{x^{2(k+1)-1}+1}{x+1}\;.$$

This can be simplified. First, the righthand side is clearly $$\frac{x^{2k+1}+1}{x+1}\;.$$ The lefthand side is $1-x+x^2-x^3+\ldots+x^{2k}$; if you display a couple more terms, working backwards from the end, you’ll see that it’s

$$1-x+x^2-x^3+\ldots+x^{2k-2}-x^{2k-1}+x^{2k}\;,$$

which is $$\Big(1-x+x^2-x^3+\ldots+x^{2k-2}\Big)-x^{2k-1}+x^{2k}\;.$$ Thus, $P(k+1)$ is the statement

$$1-x+x^2-x^3+\ldots+x^{2k-2}-x^{2k-1}+x^{2k}=\frac{x^{2k+1}+1}{x+1}\;,$$

which can be usefully parenthesized as

$$\Big(1-x+x^2-x^3+\ldots+x^{2k-2}\Big)-x^{2k-1}+x^{2k}=\frac{x^{2k+1}+1}{x+1}\;.\tag{2}$$

This is useful because $P(k)$, the induction hypothesis, lets us replace

$$1-x+x^2-x^3+\ldots+x^{2k-2}$$

by $\dfrac{2^{2k-1}+1}{x+1}$ in $(2)$ to see that $P(k+1)$ is equivalent to the claim that

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

which is easily verified by a little elementary algebra.

I don’t know why the induction was started at $n=2$; presumably the theorem was stated that way, as the assertion that $P(n)$ holds for every $n\ge 2$. It could just as well have been started at $n=1$: since $2\cdot1-2=0$, $P(1)$ is

$$1=\frac{x^1+1}{x+1}=1\;,$$

which is certainly true.

-

Substitute $n=k+1$. Then the last member of the sum is $+x^{2n-2}=+x^{2k}$, and before it is $-x^{2k-1}$.

If $n$ increases by one, we get 2 more summands...

About the first step, yes, $n=1$ is enough, and trivial. But, usually it's good to see for small $n$'s what we are talking about..

-