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 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.

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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer

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..

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.