# Thread: Recursive definition and induction principle

1. (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?

2.

3. Well, what's the difference between the element at k and the element at k+1? You've already assumed the element at k exists. Now you need to use that to prove the element at k+1 exists.

 Bookmarks
##### Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement