# Thread: Mathematical induction

1. ## Mathematical induction

(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. Originally Posted by annitaz
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?
Add $(1/2)^{(k+1)}$ to both sides:

$(1/2)^0 + (1/2)^1 + ... + (1/2)^k + (1/2)^{(k+1)} = 2 - (1/2)^k + (1/2)^{(k+1)}$

Now simplify the right hand side and you are done.

3. Is the following correct?

((2.2^k+1)-2+1)/(2^(k+1)=2^(k+2)-1)/2^k+1=2-1/2^(k+1)

4. Originally Posted by annitaz
Is the following correct?

((2.2^k+1)-2+1)/(2^(k+1)=2^(k+2)-1)/2^k+1=2-1/2^(k+1)
Yes, if you add a few more pairs of parentheses:

$\frac{2 \cdot 2^{(k+1)} - 2 + 1}{2^{(k+1)}} = \frac{2^{(k+2)} - 1}{2^{(k+1)}} = 2 - (1/2)^{(k+1)}$

However, it's easier to do this:

$2 - (1/2)^k + (1/2)^{(k+1)} = 2 - 2 \cdot (1/2)^{(k+1)} + (1/2)^{(k+1)} = 2 - (1/2)^{(k+1)}$