Proof by induction valid or not?

80 Views Asked by At

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.

1

There are 1 best solutions below

3
On

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.