Results 1 to 2 of 2

Thread: Recursive definition and induction principle

  1. #1 Recursive definition and induction principle 
    Forum Freshman
    Join Date
    Jan 2010
    (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?

    Reply With Quote  


  3. #2  
    Forum Radioactive Isotope MagiMaster's Avatar
    Join Date
    Jul 2006
    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.

    Reply With Quote  

Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts