# Problem with induction?

1. Jul 3, 2006

### EvLer

I don't quite see what i need to notice here:
the problem says try to prove this by induction and note what goes wrong:

1 + 1/2 + 1/4 + ... + 1/(2^n) < 2

so my solution so far is this:
Base case:
P(1): 1/(2^1) < 2 (true)

Assume P(k):
1/(2^k) < 2

Induction step P(k+1):
1/(2^(k+1)) < 2

expressing P(k+1) in terms of P(k):
1/(2^k) * 1/2 < 2

but how exactly to show what goes wrong here
Hints from anyone?

2. Jul 3, 2006

### StatusX

First of all, you want to show that the sum is less than 2, and this sum is not equal to 1/2^k. Second, this problem doesn't really make sense, because you can't just assume some expression is less than 2 and prove that adding another terms keeps it less than 2 unless you know how much less than 2 the original expression is.

That may be what they mean by "finding where induction goes wrong", but if so it's a very poor question. A more interesting and useful problem would be to find an expression for the sum of the first n terms and prove it is correct by induction, then show that the sum is always less than 2 for any integer n, but also show that this does not imply that the limit of the infinite sum is less than 2.

3. Jul 3, 2006

### 0rthodontist

Well, this is not P(k). P(k) has to have something to do with
$$\sum_{i=0}^k \frac{1}{2^i} < 2$$
But as StatusX mentioned, you can't do induction just by knowing P(k) is less than 2--you have to know how much less.
Continuing as StatusX suggested, let S(k) be the sum on the left side of that inequality. If you do some trial and error, you will find
S(0) = 2 - 1
S(1) = 2 - 1/2
S(2) = 2 - 1/4
...

Now what might you let P(k) be so that you can prove this in general?

Last edited: Jul 3, 2006