# Mathematical induction

1. Mar 9, 2010

### annitaz

(a) Give a recursive definition of the set P of all non negative integers,
(b) formulate the applicable induction principle and
(c) then apply the induction principle to prove that 1/2^0+1/2^1+1/2^2....+1/2^i = 2-1/2^n for n>=0

I have solved parts a and b and stuck on c

(a) P is the smallest subset of R (Real numbers) such that 0 belongs to P and if k belongs to P then also k+1 belongs to P. Recursive definition

(b) If a subset B of P is such that 0 belongs to B and if k belongs to B then also k+1 belongs to B, then subset B is equal to P. Induction principle

(c) Proof:
Step 1:
Let B = {n│ n belongs to P, 1/2^0+1/2^1+1/2^2…+1/2^n = 2-1/2^n}

Step 2:
0 belongs to B: 0 belongs to B because 1/2^0 =2- 1/2^0 Therefore 1 = 1

Step 3:
Let k belong to B, thus 1/2^0+1/2^1+1/2^2…+1/2^k = 2-1/2^k
Is k+1 belong to B? I am stuck Here

Any ideas?