0
$\begingroup$

Prove by induction the following:

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

We want:

$$x^0+x^1+ \ldots + x^n = \frac{1-x^{n+1}}{1-x}$$

I try this for $i=1$ and it works, so I have an initial condition.

So assuming it works for all $i$:

$$[x^0+x^1+ \ldots + x^n] + x^{n+1} = \frac{1-x^{n+2}}{1-x}$$

We know the part in brackets and we know that it works for $i=1$.

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

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

And by crossing out two terms on top we arrive where we want to be.

Is this proof valid? I've just never been 100% sure when performing a proof by induction.

$\endgroup$
4

1 Answer 1

2
$\begingroup$

When you write "for $i=1$", I think you mean "for $n=1$". $i$ is just an index, which varies over all $0,1,\dots,n$ for a fixed $n$, so you want to show that the claim holds for all $n$, not all $i$. Other than that it looks pretty good.

EDIT actually I see a couple of very minor issues. Your general idea is right.

We begin with the base case: suppose that $n=0$. Then $\sum_{i=0}^{0}x^i=x^0=1=\frac{1-x^1}{1-x}$, so we're all good on that front.

Now, you wrote "So assuming it works for all $i$". I've already covered that we want to talk about $n$ and not $i$, but there's a bigger problem with how you've written this. We do not want to assume that it holds for all $n$; this, after all, is exactly what you're trying to prove. What you want to do is assume that it works for a particular $n$. The reason for this is that you'd like to show that if it holds for a particular $n$, then it holds for $n+1$. At this point, you'll have shown that it holds for $n=0$, and that if it holds for $n=0$ then it holds for $n=1$, and that if it holds for $n=1$ then ..., and so you'll have shown that it holds for all $n$. So here, you want to write "assume that it works for some number $n$". This seems like a minor nitpick, but you asked if the proof is "valid" as stated; as written, it's not.

But the algebra is all right and your basic idea will work once you frame it correctly.

$\endgroup$
3
  • $\begingroup$ Sometimes it is useful to be able to assume the formula works for a particular value of $n$ and for all smaller integer values of $n$, and then show that it follows that the formula works for the value $n + 1$. But in this case, you don't need that kind of induction. $\endgroup$
    – David K
    Apr 13, 2014 at 23:25
  • $\begingroup$ @DavidK I know. But either way, it is never correct to assume that the formula works for all $n$. $\endgroup$
    – crf
    Apr 13, 2014 at 23:30
  • $\begingroup$ Quite so. It is important to understand that even "this and all smaller values" is very different from "all values". The language in the question seemed confused on that point, and you were quite correct to point that out. $\endgroup$
    – David K
    Apr 13, 2014 at 23:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .