3
$\begingroup$

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.

  • 0
    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$.2012-10-29

2 Answers 2

4

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.

1

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